¿Cómo detectar un error tipográfico en una búsqueda de un producto y sugerir posibles correcciones?

Question

Dada una gran base de datos de nombres de productos, ¿cómo detectaría posibles errores tipográficos en las búsquedas de los usuarios y sugerir posibles correcciones (algo así como la forma en que Google los presenta)?

E.g.

El usuario ingresa "fork handdels" y presiona "buscar".

que vuelvan

"No hay resultados. Quiso decir 'tenedor maneja'?"

Answer 1

Existen varios enfoques para este problema:

1. mantener una tabla de faltas de ortografía más populares en su base de datos. Si usted necesita algunas faltas de ortografía comunes: here)
2. utilizando un algoritmo basado en la edit distance: En teoría de la información y la informática, la distancia de edición entre dos cadenas de caracteres es el número de operaciones necesarias para transformar uno de ellos en el otro. Existen varios algoritmos diferentes para definir o calcular esta métrica. Lea el Wikipedia article for the Levenshtein algorithm por ejemplo.
3. Si está utilizando Lucene para búsqueda de texto completo, here is a nice article que muestra cómo implementar la función "¿Quiso decir?".
4. Si ve esa característica tan simple corrección ortográfica, aquí hay algunas buenas implementaciones, muy cortos en varios idiomas: How to Write a Spelling Corrector

Answer 2

Puede usar un phonetic algorithm, como Soundex para encontrar coincidencias que suenen similares.

PostgreSQL tiene un módulo llamado fuzzystrmatch, con los documentos que muestran ejemplos del uso de Soundex, Levenshtein, Metaphone y Double Metaphone.

Answer 3

Estoy seguro de que he leído que Google mantiene una lista de lo que un usuario vuelve a escribir cuando no obtienen ningún resultado. Podría mantener un mapeo de estos valores (por ejemplo, si la cadena re-escrita comienza con la misma letra).