algorithm - teclado - como agregar palabras al diccionario del samsung j7
Algoritmo deseado: encuentre todas las palabras de un diccionario que sean similares a las palabras en un texto libre (4)
Eche un vistazo a http://norvig.com/spell-correct.html para obtener un algoritmo simple. El artículo usa Python, pero hay enlaces a implementaciones en otros idiomas al final.
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 en realidad 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
Es probable que desee utilizar un algoritmo que calcule la distancia Levenshtein .
Sin embargo, dado que su conjunto de datos es bastante grande, y estará comparando muchas palabras en su contra, una implementación directa de algoritmos típicos que lo hagan no será práctico.
Para encontrar palabras en un tiempo razonable, tendrá que indexar su conjunto de palabras de una manera que facilite la coincidencia de cadenas difusas .
Uno de estos métodos de indexación sería usar un árbol de sufijos . Otro enfoque sería usar n-grams .
Me inclino por usar un árbol de sufijos ya que me resulta más fácil abarcarlo y me parece más adecuado para el problema.
Puede ser de interés observar algunos algoritmos, como la distancia Levenshtein , 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. Aquí hay un ejemplo de código para la función levenshtein que levenshtein una palabra con un diccionario de palabras posibles y devuelve las palabras más cercanas.
¡Espero que esto te dé una idea de cómo una solución podría funcionar!
Harás bastantes búsquedas de palabras contra 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 pueden compartir un sufijo, pero obviamente no son errores ortográficos el uno del 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 deberían 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 una duración 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. Por ejemplo, el car convierte en "acr" ; rack 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 el rack tienen una diferencia de tamaño 1, el car y el hat tienen una diferencia de tamaño 2. Esto reduce aún más el conjunto de candidatos. Tenga en cuenta que para palabras más largas, puede rescatar temprano cuando haya encontrado demasiadas diferencias. Por ejemplo, una biography diferente tiene una diferencia total de 13, pero teniendo en cuenta la duración (8/9) probablemente puedas rescatar una vez que hayas 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 "palabras" 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, por g , gre , gre , gree , etc. Para cada prefijo que haya encontrado, verifique si el sufijo restante también está en la dicción, por ejemplo, reencar , eencar . Si las dos mitades de la palabra de entrada están en el diccionario, pero la palabra en sí no es, puede suponer que falta un espacio.