A distância Levenshtein (ou distância de edição) é uma maneira de quantificar a diferença entre duas strings contando o número mínimo de operações necessárias para transformar uma string na outra.
A distância Levenshtein entre duas palavras é o número mínimo de edições de um único caractere (ou seja, inserções, exclusões ou substituições) necessárias para mudar uma palavra para outra. Cada uma dessas operações tem um custo unitário.
Por exemplo, a distância Levenshtein entre kitten e sitting é 3. O script de edição mínimo que transforma o primeiro no último é:
sitten —> sittin (substitution of i for e)
sittin —> sitting (insertion of g at the end)
O problema Editar distância tem subestrutura ideal. Isso significa que o problema pode ser dividido em “subproblemas” menores e simples, que podem ser divididos em subproblemas ainda mais simples, e assim por diante, até que, finalmente, a solução se torne trivial.
Problema: Transformar string X[1…m] em Y[1…n] executando operações de edição na string X.
Subproblema: Transformar substring X[1…i] em Y[1…j] executando operações de edição na substring X.
Caso 1: Chegamos ao final de qualquer substring.
Se substring X está vazio, insira todos os caracteres restantes da substring Y em X. O custo desta operação é igual ao número de caracteres restantes na substring Y.
('', 'ABC') ——> ('ABC', 'ABC') (cost = 3)
Se substring Y está vazio, insira todos os caracteres restantes da substring X em Y. O custo desta operação é igual ao número de caracteres restantes na substring X.
('ABC', '') ——> ('', '') (cost = 3)
Caso 2: Os últimos caracteres da substring X e Y são os mesmos.
Se os últimos caracteres da substring X e substring Y correspondências, nada precisa ser feito - basta recorrer para a substring restante X[0…i-1], Y[0…j-1]. Como nenhuma operação de edição está envolvida, o custo será 0.
('ACC', 'ABC') ——> ('AC', 'AB') (cost = 0)
Caso 3: Os últimos caracteres da substring X e Y são diferentes.
Se os últimos caracteres da substring X e Y forem diferentes, retorne o mínimo das seguintes operações:
- Insira o último caractere de
YemX. O tamanho deYreduz em 1, eXcontinua o mesmo. Isso dá contaX[1…i],Y[1…j-1]à medida que avançamos na substring de destino, mas não na substring de origem.
('ABA', 'ABC') ——> ('ABAC', 'ABC') == ('ABA', 'AB') (using case 2) - Apague o último caractere de
X. O tamanho deXreduz em 1, eYcontinua o mesmo. Isso dá contaX[1…i-1],Y[1…j]à medida que avançamos na string de origem, mas não na string de destino.
('ABA', 'ABC') ——> ('AB', 'ABC') - Substituir (Substituir) o caractere atual de
Xpelo personagem atualY. O tamanho de ambosXeYreduz em 1. Isso representaX[1…i-1],Y[1…j-1]à medida que nos movemos na string de origem e de destino.
('ABA', 'ABC') —> ('ABC', 'ABC') == ('AB', 'AB') (using case 2)É basicamente o mesmo que o caso 2, onde os dois últimos caracteres correspondem, e movemos tanto a string de origem quanto a de destino, exceto que custa uma operação de edição.
Assim, podemos definir o problema recursivamentemente como:
dist[i][j] = | dist[i – 1][j – 1] when X[i-1] == Y[j-1]
| 1 + minimum { dist[i – 1][j], when X[i-1] != Y[j-1]
| dist[i][j – 1],
| dist[i – 1][j – 1] }
A seguir está a implementação C++, Java e Python da ideia:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> using namespace std; // Função para encontrar a distância Levenshtein entre a string `X` e `Y`. // `m` e `n` é o número total de caracteres em `X` e `Y`, respectivamente int dist(string X, int m, string Y, int n) { // caso base: strings vazias (case 1) if (m == 0) { return n; } if (n == 0) { return m; } int cost; // se os últimos caracteres das strings corresponderem (case 2) if (X[m - 1] == Y[n - 1]) { cost = 0; } else { cost = 1; } return min (min(dist(X, m - 1, Y, n) + 1, // exclusão (caso 3a)) dist(X, m, Y, n - 1) + 1), // inserção (caso 3b)) dist(X, m - 1, Y, n - 1) + cost); // substituição (caso 2 e 3c) } int main() { string X = "kitten", Y = "sitting"; cout << "The Levenshtein distance is " << dist(X, X.length(), Y, Y.length()); return 0; } |
Resultado:
The Levenshtein distance is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class Main { // Função de utilidade para encontrar o mínimo de três números public static int minimum(int a, int b, int c) { return Integer.min(a, Integer.min(b, c)); } // Função para encontrar a distância Levenshtein entre a string `X` e `Y`. // `m` e `n` é o número total de caracteres em `X` e `Y`, respectivamente public static int dist(String X, int m, String Y, int n) { // caso base: strings vazias (case 1) if (m == 0) { return n; } if (n == 0) { return m; } // se os últimos caracteres das strings corresponderem (case 2) int cost = (X.charAt(m - 1) == Y.charAt(n - 1)) ? 0: 1; return minimum(dist(X, m - 1, Y, n) + 1, // exclusão (caso 3a)) dist(X, m, Y, n - 1) + 1, // inserção (caso 3b)) dist(X, m - 1, Y, n - 1) + cost); // substituição (caso 2 e 3c) } public static void main(String[] args) { String X = "kitten", Y = "sitting"; System.out.println("The Levenshtein distance is " + dist(X, X.length(), Y, Y.length())); } } |
Resultado:
The Levenshtein distance is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
# Função para encontrar a distância Levenshtein entre a string `X` e `Y`. # `m` e `n` é o número total de caracteres em `X` e `Y`, respectivamente def dist(X, m, Y, n): # Caso base: strings vazias (caso 1) if m == 0: return n if n == 0: return m # se os últimos caracteres das strings corresponderem (caso 2) cost = 0 if (X[m - 1] == Y[n - 1]) else 1 return min(dist(X, m - 1, Y, n) + 1, # Deleção de # (caso 3a)) dist(X, m, Y, n - 1) + 1, # Inserção de # (caso 3b)) dist(X, m - 1, Y, n - 1) + cost) # Substituição de # (caso 2 + 3c) if __name__ == '__main__': X = 'kitten' Y = 'sitting' print('The Levenshtein distance is', dist(X, len(X), Y, len(Y))) |
Resultado:
The Levenshtein distance is 3
A complexidade de tempo da solução acima é exponencial e ocupa espaço na ligue para Stack.
Como visto acima, o problema subestrutura ideal. A solução acima também apresenta subproblemas sobrepostos. Se desenharmos a árvore de recursão da solução, podemos ver que os mesmos subproblemas são computados repetidamente. Sabemos que problemas com subestrutura ótima e subproblemas sobrepostos podem ser resolvidos usando programação dinâmica, na qual as soluções de subproblemas são memorizadas em vez de computadas repetidamente.
o memorandoA versão ized segue a abordagem de cima para baixo, pois primeiro dividimos o problema em subproblemas e, em seguida, calculamos e armazenamos valores. Também podemos resolver este problema de forma ascendente. Na abordagem de baixo para cima, resolvemos primeiro os subproblemas menores, depois resolvemos os subproblemas maiores a partir deles.
A invariante mantida ao longo do algoritmo é que podemos transformar o segmento inicial X[1…i] em Y[1…j] usando um mínimo de T[i, j] operações. No final, o elemento do array no canto inferior direito contém a resposta.
Por exemplo, deixe X ser 'gatinho', e Y estar 'sentado'. A distância de Levenshtein entre X e Y é 3. O i'th linha e j'th coluna na tabela abaixo mostra a distância Levenshtein da substring X[0…i-1] e Y[0…j-1].
A seguir está a implementação C++, Java e Python da ideia:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <iostream> #include <cstring> using namespace std; // Função para encontrar a distância Levenshtein entre a string `X` e `Y`. // `m` e `n` é o número total de caracteres em `X` e `Y`, respectivamente int dist(string X, string Y) { int m = X.length(); int n = Y.length(); // Para todos os pares de `i` e `j`, `T[i, j]` manterá a distância Levenshtein // entre os primeiros caracteres `i` de `X` e os primeiros caracteres `j` de `Y`. // Note que `T` contém valores `(m+1)×(n+1)`. int T[m + 1][n + 1]; // inicializa `T` por todos os 0's memset(T, 0, sizeof T); // podemos transformar prefixos de origem em uma string vazia por // removendo todos os caracteres for (int i = 1; i <= m; i++) { T[i][0] = i; // (caso 1) } // podemos alcançar prefixos de destino a partir do prefixo de origem vazio // inserindo todos os caracteres for (int j = 1; j <= n; j++) { T[0][j] = j; // (caso 1) } int substitutionCost; // preenche a tabela de pesquisa de forma baixo para cima for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (X[i - 1] == Y[j - 1]) { // (caso 2) substitutionCost = 0; // (caso 2) } else { substitutionCost = 1; // (caso 3c) } T[i][j] = min(min(T[i - 1][j] + 1, // exclusão (caso 3b) T[i][j - 1] + 1), // inserção (caso 3a) T[i - 1][j - 1] + substitutionCost); // substitui (caso 2 e 3c) } } return T[m][n]; } int main() { string X = "kitten", Y = "sitting"; cout << "The Levenshtein distance is " << dist(X, Y); return 0; } |
Resultado:
The Levenshtein distance is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
class Main { // Função de utilidade para encontrar o mínimo de três números public static int minimum(int a, int b, int c) { return Integer.min(a, Integer.min(b, c)); } // Função para encontrar a distância Levenshtein entre a string `X` e `Y`. public static int dist(String X, String Y) { // `m` e `n` é o número total de caracteres em `X` e `Y`, respectivamente int m = X.length(); int n = Y.length(); // Para todos os pares de `i` e `j`, `T[i, j]` manterá a distância Levenshtein // entre os primeiros caracteres `i` de `X` e os primeiros caracteres `j` de `Y`. // Note que `T` contém valores `(m+1)×(n+1)`. int[][] T = new int[m + 1][n + 1]; // podemos transformar prefixos de origem em uma string vazia por // removendo todos os caracteres for (int i = 1; i <= m; i++) { T[i][0] = i; // (caso 1) } // podemos alcançar prefixos de destino a partir do prefixo de origem vazio // inserindo todos os caracteres for (int j = 1; j <= n; j++) { T[0][j] = j; // (caso 1) } int cost; // preenche a tabela de pesquisa de forma baixo para cima for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (X.charAt(i-1) == Y.charAt(j-1)) { // (caso 2) cost = 0; // (caso 2) } else { cost = 1; // (caso 3c) } T[i][j] = minimum(T[i - 1][j] + 1, // exclusão (caso 3b) T[i][j - 1] + 1, // inserção (caso 3a) T[i - 1][j - 1] + cost); // substitui (caso 2 + 3c) } } return T[m][n]; } public static void main(String[] args) { String X = "kitten", Y = "sitting"; System.out.print("The Levenshtein distance is " + dist(X, Y)); } } |
Resultado:
The Levenshtein distance is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
# Função para encontrar a distância Levenshtein entre a string `X` e `Y`. def dist(X, Y): # `m` e `n` é o número total de caracteres em `X` e `Y`, respectivamente (m, n) = (len(X), len(Y)) # Para todos os pares de `i` e `j`, `T[i, j]` manterá a distância Levenshtein # entre os primeiros caracteres `i` de `X` e os primeiros caracteres `j` de `Y`. # Observe que `T` contém valores `(m+1)×(n+1)`. T = [[0 for x in range(n + 1)] for y in range(m + 1)] # podemos transformar prefixos de origem em uma string vazia por # soltando todos os personagens for i in range(1, m + 1): T[i][0] = i # (caso 1) # podemos alcançar prefixos de destino do prefixo de origem vazio # inserindo todos os caracteres for j in range(1, n + 1): T[0][j] = j # (caso 1) # preenche a tabela de pesquisa de forma baixo para cima for i in range(1, m + 1): for j in range(1, n + 1): if X[i - 1] == Y[j - 1]: # (caso 2) cost = 0 # (caso 2) else: cost = 1 # (caso 3c) T[i][j] = min(T[i - 1][j] + 1, # Deleção de # (caso 3b) T[i][j - 1] + 1, # Inserção de # (caso 3a) T[i - 1][j - 1] + cost) # substituir (caso 2 + 3c) return T[m][n] if __name__ == '__main__': X = 'kitten' Y = 'sitting' print('The Levenshtein distance is', dist(X, Y)) |
Resultado:
The Levenshtein distance is 3
A complexidade de tempo da solução acima é O(m.n) e requer O(m.n) espaço extra, onde m é o comprimento da primeira string e n é o comprimento da segunda string. Acontece que apenas duas linhas da tabela são necessárias para a construção se não se quiser reconstruir as strings de entrada editadas (a linha anterior e a linha atual sendo calculadas).
Exercício: Modifique a versão iterativa para usar apenas duas linhas da matriz.
Referências: Distância Levenshtein – Wikipedia