Algoritmo Aho - Korasik

El algoritmo Aho-Korasik es un algoritmo de búsqueda de subcadenas desarrollado por Alfred Aho y Margaret Korasik en 1975 [1] que busca un conjunto de subcadenas de un diccionario en una cadena dada .

Ampliamente utilizado en el software del sistema, como la utilidad de búsqueda grep [2] .

Cómo funciona

El algoritmo construye una máquina de estado , a la que luego pasa la cadena de búsqueda. El autómata recibe uno por uno todos los caracteres de la cadena y se desplaza por los bordes correspondientes. Si el autómata ha alcanzado el estado final, la cadena de diccionario correspondiente está presente en la cadena de búsqueda.

Se pueden combinar varias cadenas de búsqueda en un árbol de búsqueda, el llamado boro (árbol de prefijos). Bor es una máquina de estado que reconoce una línea desde , pero con la condición de que se conozca el comienzo de la línea. $metro$

La primera tarea del algoritmo es enseñar al autómata a "recuperarse" si la subcadena no coincide. Al mismo tiempo, restablecer el autómata a su estado inicial para cualquier letra no adecuada no es adecuado, ya que esto puede provocar que se salte una subcadena (por ejemplo, al buscar una cadena aabab, se encuentra , después de leer el quinto carácter, transfiriendo el autómata a su estado inicial conducirá a omitir una subcadena; sería correcto ir al estado y luego procesar el quinto carácter nuevamente). Para hacer que el autómata se autorrepare, se le agregan enlaces de sufijo cargados con el símbolo vacío ⌀ (para que un autómata determinista se convierta en uno no determinista). Por ejemplo, si se analiza la cadena , los sufijos , , . Un enlace de sufijo es un enlace a un nodo que coincide con el sufijo más largo que no conduce a la perforación a un callejón sin salida (en este caso ). aabaababaaabaababaaa

Para el nodo raíz, el enlace de sufijo es un bucle. Por lo demás, la regla es la siguiente: si el último carácter reconocido es , entonces se omite el enlace del sufijo del padre, si hay un arco cargado con el carácter de allí , el enlace del sufijo se dirige al nodo donde se encuentra este arco. Guías. De lo contrario, el algoritmo atraviesa el enlace del sufijo una y otra vez hasta que atraviesa el enlace del bucle raíz o encuentra un arco cargado con el símbolo . $C$ $C$ $C$

* ···Ø···> * ···Ø···> * ···Ø···> * | | cc _ ↓ ↓ [*] Ø Ø nuevo enlace de sufijo

Este autómata no es determinista. Convertir un autómata finito no determinista en uno determinista generalmente conduce a un aumento significativo en el número de vértices. Pero este autómata se puede convertir en un autómata determinista sin crear nuevos vértices: si no hay ningún lugar para que un vértice vaya por el símbolo , pasamos por el enlace del sufijo una y otra vez hasta que lleguemos a la raíz o haya un lugar para ir por el símbolo . $v$ $C$ $C$

Es conveniente hacer toda la determinación recursivamente. Por ejemplo, para un enlace de sufijo:

sufijo alg(v) if v.cacheSuffRef ≠ Ø // para root, inicialmente root.cacheSuffRef = root volver v.cacheSuffReference u := v.padre c := v.símbolo repetir u := SufReferencia(u) antes de (u = raíz) o (hay un camino u --c→ w) si hay una transición u —c→ w entonces v.cacheSuffref := w de lo contrario v.cacheSuffReference := root volver v.cacheSuffReference

La determinación aumenta el número de vértices finales: si los enlaces de sufijo de un vértice conducen al vértice final , también se declara final. Para esto, se crean los llamados enlaces finales: el enlace final conduce al nodo final más cercano a los enlaces de sufijo; el recorrido de las referencias finales devuelve todas las filas coincidentes. $v$ $tu$ $v$

alg SalidaResultado(v, i) imprime "Encontrado" + v.aguja + "en la posición" + (i - v.profundidad + 1) alg MainPartSearch estado := raíz bucle i=1..|pajar| estado := Transición(estado, pajar[i]); si condición.aguja ≠ Ø OutputResult(estado, i) timeStat := estado mientras que RefFinal(const.tiempo) ≠ Ø tempst := EndRef(timestst); Resultado de salida (Const. de tiempo, i)

Los enlaces de sufijo y final en el autómata se pueden calcular según sea necesario ya en la fase de búsqueda. Transiciones laterales: puede calcular en el lugar sin almacenar en caché de ninguna manera , puede almacenar en caché para todos los nodos, puede hacerlo, para los más importantes (todo esto no afecta la estimación asintótica del algoritmo).

Complejidad computacional

La complejidad computacional del algoritmo depende de la organización de los datos. Por ejemplo:

Si la tabla de saltos del autómata se almacena como una matriz de índices - consumo de memoria , complejidad computacional , donde - la longitud del texto en el que se realiza la búsqueda, - la longitud total de todas las palabras en el diccionario, - el tamaño del alfabeto, - la duración total de todos los partidos. ${\ estilo de visualización O (n \ sigma)}$ ${\ estilo de visualización O (n \ sigma + H + k)}$ $H$ $norte$ $\sigma$ $k$
Si la tabla de transición del autómata se almacena como un árbol rojo-negro , el consumo de memoria disminuye a , pero la complejidad computacional aumenta a . $En)$ ${\ estilo de visualización O ((H + n) \ registro \ sigma + k)}$

Notas

↑ Alfred V. Aho, Margaret J. Corasick. Coincidencia eficiente de cadenas: una ayuda para la búsqueda bibliográfica // Comunicaciones de la ACM . - 1975. - T. 18 , N º 6 . - S. 333-340 . -doi : 10.1145/ 360825.360855 .
↑ grep-2.26 publicado [estable ] . www.mail-archive.com. Consultado el 4 de octubre de 2016. Archivado desde el original el 5 de octubre de 2016. (indefinido)

Enlaces

https://xlinux.nist.gov/dads/HTML/ahoCorasick.html

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitudes Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común