Algoritmo de pesquisa difusa (algoritmo de correspondência aproximada de texto)
quero criar um algoritmo que realize uma pesquisa difusa numa lista de nomes de escolas.
Foi isto que eu vi até agora.:
A maior parte da minha pesquisa continua a apontar para "string metrics " no Google e Stackoverflow como:
- distância Levenshtein
- Damerau-Levenshtein distância
- algoritmo Needleman-Wunsch
no entanto, isto apenas dá uma pontuação de como 2 cadeias de caracteres são similares. A única maneira de pensar em implementá-lo como um algoritmo de busca é realizar uma pesquisa linear e executar o algoritmo métrico string para cada string e devolver as strings com pontuações acima de um certo limiar. (Originalmente eu tinha minhas cordas armazenadas em uma árvore de trie, mas isso obviamente não vai me ajudar aqui!)
embora isto não é uma idéia tão ruim para listas pequenas, seria problemático para listas com digamos 100.000 nomes, e o usuário realizou muitas consultas.
outro algoritmo que eu vi é o método de Verificação Ortográfica , onde você apenas faz uma pesquisa para todas as potenciais grafias erradas. No entanto, isso também é altamente ineficiente, pois requer mais de 75.000 palavras para uma palavra de comprimento 7 e contagem de erro de apenas 2.
o que preciso?
Alguém pode sugerir - me um bom? algoritmo de pesquisa difusa eficiente . com:- nome do algoritmo
- Como funciona ou uma ligação ao seu funcionamento
- pró e contra e quando for melhor utilizado (opcional)
eu entendo que todos os algoritmos terão os seus prós e contras e não há nenhum algoritmo melhor .
4 answers
As métricas de distância dizem-lhe como duas cadeias semelhantes são baseadas em substituições, supressões e inserções. Mas esses algoritmos não te dizem qualquer coisa sobre como as cordas são parecidas como palavras numa linguagem humana.
Considere, por exemplo, as palavras "smith", "smythe" e "smote". Posso ir de "smythe" para "smith"em dois passos:
smythe -> smithe -> smith
smote -> smite -> smith
Então os dois têm a mesma distância que cadeias, mas como palavras, são significativamente diferentes. Se alguém lhe dissesse (língua falada) que ele estava à procura de "Symthe College", você quase certamente diga, " Oh, eu acho que você quer dizer Smith."Mas se alguém dissesse "feriu a faculdade", não fazia ideia do que ele estava a falar.
O que precisas é de um algoritmo fonético como Soundex ou Metafone . Basicamente, esses algoritmos dividem uma palavra em fonemas e criam uma representação de como a palavra é pronunciada na linguagem falada. Você pode então comparar o resultado com uma lista conhecida de palavras para encontrar uma correspondência.
Um tal sistema be much faster than using a distance metric. Considere que com uma métrica de distância, você precisa comparar a entrada do usuário com cada palavra em sua lista para obter a distância. Isso é computacionalmente caro e os resultados, como eu demonstrei com "smith" e "smote" podem ser ruins.Usando um algoritmo fonético, você cria a representação fonema de cada uma das suas palavras conhecidas e coloca-a num dicionário (um mapa de hash ou possivelmente uma trie). É um custo único de arranque. Então, sempre que o usuário introduz um termo de pesquisa, você cria a representação fonema de sua entrada e a procura em seu dicionário. Isso é muito mais rápido e produz resultados muito melhores.
Considere também que quando as pessoas escrevem mal os nomes próprios, elas quase sempre acertam a primeira letra, e mais frequentemente do que não pronunciando o erro de ortografia soa como a palavra real que estavam tentando soletrar. Se for esse o caso, então os algoritmos fonéticos são definitivamente o caminho para Vá.
Você está confundindo algoritmos de busca difusa com implementação: uma busca difusa de uma palavra pode retornar 400 resultados de todas as palavras que têm Levenshtein distância de, digamos, 2. Mas, para o usuário você tem que exibir apenas o top 5-10.
Em termos de implementação, processará todas as palavras do dicionário e guardará os resultados num DB. As palavras populares (e seus fuzzy-likes) serão salvos em cache-layer - assim você não terá que bater o DB para cada pedido.Adicionar uma camada de IA que irá adicionar os erros de ortografia mais comuns e adicioná-los ao DB. E etc.
Escrevi um artigo sobre como implementei uma pesquisa difusa:
Https://medium.com/@Srekel/implementing-a-fuzzy-search-algorithm-for-the-debuginator-cacc349e6c55
A implementação está no Github e é do domínio público, então sinta-se livre para dar uma olhada.
Https://github.com/Srekel/the-debuginator/blob/master/the_debuginator.h#L1856
O básico disso é: dividir todas as cordas que você vai procurar em partes. Então, se você tem caminhos, então ...C:\documents\lol.txt é talvez "C", "documents", "lol", "txt".
Certifique-se de que estas cadeias de caracteres são minúsculas para garantir que é insensível a maiúsculas. (Talvez só o faça se o texto de pesquisa for todo-minúsculo).
Depois, compare o seu texto de pesquisa com este. No meu caso, eu quero igualá-lo independentemente da ordem, então "loldoc" ainda iria igualar o caminho acima, mesmo que "lol" vem depois de "doc".
A correspondência precisa de alguma pontuação para ser boa. A parte mais importante que eu acho é uma correspondência consecutiva , por isso, quanto mais caracteres imediatamente a seguir um ao outro, melhor. Então " doc "é melhor que"dcm".Então provavelmente você vai querer dar pontuação extra para um jogo que está no Início de uma parte. Então, ganhas mais pontos por "doc"do que por "ocu".
No meu caso, também dou mais pontos para igualar o Final de uma parte.
E, finalmente, pode querer considerar dar pontos extra para igualar o último part(s). Isso faz com que a correspondência com o nome do arquivo/final pontuação mais alta do que as pastas que levam até ele.
Um algoritmo simples para "uma espécie de busca difusa"
Para ser honesto, em alguns casos, a busca difusa é principalmente inútil e eu acho que um algoritmo mais simples pode melhorar o resultado da busca, ao mesmo tempo que fornece a sensação de que ainda estamos realizando uma busca difusa.
Aqui está o meu caso de uso: a filtrar uma lista de Países usando a "pesquisa difusa" .
A lista com que trabalhava tinha dois países, a começar por Z: Zâmbia E Zimbabué.
Eu estava a usar Fusejs .Neste caso, ao introduzir a agulha "zam", o conjunto de resultados teve 19 resultados e o mais relevante para qualquer humano (Zâmbia) no final da lista. E a maioria dos outros países no resultado nem sequer tinha a letra z em seu nome.
Isto era para uma aplicação móvel onde se pode escolher um país de uma lista. Era suposto ser como quando se tem de escolher um contacto dos contactos do telefone. Poderá filtrar a lista de contactos se introduzir algum termo na caixa de busca. IMHO, este tipo de conteúdo limitado para procurar não deve ser tratado de uma forma que faça as pessoas perguntarem: "Que se lixe?!?". Pode-se sugerir que se separe pela combinação mais relevante. Mas isso está fora de questão neste caso, porque o usuário sempre terá que encontrar visualmente o "Item de interesse" na lista reduzida. Tenha em mente que isso é suposto ser uma ferramenta de filtragem, não um motor de busca "à la Google". Portanto, o resultado deve ser resolvido de uma forma previsível. E antes de filtrar a ordenação era alfabética. Então a lista filtrada deve ser apenas um subconjunto alfabeticamente ordenado da lista original. Então, inventei o seguinte algoritmo ...- agarra a agulha ... neste caso: zam
- inserir o .* padrão no início e no fim da agulha
- inserir o .* padrão entre cada letra da agulha
- faça uma busca regular no palheiro usando a nova agulha que é agora .*Z. * A.M.
Neste caso, o utilizador terá um resultado muito esperado ao encontrar tudo o que tem de alguma forma as letras z, A E m a aparecer nesta ordem. Todas as letras nas agulhas estarão presentes nos fósforos na mesma ordem.
Isto também irá corresponder a nomes de países como Mo zam bique ... o que é perfeito.
Só acho que, às vezes, não devemos tentar matar uma mosca com uma bazuca.