Distância Levenshtein
# Distância Levenshtein

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.

## 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 de 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.

## 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:
A constante mantida ao longo do algoritmo é que podemos transformar o segmento inicial str1[1..X] em str2[1..Y] usando um mínimo de operações tab[X,Y]. No final, o elemento no fundo ao lado direito do array contém a resposta.

### 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 Y.
* Podemos dar diferentes penalidades de custo à inserção, deleção e substituição.
* A inicialização do tab[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 eliminar dependências.

### Prova de sucesso

Como foi mencionado, a constante é que podemos transformar o segmento inicial s[1..X] em t[1..Y] usando um mínimo de tab[X,Y] operações. Esta constante é verdadeira já que:
* É inicialmente verdadeira na linha e colunas 0 porque s[1..X] pode ser transformado num string vazio t[1..0] por simplesmente apagando todos os X caracteres. Do mesmo modo, podemos transformar s[1..0] em t[1..Y] ao simplesmente adicionando todos os caracteres Y.
* O mínimo é tomado em três distâncias, sendo em qualquer das quais possível que:
** Se podemos transformar s[1..X] a t[1..Y-1] em k operações, então nós podemos simplesmente adicionar t[Y] depois para obter t[1..Y] em k+1 operações.
** Se podemos transformar s[1..X-1] a t[1..Y] em k operações, então nós podemos fazer as mesmas operações em s[1..X] e depois remover o s[X] original ao fim de k+1 operações.
** Se podemos transformar s[1..X-1] a t[1..Y-1] em k operações, então podemos fazer o mesmo com s[1..X] e depois fazer uma substituição de t[Y] pelas s[X] 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 tab[n,m] contém o nosso resultado desejado.
Esta prova não confirma que o número colocado em tab[X,Y] seja de facto o mínimo; isso é mais difícil de provar e exige um argumento Reductio ad absurdum no qual assumimos que tab[X,Y] é menor que o mínimo dos três, e usamos isto para mostrar que um dos três não é mínimo.

## 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 de 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.

## Links (em português, inglês e alemão)

* Levenshtein distance - Rosetta Code - Implementações do algoritmo em diversas linguagens de programação
* O fantástico mundo da distância de edição (um survey em formato PDF sobre distância de edição)
* Levenshtein Distance, in Three Flavors, by Michael Gilleland
* NIST's Dictionary of Algorithms and Data Structures: Levenshtein Distance
* CSE 590BI, Winter 1996 Algorithms in Molecular Biology The algorithms from lectures 2, 3 and 4 are based on the Levenshtein distance but implement a different scoring function. The Haskell example was based on these notes.
* Levenshtein Distance - visualized
* Distance between strings - Levenshtein and Hamming
* Another Edit Distance Visualization (very fast)
* Wie funktioniert der Levenshtein-Algorithmus…?