Commentz-Walter

Introducción

El algoritmo de Commentz-Walter (1979)$^1$, nombre heredado de su autora Beate Commentz-Walter, es un algoritmo diseñado para búsqueda de múltiples patrones basado en sufijos y máquinas de estado finito, el cual combina técnicas de dos algoritmos muy reconocidos: Aho-Corasick y Boyer-Moore. En particular, sea el conjunto de palabras K en un documento D, las ideas captadas de estos autores fueron:

Aho-Corasick: Toma la idea de preprocesar el conjunto de palabras clave K en una única estructura, un trie. También utiliza una función de "fallo" similar a la de Aho-Corasick para calcular los saltos.
Boyer-Moore: Toma la idea de escanear el texto de derecha a izquierda. Esto permite que la fase de búsqueda en promedio sea sublineal, inspeccionando menos caracteres que la longitud total del documento (aproximadamente $\frac{|D|}{wmin}$, donde $wmin$ es el tamaño de clave mínimo del conjunto K).

Una de las mayores diferencias con estos algoritmos es que el trie se construye sobre las palabras invertidas.

Este algoritmo alcanza tiempo sublineal en promedio, pero en el peor caso no se mantiene lineal. La misma autora publicó modificaciones de su algoritmo para evitar el peor caso, pero ella consideraba que en la práctica, el algoritmo original tiene mejor rendimiento. Por esta razón, en este artículo solo se presentará el algoritmo original.

A nivel de rendimiento y para el caso promedio, el algoritmo de Commentz-Walter (de ahora en adelante CW) es ligeramente superior a algunos de sus símiles clásicos, como el algoritmo de Wu-Manber y Aho-Corasick$^2$.

Definición

El algoritmo tiene dos fases principales, la de preprocesamiento (que se ejecuta una sola vez) y la de búsqueda (que se ejecuta sobre el texto).

Fase de preprocesamiento

Esta fase toma como entrada el conjunto de palabras clave $K = \{w_1, ..., w_r\}$ y produce la estructura de datos necesaria para la búsqueda.

