Calculando a distância de Levenshtein rapidamente

24

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.

Joshua Herman
fonte

Respostas:

16

O que você está perguntando é o problema da pesquisa por vizinhos próximos na distância de edição. Você não mencionou se está interessado em resultados teóricos ou heurísticos, então responderei ao primeiro.

A distância de edição é um tanto desagradável para a construção de estruturas de pesquisa próximas. O principal problema é que, como uma métrica, ela se comporta (mais ou menos) como outras métricas ruins conhecidas como para fins de redução e aproximação da dimensionalidade. Há um vasto corpo de trabalho para ler sobre esse tópico, e sua melhor fonte é o conjunto de documentos de Alex Andoni : seguindo os ponteiros do contrário (por exemplo, no artigo do FOCS 2010), você obterá um bom conjunto de fontes.1 1

Suresh Venkat
fonte
11
Tudo o que sei sobre espaços métricos é da semântica, então uma pergunta: existe alguma incorporação decente (por qualquer valor decente) da métrica de Levenshtein em uma ultramétrica? Imediatamente, isso pode dar origem ao algoritmo binário-árvore-ish.
Neel Krishnaswami
Não tenho muita certeza. Suspeito que a resposta seja não em geral, mas não tenho nada a apontar.
Suresh Venkat
O segundo artigo sobre boytsov.info/pubs é uma boa pesquisa de possíveis soluções para busca por vizinhos próximos, nas distâncias de edição de Levenshtein e Damereau-Levenshtein.
a3nm
@NeelKrishnaswami Uma incorporação em um ultramétrico teria distorção pelo menos onde d é o comprimento da string. Isto resulta de uma distorção limite inferior para a incorporação em L 1 devido a Krauthgamer e Rabani , desde ultrametrics incorporar isometricamente para o espaço euclidiano, que incorpora isometricamente em L 1 . Ω(registrod)deu1 1eu1 1
Sasho Nikolov
5

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.

luispedro
fonte
11
Você deveria ter incluído um link para o seu arquivo de pesquisa reproduzível do artigo .
Dan D.
4

O(mk+1 1σk)mσk

Jouni Sirén
fonte
4

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.

Sasho Nikolov
fonte
3

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.

Björn Lindqvist
fonte
2

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.

Pratik Deoghare
fonte
Eu não entendo essa resposta. A pergunta pergunta como é possível encontrar com eficiência uma palavra em um dicionário grande, com uma distância próxima de Levenshtein a uma determinada entrada, não sobre como calcular a distância de Levenshtein ou sobre a comparação com a saída de um verificador ortográfico de caixa preta ...
Huck Bennett
@ Huck Bennett: Eu pensei que @Grigory Javadyan está construindo um 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. :)
Pratik Deoghare
Acho que suas idéias são boas, mas parece que Grigory está pedindo algo mais profundo e mais específico.
Huck Bennett
@ Huck Bennett: Sim, você está certo! :)
Pratik Deoghare
-1

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:

  1. procedimento de treinamento = descida do gradiente estocástico com gradientes adaptativos
  2. função de perda = erro quadrado médio entre a distância de edição verdadeira e a distância euclidiana
  3. dados de treinamento = seqüências aleatórias entre 1 e 32 caracteres (podem ser aprimoradas com dados que correspondem a uma distribuição real de erros de digitação comuns)
  4. resultados quantitativos: após o treinamento de aproximadamente 150 épocas com um tamanho de lote de 2048 (tempo de parede = aproximadamente um minuto), usando combinações de palavras de 512 dimensões, com uma camada oculta, o erro absoluto médio entre a distância de edição verdadeira e a distância de edição prevista fica em torno de 0,75, o que significa que a distância de edição prevista é de aproximadamente um caractere

Resumo da estrutura do modelo:

  1. Crie uma incorporação aprendida para cada caractere, incluindo o caractere nulo (usado posteriormente para colocar o texto à direita sob o limite de caracteres)
  2. Coloque o lado direito do texto com o caractere nulo até chegar ao limite de caracteres (32)
  3. Concatene esses incorporamentos
  4. Execute os incorporamentos por meio de uma rede neural de feed-forward para produzir uma incorporação de palavras com dimensões inferiores (512 dimensões)
  5. Faça isso para as duas palavras
  6. Encontre a distância euclidiana entre os vetores
  7. Defina a perda como o erro quadrático médio entre a distância real de Levenshtein e a distância euclidiana

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/wordsporque geralmente está disponível.

michaelsnowden
fonte
2
Como você treina um modelo de ML para que as palavras próximas a Levenshtein sejam mapeadas para vetores semelhantes? Que procedimento de treinamento e função de perda você usa para isso? Você pode resumir o método em sua resposta, para que a resposta ainda seja útil, mesmo que o link pare de funcionar, e para que não tenhamos que vasculhar seu bloco de anotações para entender o método que você está usando? Além disso, você pode avaliar o quão bem ele funciona de alguma maneira quantitativa? Isso é melhor do que as alternativas?
DW
Tal como está, acho que é um ajuste inadequado para o CSTheory. Ou seja, nenhuma idéia do que é especificamente sugerido e nenhuma justificativa teórica para isso.
Clement c
@ DW Desculpe por isso - eu fiz uma edição bastante substancial, que deve ser abrangente, caso o link seja desativado (ou caso você não queira procurar no notebook). Embora essa não seja realmente a teoria do CS, porque não é pesquisa, acho que é uma abordagem prática, porque é rápida e fácil para treinamento e inferência.
22818 michaelsnowden
11
Você está treinando em seqüências aleatórias. A distância esperada de Levenshtein entre duas dessas cordas será aproximadamente o comprimento da corda mais longa. Portanto, é muito fácil estimar essa distância em seqüências aleatórias, mas isso não é útil para lidar com dados do mundo real. Suspeito que seus casamentos possam apenas codificar o comprimento da corda e, portanto, você pode ter construído uma maneira elegante de fazer algo trivial e inútil. Este é um problema com o uso de ML; é muito sensível à função de perda que você usa.
DW
@DW Se você olhar para os resultados no notebook, a recuperação acabou retornando resultados decentes - não apenas seqüências do mesmo comprimento. Eu realmente encorajo você a dar uma olhada. Eu não chamaria isso de trivial e inútil.
michaelsnowden