Última atualização: 2026-07-01

Distância de Levenshtein

A distância de Levenshtein, também chamada de distância de edição, mede o quanto duas cadeias de caracteres são diferentes contando o menor número de edições de um único caractere necessárias para converter uma na outra. As edições permitidas são inserção, exclusão e substituição, cada uma com custo um. A calculadora recebe duas cadeias e devolve essa distância junto com uma porcentagem de similaridade, o que é útil para corretor ortográfico, correspondência aproximada e comparação de sequências como o DNA.

As três operações de edição

Toda transformação entre duas cadeias pode ser expressa como uma sequência de três movimentos básicos. Uma inserção adiciona um caractere, uma exclusão remove um e uma substituição troca um caractere por outro. A distância de Levenshtein procura a sequência mais econômica desses movimentos, em que cada um custa um. Como a substituição é um único passo, e não uma exclusão seguida de uma inserção, mudar uma letra conta sempre como uma edição, não duas.

Nomeada em homenagem a Vladimir Levenshtein, que a definiu em 1965, a medida generaliza a mais antiga Calculadora de Distância de Hamming: a distância de Hamming permite apenas substituições e somente para cadeias de igual comprimento, enquanto a de Levenshtein admite também inserções e exclusões, de modo que lida com cadeias de comprimentos diferentes.

A tabela de programação dinâmica

A distância é calculada preenchendo uma tabela $D$ com uma linha por caractere da primeira cadeia (mais uma linha vazia inicial) e uma coluna por caractere da segunda (mais uma coluna vazia inicial). A célula $D[i][j]$ contém a distância de edição entre os primeiros $i$ caracteres de A e os primeiros $j$ caracteres de B.

A primeira linha e a primeira coluna contam as edições em relação à cadeia vazia, de modo que $D[i][0] = i$ e $D[0][j] = j$. Qualquer outra célula é o mínimo de três candidatos:

em que o custo de substituição $c$ é 0 quando os caracteres coincidem e 1 quando diferem. A resposta fica na célula inferior direita. Preencher a tabela leva um tempo proporcional ao produto dos dois comprimentos, $m \times n$.

Exemplo resolvido

Tomemos o par clássico «kitten» e «sitting». Percorrer o caminho ótimo pela tabela resulta em três edições:

Não existe nenhuma sequência mais curta, então a distância é 3. A cadeia mais longa tem 7 caracteres, de modo que a similaridade é $1 - 3/7 \approx 0{,}571$, ou seja, cerca de 57%.

A similaridade e seus limites

A calculadora normaliza a distância bruta em uma pontuação de similaridade por meio de

$S = 1 - \dfrac{d_L}{\max(m, n)}$

Dividir pelo comprimento da cadeia mais longa mantém o resultado entre 0% para cadeias totalmente diferentes e 100% para idênticas; duas cadeias vazias são consideradas idênticas. Essa é uma das normalizações comuns — outras ferramentas dividem pela soma dos comprimentos ou usam medidas baseadas em razões —, portanto os números de similaridade de fontes diferentes não são diretamente comparáveis.

Onde é usada

Os corretores ortográficos ordenam as correções candidatas pela distância de edição em relação à palavra escrita errada. Sistemas de busca e de bancos de dados a usam para correspondência aproximada, tolerando erros de digitação ao consultar nomes ou endereços. Na bioinformática, a distância de edição é a base do alinhamento de sequências para comparar DNA, RNA e proteínas, em que inserções e exclusões correspondem a mutações. O modelo de custo de Levenshtein simples trata todas as edições igualmente; aplicações que precisam de penalidades diferentes para operações diferentes, ou que devem alinhar sequências muito longas de forma eficiente, o estendem com custos ponderados ou algoritmos de alinhamento especializados.