La creación de un "cheque de encanto" que comprueba contra una base de datos con un tiempo de ejecución razonable

No estoy pidiendo acerca de cómo implementar el algoritmo de corrección ortográfica en sí. Tengo una base de datos que contiene cientos de miles de registros. Lo que estoy buscando hacer es verificar la entrada de un usuario contra una cierta columna en una tabla para todos estos registros y devolver cualquier coincidencia con una cierta distancia cortada (de nuevo, esta pregunta no trata de determinar la distancia de corte, etc.). El objetivo, por supuesto, es crear una característica "¿quisiste decir?", Donde un usuario busca un nombre, y si no se encuentran coincidencias directas en la base de datos, se devuelve una lista de posibles coincidencias.La creación de un "cheque de encanto" que comprueba contra una base de datos con un tiempo de ejecución razonable

estoy tratando de llegar a una manera de hacer todas estas comprobaciones en el tiempo de ejecución más razonable posible. ¿Cómo puedo verificar la entrada de un usuario contra todos estos registros de la manera más eficiente posible?

La característica se implementa en la actualidad, pero el tiempo de ejecución es extremadamente lento. La forma en que funciona ahora es que carga todos los registros de una tabla (o tablas) especificada por el usuario en la memoria y luego realiza la comprobación.

Por lo que vale la pena, estoy usando NHibernate para acceso a datos.

Le agradecería cualquier información sobre cómo puedo hacer esto o cuáles son mis opciones.

Fuente

2011-01-28 Tyler Treat

Hmmm, buena pregunta! !! ';)' – jjnguy

La manera más fácil (dado que ya lo ha implementado) sería hacer lo que Conrad sugirió, y cargar la base de datos una vez cuando se carga el programa. En cuanto a golpear la base de datos más de una vez, realmente necesitaría ver la lógica detrás de sus sugerencias para encontrar la mejor manera de consultar su base de datos. – Rob

Si carga todos los registros DB en la memoria, ¿tiene que administrar la sincronización de los datos cuando cambia la base de datos o son datos estáticos? –

Calculando la distancia Levenshtein no tiene que ser tan costoso como usted podría pensar. El código en el Norvig article se puede considerar como código psuedo para ayudar al lector a entender el algoritmo. Una implementación mucho más eficiente (en mi caso, aproximadamente 300 veces más rápida en un conjunto de datos de 20,000 términos) es caminar un trie. La diferencia de rendimiento se atribuye principalmente a la eliminación de la necesidad de asignar millones de cadenas para realizar búsquedas en los diccionarios, pasar mucho menos tiempo en el GC y también obtener una mejor ubicación de referencia, por lo que hay menos errores en la memoria caché de la CPU. Con este enfoque, puedo realizar búsquedas en alrededor de 2 ms en mi servidor web. Una ventaja adicional es la capacidad de devolver todos los resultados que comienzan con la cadena proporcionada fácilmente.

La desventaja es que crear el trie es lento (puede tomar un segundo más o menos), por lo que si los datos de origen cambian regularmente, entonces debe decidir si desea reconstruir todo o aplicar deltas. En cualquier caso, desea reutilizar la estructura tanto como sea posible una vez que esté construida.

Fuente

2011-01-29 16:00:18

Consulte http://norvig.com/ngrams/ para una implementación (utilizando una tabla hash en lugar de una trie, en realidad, pero la idea es la misma). –

@Darius, esa página presenta un código que es bastante idéntico al otro artículo de Norvig del que estaba hablando, sin embargo, utiliza una búsqueda de tabla hash. Como dije, el código psuedo es similar, pero la implementación de un enfoque basado en trie es bastante diferente. El trie no solo se usa para probar la existencia de términos generados. En cambio, se camina de una manera que evita la necesidad de generar todos los términos con una distancia de edición de dos. –

