cómo corregir la entrada del usuario

Question

tengo el siguiente requisito (Clase de Google "Qué quieres decir?"): -

Tengo valores muchos (digamos 1 millón) (nombres). El usuario tecleará una cadena de búsqueda.

No espero que el usuario deletree los nombres correctamente.

Entonces, quiero hacer una especie de Google "¿Quiso decir?". Esto mostrará una lista de todos los valores posibles de mi almacén de datos. Hay una pregunta similar pero no la misma here. Esto no respondió mi pregunta.

Mi pregunta: - 1) Creo que no es recomendable almacenar esos datos en RDBMS. Porque entonces no tendré filtro en las consultas SQL. Y tengo que hacer un escaneo completo de la tabla. Entonces, en esta situación ¿cómo se deben almacenar los datos?

2) La segunda pregunta es la misma que this. Pero, solo por la totalidad de mi pregunta: ¿cómo busco en el gran conjunto de datos? Supongamos que hay un nombre Franky en el conjunto de datos. Si un usuario escribe como Phranky, ¿cómo hago coincidir el Franky? ¿Tengo que recorrer todos los nombres?

Me encontré con Levenshtein Distance, que será una buena técnica para encontrar las posibles cadenas. Pero nuevamente, mi pregunta es, ¿tengo que operar con todos los 1 millón de valores de mi almacén de datos?

3) Lo sé, Google lo hace observando el comportamiento de los usuarios. Pero quiero hacerlo sin observar el comportamiento del usuario, es decir, al usar, no sé todavía, decir algoritmos de distancia. ¡Porque el primer método requerirá un gran volumen de búsquedas para comenzar!

4) Como Kirk Broadhurst señaló en una respuesta below, hay dos escenarios posibles: -

• usuarios escribir mal una palabra (una edición algoritmo distancia)
• Los usuarios no saber una palabra y adivinar (un algoritmo de coincidencia fonética)

Me interesa los dos. Son realmente dos cosas separadas; p.ej. Sean y Shawn suenan igual, pero tienen una distancia de edición de 3, demasiado alta para ser considerada un error tipográfico.

Answer 1

El algoritmo de Soundex puede ayudarlo con esto.

http://en.wikipedia.org/wiki/Soundex

Se puede pre-generar los valores soundex para cada nombre y almacenarla en la base de datos, entonces el índice que para evitar tener que escanear la tabla.

Answer 2

Este es un viejo problema, DWIM (Haz lo que quiero decir), famoso implementado en el Xerox Alto por Warren Teitelman. Si su problema se basa en la pronunciación, aquí es un documento encuesta que podría ayudar:

