performance - Estructura de datos eficiente para búsqueda de palabras con comodines

algorithm data-structures

Question

Necesito hacer coincidir una serie de palabras ingresadas por el usuario con un gran diccionario de palabras (para asegurar que el valor ingresado).

Así que si el usuario introduce:

"orange" it should match an entry "orange'' in the dictionary.

Ahora el problema es que el usuario también puede ingresar un comodín o una serie de caracteres comodín como, por ejemplo,

"or__ge" which would also match "orange"

Los requisitos clave son:

* this should be as fast as possible.

* use the smallest amount of memory to achieve it.  

Si el tamaño de la lista de palabras fuera pequeño, podría usar una cadena que contenga todas las palabras y usar expresiones regulares.

sin embargo, dado que la lista de palabras podría contener potencialmente cientos de miles de entías, asumo que esto no funcionaría.

Entonces, ¿algún tipo de ''árbol'' será el camino a seguir para esto ...?

Cualquier pensamiento o sugerencia sobre esto sería totalmente apreciado!

Gracias de antemano, Matt

Answer 1

Coloque su lista de palabras en un DAWG (gráfico de palabras acíclicas dirigidas) como se describe en el documento de Appel y Jacobsen sobre el Programa de Scrabble más rápido del mundo ( copia gratuita en Columbia). Para su búsqueda, recorrerá este gráfico manteniendo un conjunto de indicadores: en una letra, realiza una transición determinista a los niños con esa letra; en un comodín, agrega todos los hijos al conjunto.

La eficiencia será aproximadamente la misma que la interpretación de Thompson de la NFA para grep (son el mismo algoritmo). La estructura de DAWG es extremadamente eficiente en espacio, mucho más que solo almacenar las palabras por sí mismas. Y es fácil de implementar.

El costo en el peor de los casos será el tamaño del alfabeto (26?) Elevado a la potencia del número de comodines. Pero a menos que su consulta comience con N comodines, una simple búsqueda de izquierda a derecha funcionará bien en la práctica. Yo sugeriría prohibir una consulta para comenzar con demasiados comodines, o crear múltiples dawgs, por ejemplo, dawg para la imagen reflejada, dawg para los tres caracteres girados a la izquierda, etc.

Emparejar una secuencia arbitraria de comodines, por ejemplo, ______ siempre va a ser costoso porque hay muchas soluciones combinatorias. El dawg enumerará todas las soluciones muy rápidamente.

Answer 2

Independientemente del algoritmo que elija, tiene un equilibrio entre la velocidad y el consumo de memoria.

Si puede pagar ~ O (N * L) de memoria (donde N es el tamaño de su diccionario y L es la longitud promedio de una palabra), puede probar este algoritmo muy rápido. Para simplificar, asumirá el alfabeto latino con 26 letras y MAX_LEN como la longitud máxima de la palabra.

Cree una matriz 2D de conjuntos de enteros, set<int> table[26][MAX_LEN].

Para cada palabra en su diccionario, agregue el índice de palabras a los conjuntos en las posiciones correspondientes a cada una de las letras de la palabra. Por ejemplo, si "naranja" es la palabra 12345-th en el diccionario, agrega 12345 a los conjuntos correspondientes a [o] [0], [r] [1], [a] [2], [n] [ 3], [g] [4], [e] [5].

Luego, para recuperar las palabras correspondientes a "or..ge", encontrará la intersección de los conjuntos en [o] [0], [r] [1], [g] [4], [e] [5].

Answer 3

Intente construir un árbol de sufijos generalizados si el diccionario coincidirá con la secuencia de consultas. Existe un algoritmo de tiempo lineal que se puede usar para construir dicho árbol ( Ukkonen Suffix Tree Construction ).

Puede hacer coincidir fácilmente (es O (k), donde k es el tamaño de la consulta) cruzando desde el nodo raíz, y usar el carácter comodín para coincidir con cualquier carácter como el patrón típico que se encuentra en el árbol de sufijos.

Answer 4

Primero probaría la solución de expresiones regulares y vería si es lo suficientemente rápida. ¡Puede que se sorprenda! :-)

Sin embargo, si eso no fuera lo suficientemente bueno, probablemente usaría un árbol de prefijos para esto.

La estructura básica es un árbol donde:

• Los nodos en el nivel superior son todas las primeras letras posibles (es decir, probablemente 26 nodos de az suponiendo que está utilizando un diccionario completo ...).
• El siguiente nivel hacia abajo contiene todas las segundas letras posibles para cada primera letra dada
• Y así hasta llegar a un marcador de "fin de palabra" para cada palabra

La prueba de si una cadena dada con comodines está contenida en su diccionario es simplemente un algoritmo recursivo simple en el que tiene una coincidencia directa para cada posición de carácter, o en el caso del comodín, verifica cada una de las posibles ramas.

En el peor de los casos (todos los caracteres comodín, pero solo una palabra con el número correcto de letras al final del diccionario), atravesará todo el árbol, pero esto es solo O (n) en el tamaño del diccionario, por lo que no es peor que un escaneo regex completo. En la mayoría de los casos, se necesitarían muy pocas operaciones para encontrar una coincidencia o confirmar que no existe tal coincidencia, ya que las ramas grandes del árbol de búsqueda se "recortan" con cada letra sucesiva.

