Dado um enorme banco de dados de palavras permitidas (classificadas em ordem alfabética) e uma palavra, encontre a palavra no banco de dados mais próxima da palavra especificada em termos de distância de Levenshtein.
A abordagem ingênua é, é claro, simplesmente calcular a distância de levenshtein entre a palavra especificada e todas as palavras do dicionário (podemos fazer uma pesquisa binária no banco de dados antes de calcular as distâncias).
Gostaria de saber se existe uma solução mais eficiente para esse problema. Talvez alguma heurística que nos permita reduzir o número de palavras a serem pesquisadas ou otimizações para o algoritmo de distância de levenshtein.
Links para artigos sobre o assunto são bem-vindos.
fonte
Autômatos de Levenshtein: http://en.wikipedia.org/wiki/Levenshtein_automaton
Árvores BK: http://en.wikipedia.org/wiki/BK-tree
fonte
Se você tiver um pequeno número de edições incorretas que você tolerará, tente usar uma árvore de sufixos pontilhada . Isenção de responsabilidade: eu escrevi esse artigo, mas resolve o que você deseja: ele tem um alto custo de espaço em disco, mas as consultas são muito rápidas.
Em geral, é melhor analisar o contrário: você tem um índice de todas as palavras do dicionário. Agora, para uma palavra de entrada w, se estiver no dicionário, pare. Caso contrário, gere todas as variações na distância 1 e procure por elas. Se não estiverem lá, procure variações na distância 2 e assim por diante ...
Existem várias melhorias nessa idéia básica.
fonte
fonte
Escrevi uma resposta para uma pergunta muito semelhante em cs.stackexchange.com ( /cs//a/2096/1490 ) e, em seguida, encontrei essa pergunta. A resposta existe para a pesquisa de vizinhos próximos aproximados na distância de edição (ou seja, o algoritmo gera uma string que é aproximadamente tão próxima da string de consulta quanto o vizinho mais próximo da string de consulta). Estou postando aqui, pois não encontrei nenhuma das referências que dei nas respostas aqui.
fonte
Acho que o que você deseja é o algoritmo Wagner-Fischer: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm A principal conclusão é que, como o dicionário que você está percorrendo é classificado, duas palavras consecutivas é muito provável que compartilhem um prefixo longo, para que você não precise atualizar toda a matriz para cada cálculo de distância.
fonte
Você pode usar Você quis dizer?
E, em seguida, encontre a distância de Levenshtein entre a resposta retornada por "Você quis dizer" "e a string de entrada usando a Programação dinâmica.
fonte
Did you mean?
recurso. Além disso,Did you mean?
retorna a palavra que está muito próxima da entrada fornecida e a faz com bastante eficiência. :)Uma maneira é treinar um modelo de aprendizado de máquina para mapear as palavras em vetores e mapear a distância de Levenshtein à distância euclidiana. Em seguida, você pode criar um KDTree a partir dos vetores para o dicionário que você deseja usar. Criei um notebook jupyter que faz isso aqui: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03
Conforme comentários da DW:
Resumo da estrutura do modelo:
Meus dados de treinamento são apenas sequências aleatórias, mas acho que os resultados poderiam melhorar se os dados de treinamento fossem pares (erro de digitação / palavra correta). Acabei usando apenas
/usr/share/dict/words
porque geralmente está disponível.fonte