Parece que solo ha robado ese código y ha tenido una impresión incorrecta. Norvig: "Si consideramos todas las ediciones, una palabra como" alojamientos "produciría 233.166 candidatos, pero solo 11 de ellos están en el vocabulario. Así que las modificaciones funcionan precomputando el conjunto de todos los prefijos de todas las palabras en el vocabulario. A continuación, llama editsR de forma recursiva, dividiendo la palabra en una cabecera y una cola (hd y tl en el código) y asegurando que la cabecera está siempre en la lista de prefijos ". Se derivó del código que le envié, derivado a su vez de mi http://wry.me/~darius/hacks/spelling.tar.gz que había usado un trie. –

carga todos los registros de una tabla especificada por el usuario (o tablas) en la memoria y realiza la comprobación

no hacen eso

De cualquier

Do la coincidencia de partido en la parte posterior y solo devuelve los resultados que necesita.

caché los registros en la memoria primeros toman en un conjunto de trabajo golpear y hacer el cheque cuando lo necesite.

Fuente

2011-01-28 22:52:35

Usted tendrá que estructurar los datos de manera diferente que una lata de base de datos. Cree un árbol de búsqueda personalizado, con todos los datos del diccionario necesarios, en el cliente. Aunque la memoria puede convertirse en un problema si el diccionario es extremadamente grande, la búsqueda en sí será muy rápida. O (nlogn) si no recuerdo mal.

Tener un vistazo a BK-Trees

Además, en lugar de utilizar la distancia de Hamming, considere la Levenshtein distance

Fuente

2011-01-28 23:37:27 Darcara

supongo que la Levenshtein distance es más útil aquí que la Hamming distance.

Tomemos un ejemplo: tomamos la palabra example y nos limitamos a una distancia de Levenshtein de 1.Entonces podemos enumerar todas las faltas de ortografía posibles que existen:

1 de inserción (208)
- aexample
- bexample
- cexample
- ...
- examplex
- exampley
- examplez
1 deleción (7)
- xample
- eample
- exmple
- ...
- exampl
1 sustitución (182)
- axample
- bxample
- cxample
- ...
- examplz

Se podría almacenar cada falta de ortografía en la base de datos, y vincular a que la ortografía correcta, example. Eso funciona y sería bastante rápido, pero crea una gran base de datos.

Aviso cómo la mayoría de las faltas de ortografía se producen al hacer la misma operación con un carácter diferente:???

1 de inserción (8)
- ejemplo
- e jemplo
- ex amplia
- exa? Mple
- examen
- ejemplo
- ejemplificado
- ejemplo?
1 deleción (7)
- xample
- eample
- exmple
- exaple
- examle
- exampe
- exampl
1 de sustitución (7)
- ? Xample
- e? Amplio
- ex? MPLE
- exa? PLE
- examen? Le
- examp? E
- exampl?

Eso parece bastante manejable. Puede generar todos estos "consejos" para cada palabra y almacenarlos en la base de datos. Cuando el usuario ingresa una palabra, genera todos los "consejos" y consulta la base de datos.

Ejemplo: El usuario introduce exaple (aviso falta m).

SELECT DISTINCT word 
      FROM dictionary 
      WHERE hint = '?exaple' 
      OR hint = 'e?xaple' 
      OR hint = 'ex?aple' 
      OR hint = 'exa?ple' 
      OR hint = 'exap?le' 
      OR hint = 'exapl?e' 
      OR hint = 'exaple?' 
      OR hint = 'xaple' 
      OR hint = 'eaple' 
      OR hint = 'exple' 
      OR hint = 'exale' 
      OR hint = 'exape' 
      OR hint = 'exapl' 
      OR hint = '?xaple' 
      OR hint = 'e?aple' 
      OR hint = 'ex?ple' 
      OR hint = 'exa?le' 
      OR hint = 'exap?e' 
      OR hint = 'exapl?'

exaple con 1 == == inserción exa?pleexample con 1 sustitución

Ver también: How does the Google “Did you mean?” Algorithm work?

Fuente

2011-01-28 23:52:12 dtb

+1 estuvo de acuerdo con la distancia de Levenshtein. Desafortunadamente, el artículo de Peter Norwig no aborda el problema de la memoria, es una compensación de la memoria frente a la velocidad de procesamiento. Dependiendo del tamaño, puede que no sea posible cargar el diccionario completo en la memoria. los errores ortográficos en el DB tampoco suenan bien. – BrokenGlass

