En informática , el algoritmo Commentz-Walter es un algoritmo de búsqueda de cadenas inventado por Beate Commentz-Walter. [1] Al igual que el algoritmo de coincidencia de cadenas Aho-Corasick , puede buscar múltiples patrones a la vez. Combina ideas de Aho-Corasick con la coincidencia rápida del algoritmo de búsqueda de cadenas Boyer-Moore . Para un texto de longitud n y una longitud máxima de patrón de m , su tiempo de ejecución en el peor de los casos es O ( mn ), aunque el caso promedio suele ser mucho mejor. [2]
GNU grep una vez implementó un algoritmo de coincidencia de cadenas muy similar a Commentz-Walter. [3]
El artículo sobre el algoritmo fue publicado por primera vez por Beate Commentz-Walter en 1979 a través de la Universidad del Sarre y mecanografiado por "R. Scherner". [1] El artículo detallaba dos algoritmos diferentes que, según ella, combinaban la idea de los algoritmos Aho-Corasick y Boyer-Moore , a los que llamó algoritmos B y B1. Sin embargo, el artículo se centra principalmente en el algoritmo B.
El algoritmo Commentz-Walter combina dos algoritmos conocidos para intentar abordar mejor el problema de coincidencia de múltiples patrones. Estos dos algoritmos son Boyer-Moore , que aborda la coincidencia de un solo patrón mediante filtrado, y Aho-Corasick . Para ello, el algoritmo implementa un autómata de sufijo para buscar patrones dentro de una cadena de entrada, mientras que también utiliza patrones inversos, a diferencia de Aho-Corasick . [4]
Commentz-Walter tiene dos fases por las que debe pasar: una fase de precomputación y una fase de emparejamiento. Para la primera fase, el algoritmo Commentz-Walter utiliza un patrón invertido para construir un árbol de patrones; esta se considera la fase de precomputación. La segunda fase, conocida como la fase de emparejamiento, tiene en cuenta los otros dos algoritmos. Utilizando la técnica de desplazamiento de Boyer-Moore y la técnica de autómatas finitos de Aho-Corasick , el algoritmo Commentz-Walter puede comenzar a emparejar. [4]
El algoritmo Commentz-Walter escaneará hacia atrás toda la cadena de entrada para comprobar si hay alguna discrepancia. Si encuentra alguna, ya sabrá algunos de los caracteres que coinciden y utilizará esta información como índice. Con el índice, el algoritmo comprueba la tabla precalculada para encontrar la distancia que debe desplazarse y, después, vuelve a intentar realizar otra búsqueda de coincidencia.
La comparación del algoritmo Aho-Corasick con el algoritmo Commentz-Walter arroja resultados con la idea de complejidad temporal. Aho-Corasick se considera lineal O ( m+n+k ) donde k es el número de coincidencias. Commentz-Walter puede considerarse cuadrático O ( mn ). La razón de esto radica en el hecho de que Commentz-Walter se desarrolló agregando los cambios dentro del algoritmo de búsqueda de cadenas de Boyer-Moore al algoritmo Aho-Corasick , lo que movió su complejidad de lineal a cuadrática.
Según un estudio realizado en “The Journal of National Science Foundation of Sri Lanka 46”, Commentz-Walter parece ser en general más rápido que el algoritmo de comparación de cadenas Aho-Corasick . Esto, según la revista, solo ocurre cuando se utilizan patrones largos. Sin embargo, la revista afirma que no existe un análisis crítico sobre esta afirmación y que no hay un acuerdo general sobre el rendimiento del algoritmo. [5]
Como se ve en una visualización del tiempo de ejecución del algoritmo realizada en un estudio de “The International Journal of Advanced Computer Science and Information Technology”, el rendimiento del algoritmo aumentó linealmente a medida que aumentaba el patrón más corto dentro del conjunto de patrones. [4]
En el artículo original de Commentz-Walter también se creó un algoritmo alternativo, conocido como B1, que funciona de manera similar al algoritmo principal de Commentz-Walter, con la única diferencia en la forma en que se utiliza el árbol de patrones durante la fase de escaneo.
El artículo también afirma que este algoritmo funciona mejor a costa de aumentar el tiempo y el espacio de ejecución tanto de la fase de preprocesamiento como de la fase de búsqueda. Sin embargo, este algoritmo no se ha probado formalmente en otros estudios, por lo que se desconoce su rendimiento real. [1]