Answer 5

Puedes probar una matriz de cuerdas:

0,1: A
1,5: APPLE
2,5: AXELS
3,5: EAGLE
4,5: HELLO
5,5: WORLD
6,6: ORANGE
7,8: LONGWORD
8,13:SUPERLONGWORD

Llamemos a esto una matriz de índice desigual, para ahorrar algo de memoria. Pídelo en longitud, y luego en orden alfabético. Para abordar un carácter, uso la notación x,y:z : x es el índice, y es la longitud de la entrada, z es la posición. La longitud de la cadena es f y g es el número de entradas en el diccionario.

• Cree la lista m , que contiene los posibles índices de coincidencia x .
• Iterar en z de 0 a f .
  • ¿Es un comodín y no el último carácter de la cadena de búsqueda?
    • Continuar bucle (todos coinciden).
  • ¿Está m vacío?
    • Busque en todas las x de 0 a g para y que coincida con la longitud. !!¡¡UNA!!
      • ¿ z carácter z con la cadena de búsqueda en esa z ? Guardar x en m .
    • ¿Está m vacío? Bucle de interrupción (no coincide).
  • ¿No estoy vacío?
    • Buscar a través de todos los elementos de m . !!¡¡SEGUNDO!!
      • ¿ No coincide con la búsqueda? Retirar de m .
    • ¿Está m vacío? Bucle de interrupción (no coincide).

Un comodín siempre pasará "¿Coincidir con la cadena de búsqueda?". Y m está igualmente ordenada como la matriz.

!! A !!: Búsqueda binaria en longitud de la cadena de búsqueda. O(log n)
!! B !!: Búsqueda binaria en orden alfabético. O(log n)

La razón para usar una matriz de cadenas es que ya almacenas la longitud de cada cadena (porque hace que la búsqueda sea más rápida), pero también te da la longitud de cada entrada (asumiendo otros campos constantes), de modo que puedas encontrarla fácilmente. La siguiente entrada en la matriz, para una rápida iteración. Ordenar la matriz no es un problema: ya que esto solo se hace una vez que se actualiza el diccionario y no durante el tiempo de búsqueda.

Answer 6

Si se le permite ignorar el caso, que asumo, entonces haga que todas las palabras en su diccionario y todos los términos de búsqueda sean el mismo caso antes que nada. Mayúsculas o minúsculas no hace ninguna diferencia. Si tiene algunas palabras que distinguen entre mayúsculas y minúsculas y otras que no lo son, divida las palabras en dos grupos y busque cada una por separado.

Solo se combinan palabras, por lo que puede dividir el diccionario en una serie de cadenas. Como solo está haciendo una coincidencia exacta con una longitud conocida, divida la matriz de palabras en una matriz separada para cada longitud de palabra. Entonces byLength [3] es la matriz de todas las palabras con longitud 3. Cada matriz de palabras debe ordenarse.

Ahora tiene una serie de palabras y una palabra con potenciales comodines para encontrar. Dependiendo de si y dónde están los comodines, hay algunos enfoques.

Si el término de búsqueda no tiene comodines, realice una búsqueda binaria en la matriz ordenada. Podrías hacer un hash en este punto, lo que sería más rápido pero no mucho. Si la gran mayoría de los términos de búsqueda no tienen comodines, considere una tabla hash o una matriz asociativa codificada por hash.

Si el término de búsqueda tiene caracteres comodín después de algunos caracteres literales, realice una búsqueda binaria en la matriz ordenada para encontrar un límite superior e inferior, luego realice una búsqueda lineal en ese límite. Si todos los comodines están al final, entonces es suficiente encontrar un rango no vacío.

Si el término de búsqueda comienza con caracteres comodín, entonces la matriz ordenada no es de ayuda y tendrá que hacer una búsqueda lineal a menos que mantenga una copia de la matriz ordenada por cadenas hacia atrás. Si crea una matriz de este tipo, entonces elíjala en cualquier momento que haya más pérdidas que los literales principales. Si no permite comodines iniciales, entonces no hay necesidad.

Si el término de búsqueda comienza y termina con comodines, entonces se queda atascado con una búsqueda lineal dentro de las palabras con la misma longitud.

Así que una serie de matrices de cadenas. Cada conjunto de cadenas está ordenado y contiene cadenas de igual longitud. Opcionalmente, duplique toda la estructura con la clasificación basada en cadenas hacia atrás para el caso de los principales comodines.

El espacio total es uno o dos punteros por palabra, más las palabras. Debería poder almacenar todas las palabras en un solo búfer si su idioma lo permite. Por supuesto, si su idioma no lo permite, grep es probablemente más rápido de todos modos. Para un millón de palabras, eso es 4-16MB para las matrices y similar para las palabras reales.

Para un término de búsqueda sin comodines, el rendimiento sería muy bueno. Con los comodines, ocasionalmente habrá búsquedas lineales en grandes grupos de palabras. Con el desglose por longitud y un solo personaje principal, nunca debería necesitar buscar más del pequeño porcentaje del diccionario, incluso en el peor de los casos. La comparación de palabras completas de longitud conocida siempre será más rápida que la concordancia genérica de cadenas.