Escalabilidad de aho corasick

Question

Quiero buscar en un documento de texto las apariciones de frases clave de una base de datos de frases clave (extraída de títulos de artículos de wikipedia). (es decir, dado un documento que deseo encontrar si alguna de las frases tiene un artículo correspondiente de Wikipedia), descubrí el algoritmo Aho-Corasick. Quiero saber si la construcción de un autómata Aho-Corasick para el diccionario de millones de entradas es eficiente y escalable.

Answer 1

En teoría, debería mantener la velocidad lineal sujeta únicamente a los efectos de la jerarquía de la memoria: se ralentizará, ya que es demasiado grande para caber en la memoria caché, y cuando se pone realmente grande, tendrá problemas si comienza a ser paginado.

OTOH la gran victoria con Aho-Corasick es cuando se buscan subcadenas de tamaño decente que pueden aparecer en cualquier ubicación dentro de la cadena alimentada. Si su documento de texto ya está cortado en palabras, y sus frases de búsqueda no son más que, por ejemplo 6 palabras, luego puede construir una tabla hash de frases de palabras K, y luego buscar cada sección contigua de palabras K de las palabras del texto de entrada, para K = 1..6.

(respuesta al comentario)

Aho-Corasick necesita para vivir en la memoria, porque se van a seguir punteros en todo el lugar. Si tiene que trabajar fuera de la memoria, probablemente sea más fácil volver al modo/fusión anticuado. Cree un archivo de registros de palabras K a partir de los datos de entrada, donde K es el número máximo de palabras en cualquier frase que le interese. Ordene y luego combínelo con un archivo de frases ordenadas de Wikipedia. Probablemente puedas hacer esto casi a mano en Unix/Linux, usando utilidades como ordenar y unir, y un poco de shell/awk/perl/whatever. Consulte también http://en.wikipedia.org/wiki/Key_Word_in_Context (Tengo la edad suficiente para haber utilizado uno de estos índices, proporcionado como páginas enlazadas de la impresión de la computadora).

Answer 2

Bueno, hay una solución. Escribiendo el trie de AC construido del diccionario en un archivo de texto en formato xml, haciendo un archivo de índice para los primeros 6 niveles de ese trie, etc ... En mis pruebas busco todas las coincidencias parciales de una oración en el diccionario (500'000 entradas), y obtengo ~ 150ms por ~ 100 resultados por una oración de 150-200 símbolos.

Para más detalles, echa un vistazo a este artículo: http://212.34.233.26/aram/IJITA17v2A.Avetisyan.doc

Answer 3

Vamos a hacer unos cálculos sencillos:

Suponga que tiene 1 millón de patrones (cadenas, frases) con promedio de longitud de 10 caracteres y un valor (etiqueta, token, puntero, etc.) de 1 palabra (4 bytes) de longitud, asignada a cada patrón

Luego necesitará una matriz de 10 + 4 = 14 millones de bytes (14 Mb) solo para mantener la lista de patrones.

De 1 millón de patrones 10 bytes (letras, caracteres) cada uno podría construir un AC trie con no más de 10 millones de nodos. ¿Qué tan grande es este trie en la práctica depende del tamaño de cada nodo. Al menos debe conservar 1 byte para una etiqueta (letra) y palabra (4 bytes) para un puntero a un siguiente nodo en trie (o un patrón para un nodo terminal) más 1 bit (booleano) para marcar el nodo terminal, Total aproximadamente 5 bytes

Por lo tanto, el tamaño mínimo de un trie para 1 millón de patrones de 10 caracteres requerirá un mínimo de 50 millones de bytes o aproximadamente 50 MB de memoria.

En la práctica puede ser 3-10 veces más, pero aún así es muy manejable, ya que incluso la memoria de 500 Mb es muy moderada en la actualidad.(Compárese con aplicaciones de Windows como Word o Outlook)

dado que en términos de velocidad de algoritmo de Aho-Corasick (AC) es casi inmejorable, sigue siendo el mejor algoritmo de coincidencia de patrón múltiple nunca. Esa es mi fuerte opinión educada personal aparte de la basura académica.

Todos los informes de "nuevos" y más nuevo algoritmos que pueden obtener rentabilidades superiores AC son muy exageradas (excepto tal vez para algunos casos especiales con patrones cortos como el ADN)

La única mejora de la CA en la práctica podría ir a lo largo de la línea de un hardware más rápido y más rápido (núcleos múltiples, CPUs más rápidas, clusters, etc.)

No tome mi palabra, pruébelo usted mismo. Pero recuerde que la velocidad real de la CA depende en gran medida de la implementación (idioma y calidad de la codificación)