Distância Levenshtein

Origem: Wikipédia, a enciclopédia livre.

Em teoria da informação, a distância Levenshtein ou distância de edição entre dois "strings" (duas sequências de caracteres) é dada pelo número mínimo de operações necessárias para transformar um string no outro. Entendemos por "operações" a inserção, deleção ou substituição de um carácter. O nome advém do cientista russo Vladimir Levenshtein, que considerou esta distância já em 1965. É muito útil para aplicações que precisam determinar quão semelhantes dois strings são, como é por exemplo o caso com os verificadores ortográficos.

[editar] Exemplo

Por exemplo, a distância Levenshtein entre as palavras inglesas "kitten" (gato) e "sitting" (sentando-se) é 3, já que com apenas 3 edições conseguimos transformar uma palavra na outra, e não há maneira de o fazer com menos de três edições:

kitten
sitten (substituição de 'k' por 's')
sittin (substituição de 'e' por 'i')
sitting (inserção de 'g' no final)

A distância de Levenshtein pode ser considerada como uma generalização da Distância Hamming, usada para strings com o mesmo tamanho, a qual só considera edições por substituição. Há também outras generalizações da distância Levenshtein que consideram, por exemplo, a troca de dois caracteres como uma aplicação.

[editar] O algoritmo

Um algoritmo bottom-up de programação dinâmica usado frequentemente para calcular a distância Levenshtein usa uma matriz (n + 1) × (m + 1), na qual n e m são o número de caracteres dos dois strings. Aqui um pseudocódigo para uma função LevenshteinDistance que usa dois strings, str1 de comprimento lenStr1, e str2 de comprimento lenStr2, e calcula a distância Levenshtein entre eles:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is a table with lenStr1+1 rows and lenStr2+1 columns
   declare int d[0..lenStr1, 0..lenStr2]
   // i and j are used to iterate over str1 and str2
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 0 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i] = str2[j] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j  ] + 1,     // deletion
                                d[i  , j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
 
   return d[lenStr1, lenStr2]

A constante mantida ao longo do algoritmo é que podemos transformar o segmento inicial str1[1..i] em str2[1..j] usando um mínimo de operações d[i,j]. No final, o elemento no fundo ao lado direito do array contém a resposta.

[editar] Melhoramentos possíveis

Melhoramentos possíveis para este algoritmo poderiam ser por exemplo:

Podemos adaptar o algoritmo para usar menos espaço, O(m) em vez de O(mn), já que ele apenas requer que a linha anterior e a linha actual sejam armazenadas ao mesmo tempo.
Podemos armazenar o número de inserções, deleções e substituições separadamente, ou mesmo as posições em que elas ocorrem, que são sempre j.
Podemos dar diferentes penalidades de custo à inserção, deleção e substituição.
A inicialização do d[i,0] pode passar para dentro do grande loop principal exterior.
Este algoritmo paraleliza de uma forma pouco eficiente, devido a grande número de dependências de dados. No entanto, todo o custo pode ser calculado em paralelo, e o algoritmo pode ser adaptado para perfazer a função mínimo em fases para eleminar dependências.

[editar] Prova de sucesso

Como foi mencionado, a constante é que podemos transformar o segmento inicial s[1..i] em t[1..j] usando um mínimo de d[i,j] operações. Esta constante é verdadeira já que:

É inicialmente verdadeira na linha e colunas 0 porque s[1..i] pode ser transformado num string vazio t[1..0] por simplesmente apagando todos os i caracteres. Do mesmo modo, podemos transformar s[1..0] em t[1..j] ao simplesmente adicionando todos os caracteres j.
O mínimo é tomado em três distâncias, sendo em qualquer das quais possível que:
- Se podemos transformar s[1..i] a t[1..j-1] em k operações, então nós podemos simplesmente adicionar t[j] depois para obter t[1..j] em k+1 operações.
- Se podemos transformar s[1..i-1] a t[1..j] em k operações, então nós podemos fazer as mesmas operações em s[1..i] e depois remover o s[i] original ao fim de k+1 operações.
- Se podemos transformar s[1..i-1] a t[1..j-1] em k operações, então podemos fazer o mesmo com s[1..i] e depois fazer uma substituição de t[j] pelas s[i] originais no final, se necessário, requerindo k+cost operações.
As operações requiridas para transformar s[1..n] em t[1..m] é o número necessário para transformar todos os s em todos os t, e logo d[n,m] contém o nosso resultado desejado.

Esta prova não confirma que o número colocado em d[i,j] seja de facto o mínimo; isso é mais difícil de provar e exige um argumento Reductio ad absurdum no qual assumimos que d[i,j] é mais pequeno do que o mínimo dos três, e usamos isto para mostrar que um dos três não é mínimo.

[editar] Implementações

Exemplo de implementações podem ser encontrados em Wikisource.

[editar] Limites superior e inferior

A distância Levenshtein tem vários limites superior e inferior simples que são úteis em aplicações que calculam vários deles e os comparam. Estes incluem:

É sempre pelo menos igual à diferença dos tamanhos dos dois strings.
É no máximo igual ao tamanho do string mais longo.
É zero se e só se os strings são idênticos.
Se os strings têm o mesmo tamanho, a distância Hamming é um limite superior da distância Levenshtein.
Se os strings são chamados s e t, o número de caracteres (não contando os duplicados) que encontramos em s mas não em t é um limite inferior.