J. Zobel y P. Dart, "fonético cadena coincidente: Lecciones de información Retieval," Proc. 19th Annual Inter. ACM SIGIR Conf. sobre Investigación y Desarrollo en Recuperación de Información (SIGIR'96), agosto de 1996, págs. 166-172.

Mis amigos que trabajan en la recuperación de información dicen que Soundex, según lo descrito por Knuth, ahora se considera muy desactualizado.

Answer 3

que sería considerar el uso de una solución pre-existente para esto.

Aspell con un custom dictionary de los nombres pueden ser adecuados para esto. La generación del archivo de diccionario calculará previamente toda la información requerida para dar sugerencias rápidamente.

Answer 4

la Bitap Algorithm está diseñado para encontrar una coincidencia aproximada en un cuerpo de texto. Tal vez podrías usar eso para calcular coincidencias probables. (Que se basa en la Levenshtein Distance)

(Actualización: Después de haber leído Ben Sanswer (use una solución existente, posiblemente aspell) es el camino a seguir)

---

Como otros han dicho, Google hace la corrección automática por viendo a los usuarios corregir ellos mismos. Si busco "someting" (sic) e inmediatamente después de "something" Es muy probable que la primera consulta fue incorrecta. Una posible heurística para detectar esto sería:

• Si un usuario ha hecho dos búsquedas en una ventana de tiempo corto, y
• la primera consulta no dió ningún resultado (o el usuario no haga clic en cualquier cosa)
• la segunda consulta dió resultados útiles
• las dos consultas son similares (tienen una pequeña distancia Levenshtein)

continuación, la segunda consulta es un posible perfeccionamiento de la primera consulta que puede almacenar y pre enviado a otros usuarios.

Tenga en cuenta que probablemente necesite un lote de consultas para recopilar datos suficientes para que estas sugerencias sean útiles.

Answer 5

Sólo tiene que utilizar Solr o un servidor de búsqueda similar, y entonces no tendrá que ser un experto en el tema. Con la lista de sugerencias de ortografía, ejecute una búsqueda con cada resultado sugerido, y si hay más resultados que la consulta de búsqueda actual, agréguelo como un resultado "¿Quiso decir?". (Esto evita sugerencias de ortografía falsas que en realidad no devuelven resultados más relevantes). De esta forma, no se requiere recopilar una gran cantidad de datos para realizar una oferta inicial de "¿quiso decir?", Aunque Solr tiene mecanismos por los cuales usted puede ajustar manualmente los resultados de ciertas consultas.

En general, no se estaría utilizando un RDBMS para este tipo de búsqueda, en lugar dependiendo de sólo lectura, bases de datos ligeramente rancio destinados a este fin. (Solr añade una interfaz de programación amigable y configuración de un motor subyacente Lucene y la base de datos.) En el sitio Web de la empresa para la que trabajo, un servicio nocturno selecciona registros alterados del RDBMS y las empuja como documentos en Solr. Con muy poco esfuerzo, tenemos un sistema donde el cuadro de búsqueda puede buscar productos, reseñas de clientes, páginas de sitios web y entradas de blog de manera muy eficiente y ofrecer sugerencias de ortografía en los resultados de búsqueda, así como la exploración con facetas como NewEgg, Netflix, o Home Depot, con muy poca tensión adicional en el servidor (especialmente el RDBMS). (Creo que tanto Zappo [el nuevo sitio] como Netflix usan Solr internamente, pero no me cites sobre eso.)

En su escenario, estaría llenando el índice de Solr con la lista de nombres, y seleccione un algoritmo de coincidencia apropiado en el archivo de configuración.

Answer 6

Al igual que en una de las respuestas a la pregunta que hace referencia, Peter Norvig's great solution funcionaría para esto, completo con el código de Python. Es probable que Google consulte la sugerencia de varias maneras, pero lo que les ofrece es mucha información. Claro que pueden seguir el comportamiento del usuario modelo con enormes registros de consulta, pero también pueden usar datos de texto para encontrar la ortografía correcta más probable para una palabra al observar qué corrección es más común. La palabra someting no aparece en un diccionario y, aunque es una falta de ortografía común, la ortografía correcta es mucho más común. Cuando encuentre palabras similares, querrá la palabra más cercana a la falta de ortografía y la más probable en el contexto dado.

La solución de Norvig es tomar un corpus de varios libros del Proyecto Gutenberg y contar las palabras que ocurren. A partir de esas palabras, crea un diccionario donde también se puede estimar la probabilidad de una palabra (COUNT(word)/COUNT(all words)). Si almacena todo esto como un hash directo, el acceso es rápido, pero el almacenamiento puede convertirse en un problema, por lo que también puede usar cosas como suffix tries. El tiempo de acceso sigue siendo el mismo (si lo implementa basado en un hash), pero los requisitos de almacenamiento pueden ser mucho menores.

A continuación, genera ediciones simples para la palabra mal escrita (eliminando, agregando o sustituyendo una letra) y luego limita la lista de posibilidades utilizando el diccionario del corpus. Esto se basa en la idea de distancia de edición (como la distancia de Levenshtein), con la heurística simple de que la mayoría de los errores de ortografía tienen lugar con una distancia de edición de 2 o menos. Puede ampliar esto según lo dicten sus necesidades y su poder computacional.

Una vez que tiene las palabras posibles, encuentra la palabra más probable del corpus y esa es su sugerencia. Hay muchas cosas que puede agregar para mejorar el modelo. Por ejemplo, también puede ajustar la probabilidad considerando la distancia del teclado de las letras en el error de ortografía. Por supuesto, eso supone que el usuario está usando un teclado QWERTY en inglés. Por ejemplo, la transposición de un e y un q es más probable que la transposición de un e y un l.

Answer 7

Para las personas que recomiendan Soundex, está muy desactualizado. Metaphone (más simple) o Double Metaphone (complejo) son mucho mejores. Si realmente se trata de datos de nombre, debería funcionar bien, si los nombres son de origen europeo o al menos fonéticos.

En cuanto a la búsqueda, si te interesa rodar la tuya, en lugar de utilizar Aspell u otra estructura de datos inteligente ... el cálculo previo de posibles coincidencias es O (n^2), en el caso ingenuo, pero saber para poder coincidir, tienen que tener una superposición de "fonemas", o incluso dos. Este paso previo a la indexación (que tiene una baja tasa de falsos positivos) puede reducir mucho la complejidad (en el caso práctico, algo como O (30^2 * k^2), donde k es < < n).

Answer 8

Tiene dos posibles problemas que usted necesita para hacer frente (o no abordar si así lo desea)

1. usuarios escribir mal una palabra (un algoritmo de distancia de edición)
2. Los usuarios no saber una palabra y adivinanzas (un algoritmo de coincidencia fonética)

¿Le interesan estos dos o solo uno u otro? Son realmente dos cosas separadas; p.ej. Sean y Shawn suenan igual, pero tienen una distancia de edición de 3, demasiado alta para ser considerada un error tipográfico.

Debe preindicar el recuento de palabras para asegurarse de que solo está sugiriendo respuestas relevantes (similar a la sugerencia de ealdent). Por ejemplo, si ingresé sith, podría esperar que me preguntaran si me refería a smith, sin embargo, si escribí smith, no tendría sentido sugerir sith. Determine un algoritmo que mida la probabilidad relativa de una palabra y solo sugiera palabras que sean más probable.

Mi experiencia en emparejamiento suelto reforzó un aprendizaje simple pero importante: realice tantas capas de indexado/tamizado como necesite y no tenga miedo de incluir más de 2 o 3. Elimine cualquier cosa que no comience con el la letra correcta, por ejemplo, luego descartar todo lo que no termina en la letra correcta, y así sucesivamente. En realidad, solo desea realizar cálculos de distancia de edición en el conjunto de datos más pequeño posible, ya que es una operación muy intensa.

Entonces, si tiene un algoritmo O (n), O (nlogn) y O (n^2) - realice los tres, en ese orden, para asegurarse de que solo está aplicando sus 'buenos prospectos' a tu algoritmo pesado