Distância de edição (distância de Levenshtein)

Escreva recieve e o telemóvel sugere receive. Sabe que quase acertou porque as duas palavras estão a apenas algumas operações de distância. Medir essa proximidade, a distância de edição, é um problema clássico de programação dinâmica.

Uma tabela com uma palavra ao longo do lado esquerdo e outra ao longo do topo, números nas células e um caminho laranja de operações desde o canto superior esquerdo até ao canto inferior direito
Uma tabela com uma palavra ao longo do lado esquerdo e outra ao longo do topo, números nas células e um caminho laranja de operações desde o canto superior esquerdo até ao canto inferior direito

O problema

Uma operação altera uma palavra numa letra: inserir uma letra, eliminar uma letra ou substituir uma letra por outra. A distância de edição entre duas palavras é o menor número de operações que transformam uma na outra. Entre cat e cut a distância é 1, entre cat e cast também 1, e entre cat e act é 2. Também se chama distância de Levenshtein, em homenagem ao matemático soviético Vladimir Levenshtein, que a estudou em 1965.

A tabela

Seja d[i][j] a distância de edição entre as primeiras i letras de uma palavra e as primeiras j letras da outra. Transformar uma palavra em nada custa uma eliminação por letra, por isso d[i][0] = i, e construir uma palavra a partir do nada custa uma inserção por letra, por isso d[0][j] = j. Se a letra i for igual à letra j, d[i][j] = d[i − 1][j − 1]. Caso contrário, d[i][j] = 1 + o menor de d[i − 1][j − 1] (substituição), d[i − 1][j] (eliminação) e d[i][j − 1] (inserção).

Um exemplo

Para kitten e sitting, a tabela tem 7 linhas e 8 colunas. A célula do canto inferior direito vale 3, e a leitura de trás para a frente a partir dela dá: substituir k por s, manter i, t e t, substituir e por i, manter n e inserir g. De kitten para sitten, depois sittin e depois sitting: três operações, e a tabela prova que não existe nenhuma lista mais curta.

Ler as operações de trás para a frente

Comece na célula do canto inferior direito e pergunte de que vizinho veio o seu valor. Se as letras coincidirem e a célula for igual à vizinha acima e à esquerda, a letra foi mantida: avance na diagonal. Se valer mais um do que a vizinha acima e à esquerda, foi uma substituição; mais um do que a célula acima, uma eliminação; mais um do que a célula à esquerda, uma inserção. Vários caminhos podem empatar, e cada um dá uma lista de operações o mais curta possível.

História e aplicações

Levenshtein introduziu a distância em 1965, quando trabalhava em códigos corretores de erros. O método da tabela foi publicado por várias pessoas, sobretudo por Robert Wagner e Michael Fischer em 1974, e por isso chama-se muitas vezes algoritmo de Wagner–Fischer. Hoje, as distâncias de edição ordenam sugestões ortográficas, encontram nomes com gralhas em bases de dados, comparam sequências de ADN e de proteínas e avaliam o reconhecimento de fala.

Explore

Abra a aplicação e prima Avançar. As duas letras comparadas acendem-se nos cabeçalhos; se forem iguais, copia-se a célula azul acima e à esquerda, e se forem diferentes, leem-se os três vizinhos azuis e soma-se um ao menor. No fim, o caminho laranja volta para trás a partir do canto, e as operações aparecem por baixo da tabela.

Perguntas frequentes

A distância de edição é uma métrica?

Sim. Nunca é negativa, só vale 0 para palavras iguais, é a mesma nos dois sentidos, e passar por uma terceira palavra nunca a pode encurtar: d(a, c) ≤ d(a, b) + d(b, c). Isso torna-a útil para procurar correspondências próximas.

O que é a distância de Damerau–Levenshtein?

É a distância de edição com uma operação a mais: trocar duas letras vizinhas. Frederick Damerau verificou em 1964 que a inserção, a eliminação, a substituição e a troca, em conjunto, cobrem mais de 80% dos erros ortográficos. Com trocas, recieve e receive estão à distância 1 em vez de 2.

É possível calcular a distância de edição mais depressa do que O(m·n)?

Não muito. Em 2015, Arturs Backurs e Piotr Indyk mostraram que um método com tempo O(n^(2 − ε)) para algum ε > 0 refutaria a hipótese do tempo exponencial forte, na qual a maioria dos investigadores acredita. Para palavras próximas, porém, basta uma faixa estreita em torno da diagonal da tabela.

Como se usa a distância de edição na comparação de ADN?

Os biólogos usam a mesma tabela com pontuações em vez de contagens: as correspondências ganham pontos, e as substituições e as lacunas custam pontos que dependem das letras. É o algoritmo de Needleman–Wunsch, de 1970, para sequências inteiras, e o algoritmo de Smith–Waterman, de 1981, para os troços que melhor correspondem.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimentar a distância de edição