Desejo criar um algoritmo de busca difusa. No entanto, após horas de pesquisa, estou realmente lutando.

Quero criar um algoritmo que realize uma pesquisa difusa em uma lista de nomes de escolas.

Isto é o que eu olhei até agora:

A maioria das minhas pesquisas continua apontando para "métricas de cadeia"no Google e Stackoverflow, como:

Distância LevenshteinDistância Damerau-LevenshteinAlgoritmo de Needleman – Wunsch

No entanto, isso apenas fornece uma pontuação de comosemelhante 2 cordas são. A única maneira de pensar em implementá-lo como umalgoritmo de busca é executar uma pesquisa linear e executar o algoritmo de métrica de sequência para cada sequência e retornar as sequências com pontuações acima de um determinado limite. (Originalmente, eu tinha minhas cordas armazenadas em uma árvore trie, mas isso obviamente não vai me ajudar aqui!)

Embora essa não seja uma má idéia para listas pequenas, seria problemático para listas com digamos 100.000 nomes, e o usuário realizou muitas consultas.

Outro algoritmo que olhei é oMétodo do corretor ortográfico, onde você acaba de pesquisar todos os erros de ortografia em potencial. No entanto, isso também é altamente ineficiente, pois requer mais de 75.000 palavras para uma palavra de comprimento 7 e contagem de erros de apenas 2.

O que eu preciso?

Alguém pode me sugerir umbom algoritmo de busca difusa eficiente. com:

Nome do algoritmoComo funciona ou um link para como funcionaPrós e contras e quando é melhor usado (opcional)

Eu entendo que todos os algoritmos terão seus prós e contras e não hámelhor algoritmo.