Algoritmo deseado: Encuentre todas las palabras de un diccionario que sean similares a las palabras en un texto libre

Question

Tenemos una lista de aproximadamente 150,000 palabras, y cuando el usuario ingresa un texto libre, el sistema debe presentar una lista de palabras del diccionario , que están muy cerca de las palabras en el texto libre.

Por ejemplo, el usuario escribe: "Me gustaría comprar juguetes de legoe en Walmart". Si el diccionario contiene "Lego", "Coche" y "Walmart", el sistema debe presentar "Lego" y "Walmart" en la lista. "Walmart" es obvio porque es idéntico a una palabra en la oración, pero "Lego" es lo suficientemente similar a "Legoe" como para mencionarlo también. Sin embargo, nada es similar a "Coche", por lo que esa palabra no se muestra.

Mostrar la lista debe ser en tiempo real, lo que significa que cuando el usuario ha ingresado la oración, la lista de palabras debe estar presente en la pantalla. ¿Alguien sabe un buen algoritmo para esto?

El diccionario realmente contiene conceptos que pueden incluir un espacio. Por ejemplo, "Lego spaceship". La solución perfecta también reconoce estos conceptos de palabras múltiples.

Cualquier sugerencia es apreciada.

Answer 1

Eche un vistazo a http://norvig.com/spell-correct.html para un algoritmo simple. El artículo usa Python, pero hay enlaces a implementaciones en otros idiomas al final.

Answer 2

Puede ser de interés observar algunos algoritmos como el Levenshtein distance, que puede calcular la cantidad de diferencia entre 2 cadenas.

No estoy seguro de qué idioma estás pensando usar pero PHP tiene una función llamada levenshtein que realiza este cálculo y devuelve la distancia. También hay una función llamada similar_text que hace algo similar. Hay un code example here para la función levenshtein que compara una palabra con un diccionario de palabras posibles y devuelve las palabras más cercanas.

¡Espero que esto le de una idea de cómo una solución podría funcionar!

Answer 3

Es probable que desee utilizar un algoritmo que calcule el Levenshtein distance.

Sin embargo, dado que su conjunto de datos es bastante grande, y va a comparar muchas palabras en su contra, una implementación directa de typical algorithms que lo haga no será práctica.

Para encontrar palabras en un tiempo razonable, tendrá que indexar su conjunto de palabras de alguna manera que facilite fuzzy string matching.

Uno de estos métodos de indexación sería utilizar un suffix tree. Otro enfoque sería usar n-grams.

Me inclino por el uso de un árbol de sufijo ya que me resulta más fácil rodearlo y me parece más adecuado para el problema.

Answer 4

Realizará bastantes búsquedas de palabras en un diccionario fijo. Por lo tanto, debes preparar tu diccionario. Lógicamente, puede eliminar rápidamente candidatos que son "simplemente demasiado diferentes".

Por ejemplo, las palabras car y dissimilar puede compartir un sufijo, pero son obviamente no faltas de ortografía de uno al otro. Ahora, ¿por qué es tan obvio para nosotros los humanos? Para empezar, la duración es completamente diferente.Eso es una descalificación inmediata (pero con una excepción, más abajo). Por lo tanto, su diccionario debe ordenarse por longitud de palabra. Haga coincidir su palabra de entrada con palabras de longitud similar. Para palabras cortas que significa +/- 1 carácter; las palabras más largas deben tener un margen más alto (¿exactamente qué tan bien puede su hechizo demográfico?)

Una vez que se haya restringido a palabras candidatas de longitud similar, le gustaría quitar palabras que son completamente diferentes. Con esto quiero decir que usan letras completamente diferentes. Esto es más fácil de comparar si ordena las letras alfabéticamente en una palabra. P.ej. car se convierte en "acr"; rack se convierte en "ackr". Lo hará en preprocesamiento para su diccionario y para cada palabra de entrada. La razón es que es barato determinar el (tamaño de una) diferencia de dos conjuntos ordenados. (Agregue un comentario si necesita una explicación). car y rack tienen una diferencia de tamaño 1, car y hat tienen una diferencia de tamaño 2. Esto reduce aún más su conjunto de candidatos. Tenga en cuenta que para palabras más largas, puede rescatar temprano cuando haya encontrado demasiadas diferencias. P.ej. dissimilar y biography tienen una diferencia total de 13, pero teniendo en cuenta la duración (8/9) probablemente pueda rescatar una vez que haya encontrado 5 diferencias.

Esto te deja con un conjunto de palabras candidatas que usan casi las mismas letras, y también tienen casi la misma longitud. En este punto puede comenzar a usar algoritmos más refinados; ya no necesita ejecutar 150,000 comparaciones por palabra de entrada.

Ahora, para la excepción de longitud mencionada anteriormente: El problema está en "words" como greencar. Realmente no coincide con una palabra de longitud 8, y sin embargo, para los humanos es bastante obvio lo que se quiso decir. En este caso, no puede realmente romper la palabra de entrada en cualquier límite aleatorio y ejecutar coincidencias N-1 inexactas adicionales contra ambas mitades. Sin embargo, es factible verificar solo por un espacio faltante. Solo haga una búsqueda de todos los prefijos posibles. Esto es eficiente porque usará la misma parte del diccionario una y otra vez, p. ggr, gre, gree, etc. Para cada prefijo que haya encontrado, verifique si el sufijo restante también está en la dicción, p. reencar, eencar. Si las dos mitades de la palabra de entrada están en el diccionario, pero la palabra en sí no es así, puede suponer que falta un espacio.