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

Quiero crear un algoritmo que realice 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étrica de cadena"en Google y Stackoverflow como:

Distancia de LevenshteinDistancia Damerau-LevenshteinAlgoritmo de Needleman-Wunsch

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

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

Otro algoritmo que miré es elMétodo de corrector ortográfico, donde solo haces una búsqueda de todos los errores ortográficos potenciales. 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?

¿Alguien puede sugerirme unbuen algoritmo de búsqueda difusa eficiente. con:

Nombre del algoritmo.Cómo funciona o un enlace a cómo funcionaPros y contras y cuándo se usa mejor (opcional)

Entiendo que todos los algoritmos tendrán sus pros y sus contras y no haymejor algoritmo.