Construimos un trie $T$. Este trie se basa en las palabras clave invertidas ($w^R$). Por cada palabra clave $w_h$ en $K$, existe un nodo $v_h$ en el trie tal que la ruta desde la raíz hasta $v_h$ representa la palabra $w_h^R$ (invertida).
Calculamos la función de salida out(v) para cada nodo $v$ en el trie $T$. Más formalmente, out(v) se define como el conjunto de palabras clave originales $w$ (del conjunto $K$) tales que su inversión $w^R$ es igual a la ruta $w(v)$ desde la raíz hasta $v$ .
Calculamos la función char(a) para cada carácter $a$ en el alfabeto $A$. El valor de char(a) es el mínimo entre la profundidad más superficial $d(v)$ donde un nodo $v$ está etiquetado con el carácter $a$ y el valor $wmin+1$, donde $wmin$ es la longitud de la palabra clave $w_i$ más corta en $K$ . Matemáticamente: $ char(a) = \min(d(v), wmin+1)$
Calculamos las funciones de enteros shift1 y shift2 a cada nodo del trie. Estas funciones están relacionadas a las funciones failure de Aho-Corasick. Se basan en las funciones set1(v) (el conjunto de nodos $v$ para los cuales $w(v)$ es un sufijo propio de $w(v')$) y set2(v) (nodos en set1(v) que también tienen una salida en out). Así:
shift1(v) es el salto mínimo necesario para alinear el siguiente sufijo (basado en set1(v)).
shift2(v) es el salto mínimo necesario para alinear la siguiente coincidencia (basado en set2(v)).

Un sufijo propio es una cadena que es sufijo de otra cadena, pero no es igual a esa cadena. Más formalmente, la cadena $w(v)$ es un sufijo propio de $w(v')$ si se cumple la ecuación $w(v')= uw(v)$, donde $u$ es una palabra no vacía. Ejemplo: "papa", sufijos propios son "apa", "pa", "a", pero no "papa".

Todo este proceso de preprocesamiento se ejecuta en un tiempo lineal respecto a la suma total de las longitudes de las palabras clave $K$.

Fase de búsqueda

Esta fase toma como entrada el documento $D$ y el trie $T$ preprocesado (con sus funciones out, shift1, shift2 y char). Su objetivo es encontrar todas las ocurrencias de las palabras clave. El algoritmo CW combina la idea de escanear de derecha a izquierda (como Boyer-Moore) con el trie de palabras clave invertidas.

Inicialización

Establecemos v ← root r ( $v$ es el nodo actual del trie).
Establecemos i ← wmin ( $i$ es el puntero en el documento, alineado al final de la primera ventana de escaneo).
Establecemos j ← 0 ( $j$ indica la profundidad actual en el trie, o cuántos caracteres se han emparejado hacia la izquierda).

Bucle principal

Ejecutamos un bucle while i <= length(document) do:
- Se ejecuta un bucle while interno que intenta coincidir caracteres del documento hacia la izquierda: while there is some son $v'$ of $v$ labeled by $d_{i-j}$ do: (Donde $d_{i−j}$ es el carácter del documento que se está inspeccionando).
Si hay coincidencia:
```
    v ← v' (Se avanza al nodo hijo en el trie)
    j ← j + 1 (Se incrementa la profundidad de coincidencia)

    output: (W, i) for each w of out(v) (Si el nodo v es un estado final, se reporta una coincidencia de la palabra W terminando en la posición i).
```
Si hay desajuste (Mismatch): - El bucle while interno termina. Se procede a la fase de salto.

Fase de salto

Calculamos la longitud del salto $s(v,d_{i−j})$ usando el nodo actual v y el carácter $d_{i−j}$ que causó el desajuste. El cálculo del salto es: $\(s(v,d_{i−j}) = \min(\max(shift1(v), char(d_{i−j})−j−1), shift2(v))$\)
Actualizamos el puntero del documento $i←i+s(v,d_{i−j})$
Reiniciamos variables de escaneo $j←0$ y $v←root r$ (implícito para el siguiente ciclo del bucle principal ).
Fin: El bucle principal continúa hasta que $i$ sobrepasa la longitud del documento $D$.

Ejemplo de uso

Para poder tener un ejemplo más práctico de lo dicho en la definición (muy densa, por cierto) abarcaremos algo más ilustrativo en esta sección. Utilizaremos un conjunto pequeño de patrones $K$ y texto $D$:

$K$ = {EL, ELLA, MAR}
$D$ = ELLA Y EL

Fase de preprocesamiento

Calculamos los patrones invertidos: {LE, ALLE, RAM}
Buscamos la longitud mínima $wmin$, en este caso será la palabra EL con largo 2.
Construimos el trie con los patrones invertidos, como se ve en el grafo a continuación. Los nodos con doble círculo son nodos de salida (tienen una entrada en out(v)):

Trie

Funciones de salto: char(a)
char(L) = Buscamos la letra L en todo el trie de patrones invertidos. Encontramos la profundidad más superficial en donde aparece, en este caso 1. Si la letra no existiera en nuestro trie (como el espacio " ") sería $wmin + 1$. Finalmente calculamos el mínimo entre los dos, en este caso $\min (1, 3) = 1$.
char(A) = 1
char(R) = 1
char(E) = 2
char(" ") = wmin + 1 = 3
...

Fase de búsqueda

[ E, L, L, A, _, Y, _, E, L ], $n = 9$. Usaremos 1-indexación. Inicializamos:

v = root
i = wmin = 2
j = 0

Iteración 1: i=2

Iniciamos Fase de Escaneo:

j=0: Comparamos d[i-j] = d[2] = 'L' El root sí tiene un hijo 'L'. Avanzamos: v es ahora el nodo 'L', j se vuelve 1. out(v) está vacío
j=1: Comparamos d[i-j] = d[1] = 'E' El nodo 'L' sí tiene un hijo 'E'. Avanzamos: v es ahora el nodo 'E' (de "LE"), j se vuelve 2.
Coincidencia!: out(v) contiene {"EL"}. Reportamos coincidencia (termina en i=2)
j=2: Comparamos d[i-j] = d[0]. El índice es inválido, el escaneo no puede continuar.

Fin del Escaneo.

Fase de Salto: v = Nodo 'LE', j = 2. Usamos la fórmula: s = min(shift2(v), ...) (Asumiendo shift2(LE) = 2 (longitud del patrón)) s = 2

Actualización: i = i + s = 2 + 2 = 4. j se resetea a 0.

Iteración 2: i=4

Iniciamos Fase de Escaneo:

j=0: Comparamos d[i-j] = d[4] = 'A'. El root sí tiene un hijo 'A'. Avanzamos: v = Nodo 'A', j = 1.
j=1: Comparamos d[i-j] = d[3] = 'L'. El nodo 'A' sí tiene un hijo 'L'. Avanzamos: v = Nodo 'L' (de "AL"), j = 2.
j=2: Comparamos d[i-j] = d[2] = 'L'. El nodo 'L' (de "AL") sí tiene un hijo 'L'. Avanzamos: v = Nodo 'L' (de "ALL"), j = 3.
j=3: Comparamos d[i-j] = d[1] = 'E'. El nodo 'L' (de "ALL") sí tiene un hijo 'E'. Avanzamos: v = Nodo 'E' (de "ALLE"), j = 4.
Coincidencia!: out(v) contiene {"ELLA"}. Reportamos coincidencia (termina en i=4).
j=4: Comparamos d[i-j] = d[0]. El índice es inválido.

Fin del Escaneo.

Fase de Salto: v = Nodo 'ALLE', j = 4. (Asumiendo shift2(ALLE) = 4 (longitud del patrón)) s = 4

Actualización: i = i + s = 4 + 4 = 8. j se resetea a 0.

Iteración 3: i=8

Iniciamos Fase de Escaneo:

j=0: Comparamos d[i-j] = d[8] = 'E'. El root sí tiene un hijo 'E'. Avanzamos: v = Nodo 'E', j = 1.
j=1: Comparamos d[i-j] = d[7] = ' '. El nodo 'E' no tiene un hijo ' '.

Fin del Escaneo (Desajuste).

Fase de Salto: v = Nodo 'E', j = 1, Carácter de desajuste = ' '.

\[s = \min(\max(shift_1(E), char("\_")-j-1), shift_2(E))\]

(Asumiendo shift1(E)=1 y shift2(E)=2 heredado)

\[s = \min(\max(1, 3-1-1), 2) = \min(\max(1, 1), 2) = 1\]

Actualización: i = i + s = 8 + 1 = 9. j se resetea a 0.

Iteración 4: i=9

Iniciamos Fase de Escaneo:

j=0: d[9] = 'L'. Coincide. v='L', j=1
j=1: d[8] = 'E'. Coincide. v='LE', j=2
Coincidencia!: out(v) tiene {"EL"}. Reportamos coincidencia (termina en i=9).
j=2: d[7] = ' '. El nodo 'LE' no tiene hijo ' '.

Fin del Escaneo (Desajuste).

Fase de Salto: v = Nodo 'LE', j = 2, Carácter de desajuste = ' '.

\[s = \min(\max(shift_1(LE), char("\_")-j-1), shift_2(LE))\]

(Asumiendo shift1(LE)=1 y shift2(LE)=2)

\[s = \min(\max(1, 3-2-1), 2) = \min(\max(1, 0), 2) = 1\]

Actualización: i = i + s = 9 + 1 = 10. j se resetea a 0.

Iteración 5: i=10

while i <= n (while 10 <= 9) es Falso, por lo que el bucle termina.

Implementación

Este pseudocódigo fue recuperado de $^2$

alt text

Referencias

Commentz-Walter B. (1979). A String Matching Algorithm Fast on the Average. Proceedings of the 6^th International Colloquium on Automata, Languages and Programming, volumen 71, pp 118-132. Springer, Berlin, Germany. DOI: https://doi.org/10.1007/3-540-09510-1_10
Sheshasaayee, Ananthi & Rajagopalan, Thailambal. (2017). Performance of Multiple String Matching Algorithms in Text Mining. DOI: https://doi.org/10.1007/978-981-10-3156-4_71.