Algoritmo para comparar palabras (no alfabéticamente)

Question

Necesito codificar una solución para un cierto requisito, y quería saber si alguien está familiarizado con una biblioteca disponible en el mercado que puede lograrlo, o puede dirigirme a la mejor práctica. Descripción:

El usuario ingresa una palabra que se supone que es una de varias opciones fijas (tengo las opciones en una lista). Sé que la entrada debe estar en un miembro de la lista, pero dado que es una entrada del usuario, es posible que haya cometido un error. Estoy buscando un algoritmo que me diga cuál es la palabra más probable que el usuario quiso decir. No tengo ningún contexto y no puedo forzar al usuario a elegir de una lista (es decir, debe poder ingresar la palabra libre y manualmente).

Por ejemplo, supongamos que la lista contiene las palabras "agua", "cuarto", "cerveza", "remolacha", "infierno", "hola" y "aardvark".

La solución debe tener en cuenta diferentes tipos de errores "normales":

• errores tipográficos velocidad (por ejemplo doblando caracteres, dejando caer caracteres, etc)
• teclado caracteres adyacente errores tipográficos (por ejemplo, "Qater" para “agua “)
• errores tipográficos no nativos de inglés (por ejemplo, "quater" para‘cuarto’)
• Y así sucesivamente ...

La solución obvia es comparar letra por letra y dar "pesos de penalización" a cada letra diferente, letra extra y letra faltante. Pero esta solución ignora miles de errores "estándar" que estoy seguro que figuran en alguna parte. Estoy seguro de que hay heurísticas que se ocupan de todos los casos, tanto específicos como generales, probablemente usando una gran base de datos de desajustes estándar (estoy abierto a soluciones de datos pesados).

Estoy codificando en Python, pero considero que esta pregunta es independiente del idioma.

¿Alguna recomendación/idea?

Answer 1

desea leer cómo Google hace esto: http://norvig.com/spell-correct.html

Editar: Algunas personas han mencionado algoritmos que definen una métrica entre una palabra dada de usuario y una palabra candidato (levenshtein, soundex). Sin embargo, esta no es una solución completa al problema, ya que también se necesitaría una estructura de datos para realizar de manera eficiente una búsqueda de vecinos no euclidianos más cercanos. Esto se puede hacer, p. con el árbol de portada: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

Answer 2

¿Ha considerado algoritmos que se comparan por sonidos fonéticos, como soundex? No debería ser demasiado difícil producir representaciones de un solo dígito de su lista de palabras, almacenarlas, y luego obtener un índice de respuesta del usuario y encontrar la coincidencia más cercana allí.

Answer 3

Una solución común es calcular el Levenshtein distance entre la entrada y sus textos fijos. La distancia de dos cadenas de Levenshtein es simplemente el número de operaciones simples (inserciones, eliminaciones y sustituciones de un solo carácter) necesarias para convertir una cadena en la otra.

Answer 4

Aunque puede que no resuelva el problema completo, es posible que desee considerar el uso del algoritmo soundex como parte de la solución. Una búsqueda rápida en Google de "soundex" y "python" mostró algunas implementaciones de Python del algoritmo.

Answer 5

Intente buscar "Distancia Levenshtein" o "editar distancia".Cuenta el número de operaciones de edición (eliminar, insertar, cambiar letra) que necesita para transformar una palabra en otra. Es un algoritmo común, pero dependiendo del problema es posible que necesite algo especial con diferentes pesos para los diferentes tipos de errores tipográficos.

Answer 6

Busque el algoritmo Bitap. Califica bien para lo que quieres hacer, e incluso viene con un ejemplo de código fuente en Wikipedia.

Answer 7

Si su conjunto de datos es realmente pequeño, basta con comparar la distancia Levenshtein en todos los elementos de forma independiente. Sin embargo, si es más grande, deberá usar un BK-Tree o un sistema de indexación similar. El artículo que relacioné describe cómo encontrar coincidencias dentro de una distancia dada de Levenshtein, pero es bastante sencillo adaptarse para realizar búsquedas en el vecino más cercano (y se deja como ejercicio para el lector;).