algorithm - pratt - como funciona el algoritmo kmp
Algoritmo para encontrar múltiples coincidencias de cadena (6)
Estoy buscando sugerencias para un algoritmo eficiente para encontrar todas las coincidencias en un gran cuerpo de texto. Los términos para buscar estarán en una lista y pueden tener más de 1000 posibilidades. Los términos de búsqueda pueden ser 1 o más palabras.
Obviamente, podría hacer múltiples pasadas a través del texto comparando con cada término de búsqueda. No demasiado eficiente.
He pensado en ordenar los términos de búsqueda y combinar sub-segmentos comunes. De esa manera podría eliminar grandes cantidades de términos rápidamente. El lenguaje es C ++ y puedo usar boost.
Un ejemplo de términos de búsqueda podría ser una lista de nombres de empresas de Fortune 500.
Ideas?
No reinventar la rueda
Este problema ha sido intensamente investigado. Curiosamente, los mejores algoritmos para buscar UN patrón / cadena no extrapolan fácilmente a la coincidencia de múltiples cadenas.
La familia "grep" implementa la búsqueda de cadenas múltiples de una manera muy eficiente. Si puede usarlos como programas externos, hágalo.
En caso de que realmente necesite implementar el algoritmo, creo que la manera más rápida es reproducir lo que agrega agrep (¡agrep sobresale en la coincidencia de cadenas múltiples!). Here están los archivos fuente y ejecutables.
Y here encontrará un documento que describe los algoritmos utilizados, los antecedentes teóricos, y una gran cantidad de información y sugerencias sobre la coincidencia de cadenas.
Una nota de advertencia: la coincidencia de cadenas múltiples ha sido muy investigada por personas como Knuth, Boyer, Moore, Baeza-Yates y otros. Si necesita un algoritmo realmente rápido, no dude en pararse sobre sus anchos hombros. No reinventar la rueda.
¿Entonces tienes muchos términos de búsqueda y quieres ver si alguno de ellos está en el documento?
Puramente algorítmicamente, puede ordenar todas sus posibilidades en orden alfabético, unirlas con tuberías y usarlas como una expresión regular, si el motor de expresiones regulares verá /ant|ape/ y cortocircuitará adecuadamente la a en "simio" si no lo encontró en "hormiga". De lo contrario, podría hacer una "precompilación" de una expresión regular y "aplastar" los resultados hasta su solapamiento mínimo. Es decir, en el caso anterior /a(nt|pe)/ y así sucesivamente, de forma recursiva para cada letra.
Sin embargo, hacer lo anterior es más o menos como poner todas las cadenas de búsqueda en un árbol de 26 arios (26 caracteres, más si también hay números). Empuja tus hilos en el árbol, usando un nivel de profundidad por carácter de longitud.
Puede hacer esto con sus términos de búsqueda para hacer un hiper-rápido "si esta palabra coincide con cualquier cosa en mi lista de términos de búsqueda" si el número de términos de búsqueda es grande.
En teoría, también podría hacer lo contrario: empaque su documento en el árbol y luego use los términos de búsqueda en él, si su documento es estático y los términos de búsqueda cambian mucho.
Depende de cuánta optimización necesita ...
¿Son los términos de búsqueda las palabras que está buscando o puede ser también una representación completa?
Si solo son palabras, sugeriría construir un Árbol Rojo-Negro de todas las palabras, y luego buscar cada palabra en el árbol.
Si pudieran ser sentances, entonces podría ser mucho más complejo ... (?)
Como en el caso de patrones únicos, existen varios algoritmos para la coincidencia de patrones múltiples, y tendrá que encontrar el que mejor se adapte a su propósito. El artículo Un algoritmo rápido para la búsqueda de patrones múltiples (copia archivada) hace una revisión de la mayoría de ellos, incluido Aho-Corasick (que es una especie de versión de patrones múltiples del algoritmo Knuth-Morris-Pratt, con complejidad lineal) y Commentz-Walter (una combinación de Boyer-Moore y Aho-Corasick), e introduce uno nuevo, que usa ideas de Boyer-Moore para la tarea de emparejar múltiples patrones.
Un algoritmo alternativo basado en hash no mencionado en ese documento es el algoritmo Rabin-Karp , que tiene una complejidad en el peor caso más grande que otros algoritmos, pero lo compensa reduciendo el factor lineal mediante hash. Cuál es mejor depende en última instancia de su caso de uso. Es posible que deba implementar varios de ellos y compararlos en su aplicación si desea elegir el más rápido.
Suponiendo que la gran cantidad de texto es texto estático en inglés y necesitas unir palabras enteras, puedes intentar lo siguiente (realmente debes aclarar qué es exactamente una "coincidencia", qué tipo de texto estás viendo, etc. en tu pregunta).
Primero preprocesé todo el documento en un Trie o un DAWG .
Trie / Dawg tiene la siguiente propiedad:
Dado un trie / dawg y un término de búsqueda de longitud K, puede en O (K) tiempo buscar los datos asociados con la palabra (o indicar si no hay coincidencia).
Usar un DAWG podría ahorrarle más espacio en comparación con un trie. Intenta explotar el hecho de que muchas palabras tendrán un prefijo común y los DAWG explotan el prefijo común, así como la propiedad de sufijo común.
En el trie, también mantener exactamente la lista de posiciones de la palabra. Por ejemplo, si el texto es
That is that and so it is.
El nodo para la última t en that tendrá la lista {1,3} y el nodo para s in tendrá la lista {2,7} asociada.
Ahora, cuando obtiene un término de búsqueda de una sola palabra, puede recorrer el trie y obtener fácilmente la lista de coincidencias para esa palabra.
Si obtiene un término de búsqueda de palabras múltiples, puede hacer lo siguiente.
Recorre el trie con la primera palabra en el término de búsqueda. Obtenga la lista de coincidencias e inserte en un hashTable H1.
Ahora recorra el trie con la segunda palabra en el término de búsqueda. Obtenga la lista de coincidencias. Para cada posición coincidente x, compruebe si x-1 existe en HashTable H1. Si es así, agrega x a la nueva tabla hash H2.
Recorre el trie con la tercera palabra, obtén una lista de coincidencias. Para cada posición de coincidencia y, compruebe si y-1 existe en H3, de ser así, agréguela a la nueva tabla hash H3.
Continúa así sucesivamente.
Al final se obtiene una lista de coincidencias para la frase de búsqueda, que da las posiciones de la última palabra de la frase.
Usted podría potencialmente optimizar el paso de emparejamiento de frase manteniendo una lista ordenada de posiciones en la lista y haciendo una búsqueda binaria, es decir, por ejemplo. para cada tecla k en H2, busca binariamente k + 1 en la lista ordenada para el término de búsqueda 3 y agrega k + 1 a H3 si la encuentras, etc.
Una solución óptima para este problema es usar un árbol de sufijos (o una matriz de sufijos ). Es esencialmente un trie de todos los sufijos de una cadena. Para un texto de longitud O(N) , esto se puede construir en O(N) .
Entonces, todas las k ocurrencias de una cadena de longitud m pueden responderse de manera óptima en O(m + k) .
Los sufijos también se pueden usar para encontrar eficientemente, por ejemplo, el palíndromo más largo, la subcadena común más larga, la subcadena repetida más larga, etc.
Esta es la estructura de datos típica para usar al analizar cadenas de ADN que pueden ser millones / miles de millones de bases de longitud.
Ver también
- Wikipedia / Suffix tree
- Algoritmos en cadenas, árboles y secuencias: informática y biología computacional (Dan Gusfield).