Dado un gran diccionario de N frases cortas (1 o 2 términos) y una gran porción de texto, ¿puedo encontrar de manera eficiente las coincidencias para esas frases en el texto en tiempo sub-N, mientras perdono * los pequeños errores?

Parece que solo necesita un algoritmo para hacer una coincidencia difusa entre una cadena pequeña y un diccionario grande. El truco es encontrar una manera de hacerlo en un número constante de búsquedas hash. Así es como lo haría usando los trucos que conozco:

1. Para cada una de las entradas de su diccionario N, use algunas funciones diferentes de muchos a uno para asignarlo a unos pocos “núcleos” (imágenes de funciones). Por ejemplo, si la entrada es “cuarto de libra”, una de las funciones puede ser una derivación que la asigna a “cuarto de libra”, una de las funciones puede ser un alfabetizador que la asigna a “cuarto de libra” (pone las palabras en orden alfabético para indexarlo de una manera que sea independiente del orden original de las palabras), etc. Podría ser mejor combinar un stemmer y un alfabetizador y otras operaciones de reducción del núcleo en la misma función de muchos a uno.
2. Ahora genere un número limitado de “errores tipográficos” para todos los núcleos y almacénelos en su tabla hash. Tenga en cuenta que el conjunto de errores tipográficos de una cadena del núcleo no debería ser realmente un conjunto de errores tipográficos de esa cadena, sino más bien la imagen de la función muchos a uno de ese núcleo que obtiene si primero realiza errores tipográficos en los elementos de la cadena del núcleo. preimagen.
3. Luego, más tarde, cuando desee ver si “cuarto de galón” coincide con algo en su diccionario, aplica las mismas (número constante de) funciones de varios a uno y realiza búsquedas rápidas de hash en las salidas.

Debe hacer que las funciones de muchos a uno sean “liberales” y asignar muchas cosas al mismo núcleo, porque siempre puede tirar coincidencias que son demasiado liberales una vez que saca la palabra del diccionario de la tabla hash por su núcleo . Simplemente agrega una etapa adicional que utiliza un algoritmo de puntuación de similitud más fino (por ejemplo, Levenshtein) en el pequeño conjunto de resultados.

Debe usar una combinación de un árbol de prefijos ( http://en.wikipedia.org/wiki/Aho …) y alguna modificación de la distancia de edición para la coincidencia de texto. Para obtener más detalles sobre cómo hacerlo, consulte http: //www-tsujii.is.su-tokyo.a… .