string - moore - Algoritmo de búsqueda difusa(algoritmo de coincidencia aproximado de cadenas)

distancia entre cadenas

Question

Deseo crear un algoritmo de búsqueda difusa. Sin embargo, después de horas de investigación, realmente estoy luchando.

Quiero crear un algoritmo que realiza una búsqueda difusa en una lista de nombres de escuelas.

Esto es lo que he visto hasta ahora:

La mayor parte de mi investigación sigue apuntando a " métricas de cadenas " en Google y Stackoverflow, como:

• Distancia Levenshtein
• Distancia Damerau-Levenshtein
• Algoritmo Needleman-Wunsch

Sin embargo, esto solo da una puntuación de cuán similares son 2 cadenas. La única forma en que puedo pensar en implementarlo como algoritmo de búsqueda es realizar una búsqueda lineal y ejecutar el algoritmo de métrica de cadena para cada cadena y devolver las cadenas con puntajes por encima de un cierto umbral. (Originalmente tenía mis cadenas almacenadas en un árbol trie, ¡pero obviamente esto no me ayudará aquí!)

Aunque esta no es una mala idea para las listas pequeñas, sería problemático para las listas con digamos 100.000 nombres, y el usuario realizó muchas consultas.

Otro algoritmo que examiné es el método del corrector ortográfico , en el que solo hace una búsqueda de todos los posibles errores ortográficos. Sin embargo, esto también es muy ineficiente ya que requiere más de 75,000 palabras para una palabra de longitud 7 y un conteo de errores de solo 2.

¿Lo que necesito?

¿Puede alguien sugerirme un buen algoritmo de búsqueda difusa eficiente ? con:

• Nombre del algoritmo
• Cómo funciona o un enlace a cómo funciona
• Pro y contras y cuando se usa mejor (opcional)

Entiendo que todos los algoritmos tendrán sus pros y sus contras y que no existe el mejor algoritmo.

Answer 1

Escribí un artículo sobre cómo implementé una búsqueda difusa:

https://medium.com/@Srekel/implementing-a-fuzzy-search-algorithm-for-the-debuginator-cacc349e6c55

La implementación está en Github y es de dominio público, así que no dude en echar un vistazo.

https://github.com/Srekel/the-debuginator/blob/master/the_debuginator.h#L1856

Lo básico es: divide todas las cadenas que estarás buscando en partes. Entonces, si tiene rutas, entonces "C: / documents / lol.txt" es tal vez "C", "documentos", "lol", "txt".

Asegúrese de escribir en minúscula estas cadenas para asegurarse de que no distingue entre mayúsculas y minúsculas. (Tal vez solo lo haga si la cadena de búsqueda está en minúsculas).

Luego, haga coincidir su cadena de búsqueda con esto. En mi caso, quiero hacer coincidirlo independientemente del orden, por lo que "loldoc" aún coincidiría con el camino anterior, aunque "lol" viene después de "doc".

El emparejamiento necesita tener algo de puntuación para ser bueno. La parte más importante, creo, es la coincidencia consecutiva , por lo que cuantos más personajes directamente uno detrás del otro coinciden, mejor. Entonces "doc" es mejor que "dcm".

Entonces es probable que desee dar puntaje extra para un partido que está al comienzo de una parte. Entonces obtienes más puntos por "doc" que por "ocu".

En mi caso, también doy más puntos por igualar el final de una parte.

Y, por último, es posible que desee considerar la posibilidad de otorgar puntos adicionales por coincidir con la (s) última (s) parte (s). Esto hace que coincida el puntaje de archivo / puntaje más alto que las carpetas que lo conducen.

Answer 2

Está confundiendo los algoritmos de búsqueda difusa con la implementación: una búsqueda difusa de una palabra puede devolver 400 resultados de todas las palabras que tienen una distancia Levenshtein de, digamos, 2. Pero, para el usuario, debe mostrar solo los primeros 5-10.

En lo que respecta a la implementación, preprocesará todas las palabras del diccionario y guardará los resultados en un DB. Las palabras populares (y sus me gusta difusas) se guardarán en la capa de caché, por lo que no tendrá que pulsar la base de datos para cada solicitud.

Puede agregar una capa de AI que agregará los errores de ortografía más comunes y los agregará a la base de datos. Y etc.

Answer 3

Teniendo en cuenta que estás tratando de hacer una búsqueda difusa en una lista de nombres de escuelas, no creo que quieras ir por la similitud tradicional de las cuerdas, como la distancia de Levenshtein. Mi suposición es que está tomando la entrada de un usuario (ya sea por entrada de teclado o por teléfono), y desea encontrar rápidamente la escuela correspondiente.

Las métricas de distancia le dicen cuán similares son dos cadenas basadas en sustituciones, eliminaciones e inserciones. Pero esos algoritmos realmente no le dicen nada acerca de cuán similares son las cadenas como palabras en un lenguaje humano.

Considere, por ejemplo, las palabras "smith", "smythe" y "smote". Puedo pasar de "smythe" a "smith" en dos pasos:

smythe -> smithe -> smith

Y de "golpear" a "herrero" en dos pasos:

smote -> smite -> smith

Entonces los dos tienen la misma distancia que las cuerdas , pero como palabras , son significativamente diferentes. Si alguien le dijera (en un lenguaje hablado) que estaba buscando "Symthe College", casi seguramente diría: "Oh, creo que se refiere a Smith". Pero si alguien dijera "Smote College", no sabría de qué estaba hablando.

Lo que necesitas es un algoritmo fonético como Soundex o Metaphone . Básicamente, esos algoritmos dividen una palabra en fonemas y crean una representación de cómo se pronuncia la palabra en el lenguaje hablado. Luego puede comparar el resultado con una lista conocida de palabras para encontrar una coincidencia.

Tal sistema sería mucho más rápido que usar una métrica de distancia. Considere que con una métrica de distancia, necesita comparar la entrada del usuario con cada palabra de su lista para obtener la distancia. Eso es computacionalmente costoso y los resultados, como demostré con "smith" y "smote", pueden ser ridículamente malos.

Usando un algoritmo fonético, crea la representación de fonemas de cada una de sus palabras conocidas y la coloca en un diccionario (un hash map o posiblemente un trie). Ese es un costo inicial de una sola vez. Luego, cada vez que el usuario ingresa un término de búsqueda, usted crea la representación del fonema de su entrada y la busca en su diccionario. Eso es mucho más rápido y produce resultados mucho mejores.

Considere también que cuando las personas escriben mal los nombres propios, casi siempre obtienen la primera letra correcta, y la mayoría de las veces pronunciar el error ortográfico suena como la palabra real que intentaron deletrear. Si ese es el caso, entonces los algoritmos fonéticos definitivamente son el camino a seguir.