¿Cuál es el mejor algoritmo para la palabra más cercana.¿Cuál es el mejor algoritmo para la palabra más cercana
diccionario de palabras posibles se da y primeros caracteres de la palabra de entrada puede estar equivocada.
Una opción es BK-árboles -. Vea mi blog sobre ellos here. Otra opción más rápida pero más compleja es Levenshtein Automata, sobre la que también he escrito, here.
Estoy usando Hunspell, y devuelve 10 resultados como "hoyo", "hola", "ayuda", "héroe", etc. cuando ingreso "helo". Solo espero "hola", algo que Google hace cuando busco "helo". Ahora bien, ¿esto se basa también en datos estadísticos, o simplemente la distancia de edición puede ser suficiente para sugerir solo "hola"? – SexyBeast
Hay herramientas como HunSpell (corrector ortográfico de código abierto que incluye ampliamente a OpenOffice) que han abordado el problema desde múltiples perspectivas. Un criterio ampliamente utilizado para decidir qué tan cerca están las palabras es Levenshtein distance que también se utiliza en HunSpell.
Usted podría utilizar BLAST
y modificarlo para utilizar el hecho de que palabras en un diccionario son unidades discretas que hace que el proceso de hacer coincidir más específica a diferencia de una cadena larga de ADN.
BLAST ya ha construido en él la idea de editar distancias.
Como alternativa, puede utilizar sufijo árboles (Dan Gusfeld tiene un excelente libro sobre algoritmos básicos cadena coincidente) y construir en la idea de editar distancias en
¿Por qué sólo los primeros caracteres pueden estar equivocados? – Leonid
¿Podría dar primero su definición de "más cercano"? – FrustratedWithFormsDesigner
Me refiero a que los primeros caracteres pueden estar equivocados. – Avinash