A distância de Levenshtein é uma métrica que mede a diferença entre duas cadeias de caracteres ou, de forma mais geral, entre duas sequências finitas de símbolos. Na definição clássica, ela corresponde ao número mínimo de operações de inserção, deleção e substituição de um único símbolo necessárias para transformar uma sequência na outra, atribuindo-se custo 1 a cada operação.V. I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals”, Doklady Akademii Nauk SSSR, v. 163, n. 4, 1965, p. 845–848. Tradução inglesa em Soviet Physics Doklady, v. 10, n. 8, 1966, p. 707–710. Math-Net.
A distância recebeu esse nome em homenagem ao matemático soviético Vladimir Levenshtein, que a introduziu em 1965 no contexto da teoria de códigos corretores de erros. Ela é uma forma clássica de distância de edição. O termo “distância de edição” também é empregado em sentido mais amplo para famílias de medidas nas quais o conjunto de operações permitidas ou os seus custos são modificados.Gonzalo Navarro, “A guided tour to approximate string matching”, ACM Computing Surveys, v. 33, n. 1, 2001, p. 31–88. doi:10.1145/375360.375365.
A distância de Levenshtein é usada em tarefas como correção ortográfica, busca aproximada, comparação de nomes, relacionamento de registros, avaliação de reconhecimento de texto e comparação de sequências biológicas.
Definição
Sejam
e
duas sequências. Define-se como a distância de Levenshtein entre o prefixo e o prefixo .
As condições de contorno são
Para e ,
em que
Os três termos correspondem, respectivamente, à deleção de um símbolo da sequência de origem, à inserção de um símbolo da sequência de destino e à manutenção ou substituição do último símbolo dos dois prefixos.Robert A. Wagner e Michael J. Fischer, “The String-to-String Correction Problem”, Journal of the ACM, v. 21, n. 1, 1974, p. 168–173. doi:10.1145/321796.321811.
A distância entre as sequências completas é .
Exemplo
A distância de Levenshtein entre as palavras inglesas kitten e sitting é 3. Uma sequência ótima de operações é:
kitten → sitten — substituição de k por s; sitten → sittin — substituição de e por i; sittin → sitting — inserção de g no final.
Logo,
Um exemplo em português é casa → caso, cuja distância é 1, pois basta substituir a por o na última posição.
Propriedades e limites
Com custos unitários de inserção, deleção e substituição, a distância de Levenshtein é uma métrica: é não negativa, vale zero se e somente se as duas sequências são iguais, é simétrica e satisfaz a desigualdade triangular.
Para sequências de comprimentos e ,
O limite inferior decorre do fato de que uma única inserção ou deleção altera o comprimento em apenas uma unidade. O limite superior pode ser obtido substituindo os símbolos da parte comum e, em seguida, inserindo ou removendo os símbolos restantes.
Quando as duas sequências têm o mesmo comprimento, a distância de Hamming é um limite superior:
Se substituições não forem permitidas, e apenas inserções e deleções forem usadas, a distância de edição resultante entre sequências de comprimentos e é
em que é o comprimento de uma subsequência comum mais longa. Essa expressão não se aplica diretamente à distância de Levenshtein clássica, pois nela uma substituição custa 1, enquanto uma deleção seguida de uma inserção custa 2.
Cálculo
Programação dinâmica
O método clássico utiliza programação dinâmica. Uma matriz de tamanho armazena as distâncias entre todos os pares de prefixos.
função DistanciaLevenshtein(s[1..m], t[1..n]): criar d[0..m, 0..n]
para i de 0 até m: d[i,0] = i
para j de 0 até n: d[0,j] = j
para i de 1 até m: para j de 1 até n: se s[i] = t[j]: custo = 0 senão: custo = 1
d[i,j] = mínimo( d[i-1,j] + 1, // deleção de s[i] d[i,j-1] + 1, // inserção de t[j] d[i-1,j-1] + custo // igualdade ou substituição )
retornar d[m,n]
O algoritmo que preenche toda a matriz usa tempo e espaço .
Redução de memória
Quando se deseja apenas o valor da distância, cada linha da matriz depende apenas da linha anterior e da linha corrente. Assim, escolhendo a cadeia mais curta como dimensão armazenada, o espaço de trabalho pode ser reduzido para .Esko Ukkonen, “Algorithms for approximate string matching”, Information and Control, v. 64, n. 1–3, 1985, p. 100–118. doi:10.1016/S0019-9958(85)80046-2.
Reconstrução das operações
Se a matriz completa for mantida, é possível reconstruir uma sequência ótima de operações percorrendo-a de trás para a frente, a partir de . Mais de um predecessor pode produzir o mesmo valor mínimo; por isso, uma mesma distância pode corresponder a várias sequências ótimas de edição.
Algoritmos dependentes da distância
Quando a distância real é pequena em relação ao tamanho das sequências, nem sempre é necessário calcular a matriz inteira. Ukkonen apresentou algoritmos exatos cujo custo depende de , restringindo o cálculo a uma faixa relevante da matriz de programação dinâmica.
O termo “casamento aproximado de cadeias” nesse contexto significa permitir diferenças entre as cadeias, e não necessariamente calcular uma aproximação numérica da distância.
Métodos bit-paralelos
Myers propôs em 1999 um algoritmo baseado em vetores de bits para casamento aproximado de padrões, no qual diversos estados da programação dinâmica são representados nos bits de uma palavra de máquina e atualizados por operações bit a bit.Gene Myers, “A fast bit-vector algorithm for approximate string matching based on dynamic programming”, Journal of the ACM, v. 46, n. 3, 1999, p. 395–415. doi:10.1145/316542.316550.
Variantes e medidas relacionadas
Distância de edição ponderada
Em uma distância de edição ponderada, inserções, deleções e substituições podem receber custos diferentes, inclusive custos que dependem dos símbolos envolvidos. Uma escolha arbitrária de custos não preserva automaticamente todas as propriedades de uma métrica; por exemplo, custos assimétricos podem destruir a simetria.
A distância de Damerau–Levenshtein acrescenta a transposição de dois símbolos adjacentes ao conjunto de operações elementares.
Normalização e similaridade
A distância bruta tende a assumir valores maiores para palavras ou sequências mais longas. Por isso, diversas aplicações usam formas normalizadas. Não existe uma única definição universal de “distância de Levenshtein normalizada”.
Uma forma comum é
com valores entre 0 e 1. O complemento
pode ser usado como medida de similaridade.
Em estudos em língua portuguesa, a normalização pelo comprimento foi utilizada, por exemplo, para comparar a semelhança ortográfica entre palavras cognatas português–inglês.Maylton Silva Fernandes, Gustavo Lopez Estivalet e Márcio Martins Leitão, “Monolíngues? Uma investigação sobre o reconhecimento de palavras cognatas português-inglês”, Caligrama: Revista de Estudos Românicos, v. 26, n. 2, 2021, p. 155–177. doi:10.17851/2238-3824.26.2.155-177.
Aplicações
Correção ortográfica em português
A distância de edição é usada em sistemas de correção ortográfica para gerar ou ordenar candidatos semelhantes a uma palavra não reconhecida. Em um estudo brasileiro sobre desenvolvimento de corretores ortográficos, Araújo, Benevides e Sansão discutem explicitamente a distância de mínima edição, incluindo Levenshtein e Damerau–Levenshtein, e destacam que decisões de tokenização e tratamento de hífens, apóstrofos, maiúsculas, números e afixos dependem das características da língua e da aplicação.Leonardo Carneiro de Araújo, Aline de Lima Benevides e João Pedro H. Sansão, “Desenvolvimento de um corretor ortográfico”, Texto Livre, v. 14, n. 1, 2021, e26469. doi:10.35699/1983-3652.2021.26469.
Relacionamento de registros no Brasil
Uma aplicação particularmente frequente no Brasil é o relacionamento de registros de grandes bases administrativas e de saúde. Nesses sistemas, nomes podem conter abreviações, erros de digitação ou pequenas diferenças de grafia, tornando útil uma medida aproximada entre cadeias.
Em estudos brasileiros de saúde pública, algoritmos baseados na distância de Levenshtein foram empregados para comparar nomes completos e nomes de mães no relacionamento probabilístico de registros. Um estudo publicado nos Cadernos de Saúde Pública utilizou limiares distintos de similaridade para nome e nome da mãe em estratégias de linkage probabilístico.“Inclusão de etapa de pós-processamento determinístico para o aumento de performance do relacionamento (linkage) probabilístico”, Cadernos de Saúde Pública, v. 34, n. 6, 2018, e00088117. SciELO.
A distância de Levenshtein também foi usada em estudos de relacionamento entre bases de internação e mortalidade, em que o campo “nome completo” foi uma das variáveis do pareamento.“Acurácia do relacionamento probabilístico na avaliação da alta complexidade em cardiologia”, Revista de Saúde Pública, v. 45, n. 2, 2011. SciELO.
Esses exemplos também mostram uma limitação prática da distância: sem pré-processamento e regras adicionais, abreviações, omissões, inversões de componentes do nome e nomes compostos podem produzir escores pouco intuitivos. Por isso, sistemas de linkage costumam combinar distância de caracteres com blocagem, métodos fonéticos, frequências de nomes e revisão de casos limítrofes.
OCR e comparação de transcrições
Em OCR, uma distância de edição calculada entre a transcrição reconhecida e uma transcrição de referência pode quantificar erros de inserção, deleção e substituição. O mesmo princípio aparece em medidas como a taxa de erro de caracteres.
No contexto brasileiro, a distância de edição também aparece em trabalhos acadêmicos de comparação de transcrições e busca aproximada em sistemas que lidam com texto extraído automaticamente.
Linguística e psicolinguística
A distância de Levenshtein pode ser aplicada a palavras para medir semelhança ortográfica ou fonológica. Em pesquisas brasileiras sobre palavras cognatas português–inglês, a versão normalizada foi usada para representar o grau de similaridade formal entre pares de palavras.
Recursos lexicais do português brasileiro também incorporam medidas derivadas de Levenshtein como atributos de vizinhança ortográfica, permitindo caracterizar o grau de proximidade de uma palavra em relação a outras formas lexicais.
Reconhecimento de fala
Em reconhecimento automático da fala, palavras podem ser tratadas como os símbolos da sequência. O Word Error Rate (WER) é calculado a partir do número de substituições , deleções e inserções no alinhamento entre hipótese e transcrição de referência:
em que é o número de palavras da referência.
Essa medida corresponde a uma distância de edição em nível de palavras, normalizada pelo comprimento da referência.
Bioinformática
Em bioinformática, a distância de edição está relacionada à comparação e ao alinhamento de sequências. Inserções, deleções e substituições fornecem um modelo simples para diferenças entre sequências de DNA ou proteínas. No entanto, algoritmos de alinhamento usados na prática normalmente empregam sistemas de pontuação, matrizes de substituição e penalidades de gap mais ricos do que a distância de Levenshtein de custo unitário.Bonnie Berger, Michael S. Waterman e Yun William Yu, “Levenshtein Distance, Sequence Comparison and Biological Database Search”, IEEE Transactions on Information Theory, v. 67, n. 6, 2021, p. 3287–3294. doi:10.1109/TIT.2020.2996543.
Unicode e unidade de comparação
A definição matemática trabalha com sequências de símbolos, mas não determina o que um “caractere” deve significar em uma implementação. Em texto Unicode, a comparação pode ser feita sobre bytes, unidades de código, pontos de código ou clusters de grafemas; escolhas diferentes podem produzir valores diferentes.