@BrokenGlass, utilizando un trie puede reducir la huella de memoria para grandes conjuntos de datos. También mejora el rendimiento de búsqueda enormemente (200-300 veces más rápido en mi caso). –

Gracias Drew - Tendré que investigar eso - voté tu respuesta también – BrokenGlass

Como dijo Darcara, un BK-árbol es una buena primera toma. Son muy fáciles de implementar. Hay varias implementaciones gratuitas que se encuentran fácilmente a través de Google, pero se puede encontrar una mejor introducción al algoritmo aquí: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees.

Por desgracia, el cálculo de la distancia Levenshtein es bastante costoso, y que va a hacer que sea mucho más si estás usando un BK-árbol con un gran diccionario. Para un mejor rendimiento, puede considerar Levenshtein Automata. Un poco más difícil de implementar, pero también más eficiente, y se pueden usar para resolver su problema. El mismo blogger impresionante tiene los detalles: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata. Este documento también podría ser interesante: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.652.

Fuente

2011-01-29 06:08:04

No creo que me hayan llamado increíble antes. ;) –

La respuesta ha marcado como correcta ..

Note: when i say dictionary.. in this post, i mean hash map .. map.. 
basically i mean a python dictionary

Otra manera de mejorar su rendimiento mediante la creación de un índice invertido de palabras.

De modo que, en lugar de calcular la distancia de edición frente a db completa, se crean 26 diccionarios ... cada uno tiene una clave y un alfabeto. por lo que el idioma Inglés tiene 26 alfabetos .. por lo que las llaves son "a", "b" .. "z"

Así que se supone que tiene la palabra en su base de datos "manzana"

Así, en el "un" diccionario: se agrega la palabra "manzana"

en el diccionario "p": se agrega la palabra "manzana"

en el diccionario "l": se agrega la palabra "manzana"

en el " e "diccionario: agrega la palabra" manzana "

Por lo tanto, hacer esto para todas las palabras en el diccionario ..

Ahora, cuando se introduce la palabra mal escrita ..

digamos aplse

se comienza con "a" y retreive todas las palabras en "a"

continuación, se empieza con "p" y encontrar la intersección de palabras entre "a" y "p"

continuación, se empieza con "l" y encontrar la intersección de palabras entre "a" , "p" y "l"

y lo hace para todos los alfabetos.

al final va a tener sólo el montón de palabras que están hechas de alfabetos "a", "p", "L", "s", "e"

En el siguiente paso, se calcula la distancia de edición entre la palabra de entrada y el manojo de palabras devueltas por los pasos anteriores .. lo que reduce drásticamente el tiempo de ejecución ..

ahora puede haber un caso en que nada podría ser devuelto ..

por lo

algo como "aklse" ... hay muchas posibilidades de que no haya palabras que estén hechas de estos alfabetos. En este caso, tendrá que comenzar a invertir el paso anterior a una etapa en la que le quedan números finitos de palabra.

Así somethng como comienzo con * KLSE (intersección entre las palabras k, l, s, e) num (wordsreturned) = k1

luego un lse * (intersección entre las palabras A, L, s, e). .. numwords = k2

y así sucesivamente ... elija la que tenga mayor número de palabras devueltas ... en este caso, realmente no hay una respuesta ..como muchas palabras pueden tener la misma distancia de edición ... simplemente puede decir que si editdistance es mayor que "k" entonces no hay una buena coincidencia ...

Hay muchos sofisticados algoritmos construidos sobre este ..

como después de estos muchos pasos, utilice inferencia estadística (la probabilidad es la palabra "manzana" cuando la entrada es "aplse" .. y así sucesivamente) Luego vas máquina de manera aprendizaje :)

Fuente

2012-04-15 05:50:19 Fraz

¡Muy perspicaz, gracias! –

La creación de un "cheque de encanto" que comprueba contra una base de datos con un tiempo de ejecución razonable

Respuesta

Cuestiones relacionadas