Wikipédia

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

editar

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:

  1. kitten
  2. sitten (substituição de 'k' por 's')
  3. sittin (substituição de 'e' por 'i')
  4. 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

editar

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: 

Função LevenshteinDistance(Caracter : str1[1..lenStr1], Caracter : str2[1..lenStr2]) : INTEIRO
Início
   // tab é uma tabela com lenStr1+1 linhas e lenStr2+1 colunas
   Inteiro:  tab[0..lenStr1, 0..lenStr2]
   // X e Y são usados para iterar str1 e str2
   Inteiro:  X, Y, cost
 
   Para X de 0 até lenStr1
       tab[X, 0] ← X
   Para Y de 0 até lenStr2
       tab[0, Y] ← Y
 
   Para X de 1 até lenStr1
       Para Y de 1 até lenStr2
           Se str1[X] = str2[Y] Então cost ← 0
                                Se-Não cost ← 1 // Custo da substituição deve ser 1, deleção e inserção
           tab[X, Y] := menor(
                                tab[X-1, Y  ] + 1,     // Deletar
                                tab[X  , Y-1] + 1,     // Inserir
                                tab[X-1, Y-1] + cost   // Substituir
                            )
   LevenshteinDistance ← tab[lenStr1, lenStr2]
 Fim

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

editar

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

editar

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

editar

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.
editar
Obtida de "https://pt.wiki.x.io/w/index.php?title=Distância_Levenshtein&oldid=66833600"