Aho-Corasick y subseries adecuadas

Estoy tratando de entender el algoritmo de concordancia de cadena aho-corasick. Supongamos que nuestros patrones son abcd y bc. Terminamos un árbol como esteAho-Corasick y subseries adecuadas

 [] 
     /\ 
    [a]..[b] 
    /: | 
    [b].: [c] 
    |  : 
    [c]..... 
    | 
    [d]

La línea punteada muestra la función de falla.

Ahora suponemos que alimentamos en la cadena abcd. Esto seguirá al árbol y detectará la coincidencia "abcd", sin embargo, hasta donde puedo decir, no se informará la coincidencia bc. ¿Estoy malentendiendo el algoritmo?

Fuente

2011-03-22 Winston Ewert

La respuesta de Artem es correcta, pero quizás no muy clara. Básicamente, lo que debe hacer es: cada vez que llegue a un nuevo nodo, examine la ruta completa comenzando desde este nodo y que consiste en enlaces de falla y encuentre coincidencias en esta ruta. (Esto no cambia su posición actual). En su ejemplo, usted examinaría las rutas b-> b (no se encontraron coincidencias) y c-> c (se encuentra la coincidencia bc).

Tenga en cuenta que, por razones de eficiencia, debe almacenar en caché el valor de "siguiente coincidencia" en cada nodo. Es decir, si examina la ruta comenzando en el nodo u y encuentra un nodo correspondiente v después de varios pasos, recuerde el valor next_match[u] = v para que la próxima vez cuando tenga que examinar esta ruta, pueda hacer un solo salto directamente al v.

Fuente

2011-03-22 19:36:08 adamax

A menos que esté malinterpretando, este no es el algoritmo de Aho-Corasick. Lo que estás describiendo es esencialmente un NFA. – dfb

@spinning_plate ¿Cómo es NFA si solo hay un nodo actual en cada paso? – adamax

"Cada vez que llegue a un nuevo nodo, examine la ruta completa comenzando desde este nodo y consiste en enlaces de falla y encuentre coincidencias en esta ruta" - Está atravesando las rutas de falla mientras mantiene la misma posición para continuar más adelante. Esto produce el mismo resultado si ha evaluado el trie como un NFA. ¿Puede proporcionar una referencia a una implementación de Aho-Corasick que evalúa los enlaces de falla cuando no hay falla? – dfb

Parte de la configuración del árbol AhoCorasick es configurar los punteros que le indican a dónde ir en el árbol si el siguiente carácter no coincide. P.ej. si sigue la secuencia abcq en el árbol tal como la dibujó, debe saltar de la posición abc a la posición bc para ver si hay una q debajo de bc. Puede usar este pase para configurar otro puntero para indicarle que marque una coincidencia en bcd luego de señalar una coincidencia en abcd, y así sucesivamente.

Al escribirlo, encontré la fuente de sgrep en http://www.cs.helsinki.fi/~jjaakkol/sgrep.html muy útil. Por lo que puedo recordar, sgrep hace MUCHO más que AhoCorasick, pero tiene una implementación de AhoCorsick como parte de él.

Fuente

2011-03-22 18:21:15 mcdowella

Debe marcar los nodos como realmente_final si hay una cadena terminada en este nodo. En su ejemplo, tales nodos son "abcd" y "bc". Después tiene que calcular los estados finales para los nodos: el nodo es final si es realmente_final o la función de nodo por falla es definitiva. Por lo tanto, "abcd", "bc" y "abc" serán definitivos.

En otras palabras, el nodo es definitivo si algún patrón termina aquí o algún nodo final es alcanzable desde el nodo actual caminando por enlaces de falla.

Fuente

2011-03-22 18:22:17

Respuesta

Cuestiones relacionadas