language-agnostic - microsoft - natural language azure
Cómo corregir la entrada del usuario(tipo de google "¿quisiste decir?") (8)
Tengo el siguiente requisito:
Tengo muchos (digamos 1 millón) valores (nombres). El usuario tecleará una cadena de búsqueda.
No espero que el usuario deletree los nombres correctamente.
Entonces, quiero hacer que tipo 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 aquí . 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 deberían almacenarse los datos?
2) La segunda pregunta es la misma que esta . 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?
Encontré 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 al observar 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 señaló Kirk Broadhurst en una respuesta a continuación , hay dos escenarios posibles:
- Usuarios que escriben mal una palabra (un algoritmo de distancia de edición)
- Los usuarios no saben una palabra y adivinanza (un algoritmo de coincidencia fonética)
Estoy interesado en ambos. Son realmente dos cosas separadas; por ejemplo, Sean y Shawn suenan igual, pero tienen una distancia de edición de 3, demasiado alta para ser considerada un error tipográfico.
Consideraría usar una solución preexistente para esto.
Aspell con un diccionario personalizado de los nombres podría ser adecuado para esto. La generación del archivo de diccionario calculará previamente toda la información requerida para dar sugerencias rápidamente.
El algoritmo de Soundex puede ayudarlo con esto.
http://en.wikipedia.org/wiki/Soundex
Puede pregenerar los valores de soundex para cada nombre y almacenarlos en la base de datos, luego indexe eso para evitar tener que escanear la tabla.
Este es un viejo problema, DWIM (Do What I Mean), implementado de manera famosa en Xerox Alto por Warren Teitelman. Si su problema se basa en la pronunciación, aquí hay un documento de encuesta que podría ayudar:
J. Zobel y P. Dart, "Concordancia de cadenas fonéticas: lecciones de la recuperación de la información", Proc. 19th Annual Inter. ACM SIGIR Conf. sobre Investigación y Desarrollo en Recuperación de Información (SIGIR''96) , agosto de 1996, pp. 166-172.
Mis amigos que trabajan en la recuperación de información me dicen que Soundex, tal como lo describe Knuth, ahora se considera muy desactualizado.
Simplemente use Solr o un servidor de búsqueda similar, y luego 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 utilizará un RDBMS para este tipo de búsqueda, sino que dependerá de las bases de datos apenas leídas y de solo lectura destinadas para este fin. (Solr agrega una interfaz amigable de programación y configuración a un motor y base de datos Lucene subyacente). En el sitio web de la empresa para la que trabajo, un servicio nocturno selecciona registros alterados del SGBDR y los envía como documentos a 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 ortográficas en los resultados de búsqueda, así como la exploración con facetas como la que ve en 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 poblando el índice de Solr con la lista de nombres, y seleccionaría un algoritmo de coincidencia apropiado en el archivo de configuración.
Al igual que en una de las respuestas a la pregunta que hace referencia, la gran solución de Peter Norvig funcionaría para esto, completa con el código 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 el sufijo try . 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 tu 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 .
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 tirar la tuya, en lugar de usar Aspell u otra estructura de datos inteligente ... precalcular las posibles coincidencias es O (n ^ 2), en el caso ingenuo, pero sabemos para para nada, 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 la complejidad mucho (para en el caso práctico, algo así como O (30 ^ 2 * k ^ 2), donde k es << n).
Usted tiene dos posibles problemas que debe abordar (o no abordar si así lo desea)
- Usuarios que escriben mal una palabra (un algoritmo de distancia de edición)
- Los usuarios no saben una palabra y adivinanza (un algoritmo de coincidencia fonética)
¿Te interesan ambos, o solo uno o el otro? Son realmente dos cosas separadas; por ejemplo, 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 entro sith , podría esperar que me preguntaran si me refería a smith , sin embargo, si escribiera 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 probables .
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 la letra correcta, para instancia, luego descartar todo lo que no termina en la letra correcta, y así sucesivamente. Realmente 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 O (n), un algoritmo O (nlogn) y un O (n ^ 2) - realice los tres, en ese orden, para asegurarse de que solo está aplicando sus "buenos prospectos" a su algoritmo pesado .
el algoritmo Bitap está diseñado para encontrar una coincidencia aproximada en un cuerpo de texto. Tal vez podrías usar eso para calcular coincidencias probables. (se basa en la distancia de Levenshtein )
(Actualización: después de haber leído la respuesta de Ben S (usar una solución existente, posiblemente aspell ) es el camino a seguir)
Como dijeron otros, Google realiza la corrección automática al observar a los usuarios corregir ellos mismos. Si busco " someting " (sic) y luego de inmediato " something ", es muy probable que la primera consulta sea incorrecta. Una posible heurística para detectar esto sería:
- Si un usuario ha realizado dos búsquedas en una ventana de tiempo corto, y
- la primera consulta no arrojó ningún resultado (o el usuario no hizo clic en nada)
- la segunda consulta produjo resultados útiles
- las dos consultas son similares (tienen una pequeña distancia Levenshtein)
luego, la segunda consulta es un posible refinamiento de la primera consulta que puede almacenar y presentar a otros usuarios.
Tenga en cuenta que probablemente necesite muchas consultas para reunir datos suficientes para que estas sugerencias sean útiles.