Visualizador da Distância de Levenshtein

Introduz duas cadeias de texto para ver a sua distância de Levenshtein (de edição) — o número mínimo de edições de um único carácter necessárias para transformar uma na outra.

Exemplo resolvido — Visualizador da Distância de Levenshtein

Distância de edição	3
Semelhança	57,14%

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Visualizador da Distância de Levenshtein

A distância de Levenshtein entre duas cadeias é o menor número de edições de um único carácter que transforma uma na outra, sendo uma edição uma inserção, uma eliminação ou uma substituição. É um mínimo sobre todas as maneiras possíveis de o fazer, e é isso que a torna difícil de avaliar a olho e fácil de calcular com uma grelha: existe um número astronómico de sequências de edição, e este procedimento encontra a mais curta sem listar nenhuma.

O que significa cada símbolo

m, n: os comprimentos das duas cadeias, A e B.
D(i, j): a forma mais barata de transformar os primeiros i caracteres de A nos primeiros j caracteres de B. Uma célula da tabela desta página.
[aᵢ ≠ bⱼ]: vale 1 quando esses dois caracteres diferem e 0 quando coincidem — o preço da substituição, que desaparece se não houver nada a substituir.
d: a resposta, D(m, n): a célula do canto inferior direito.

De onde vem a fórmula

Decida o que significa uma célula antes de preencher qualquer uma. Seja D(i, j) o número mínimo de edições que transforma os primeiros i caracteres de A nos primeiros j de B. O número que procura é D(m, n), e qualquer outra célula é uma versão menor da mesma pergunta.
As margens não exigem raciocínio. Para construir os primeiros j caracteres de B a partir do nada é preciso fazer j inserções, logo D(0, j) = j. Para reduzir a nada os primeiros i de A é preciso fazer i eliminações, logo D(i, 0) = i. É a linha de cima e a coluna da esquerda da grelha, e é por isso que se limitam a contar.
Agora o passo que faz todo o trabalho. Pegue em qualquer sequência óptima para D(i, j) e olhe apenas para o seu último movimento. Há três possibilidades e mais nenhuma: eliminou aᵢ, deixando a tarefa D(i−1, j); inseriu bⱼ, deixando D(i, j−1); ou emparelhou aᵢ com bⱼ, deixando D(i−1, j−1). Cada uma delas é uma célula que já preencheu.
Portanto a célula é a mais barata das três: D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] ). Preencha a grelha da esquerda para a direita e de cima para baixo, e ao chegar a qualquer célula as suas três vizinhas já são conhecidas. É todo o algoritmo — m × n células, três comparações cada.

Como ler o que vê

A grelha desta página é essa tabela. As linhas são A, as colunas são B, e a linha e a coluna extra no canto superior esquerdo são os prefixos vazios do passo 2 — daí contarem 0, 1, 2, 3. O sombreado de cada célula é o seu valor: o corredor diagonal pálido é onde as duas cadeias ainda coincidem barato. Passe o rato ou toque em qualquer célula e o painel por baixo detalha o passo 3 para essa célula — os três candidatos, cada um com a sua aritmética, e o vencedor destacado. A linha colorida é uma rota óptima traçada para trás a partir do canto inferior direito, e a faixa de alinhamento por baixo é essa mesma rota escrita em caracteres.

Pressupõe: Cada edição custa exactamente 1 e os caracteres são comparados por igualdade exacta — sem uniformização de maiúsculas, sem normalização Unicode e sem qualquer noção de que caracteres se parecem. Vêem-se aqui duas consequências. O que se conta aqui são unidades de código UTF-16, não aquilo a que chamaria letras: escreva um único emoji numa caixa e a tabela é 3 × 1, porque um emoji são duas unidades e eliminá-lo custa 2. E café com um é pré-composto contra café escrito como e mais um acento combinante dá distância 2, embora os dois pareçam idênticos no ecrã.
Falha quando: A grelha tem m × n células, pelo que o trabalho cresce com o produto dos comprimentos. Isso serve para duas palavras e é inviável para uma consulta contra um dicionário de um milhão de entradas, que são um milhão de grelhas. A resposta natural seria um algoritmo mais esperto, e a surpresa é que praticamente não existe: Backurs e Indyk mostraram em 2015 que uma distância de edição fortemente subquadrática refutaria a hipótese do tempo exponencial forte. Os correctores ortográficos reais não batem esse limite, contornam-no — parando assim que a distância excede um pequeno limiar, ou indexando de modo que quase nenhum candidato chegue a ser comparado.

A grelha é pequena porque cada subquestão só é feita uma vez 🖖

Procurar em todas as sequências possíveis de edições é inviável — o número de ordenações explode com o comprimento das palavras. A ideia fundamental que a salva é que qualquer par de prefixos tem exatamente uma resposta ideal, e essa resposta nunca muda, independentemente do que aconteça mais à frente na cadeia de carateres. Por isso, em vez de explorar sequências, preenche-se uma grelha: uma linha por letra da primeira palavra, uma coluna por letra da segunda, além de uma linha e coluna vazias que representam o prefixo vazio. Transformar kitten em sitting equivale, portanto, a 7 × 8 = 56 células, cada uma decidida ao olhar para três vizinhos já preenchidos, e a resposta 3 está à espera no canto inferior direito. O trabalho cresce com o produto dos dois comprimentos, não com o número de formas de editar.

Uma troca custa duas edições até que diga o contrário 🖖

Escreva form e from e o Levenshtein responde 2. Não tem qualquer noção de que as letras foram trocadas, portanto paga duas substituições. Mas letras trocadas estão entre os erros de escrita mais comuns que existem, e foi por isso que Damerau acrescentou um quarto movimento: se os dois caracteres de que precisa são exactamente os dois que tem pela ordem inversa, leve ambos pelo preço de um. Mude o modelo de custo acima e o mesmo par custa 1. Nada mudou nas palavras — mudou a tabela de preços. Vale a pena lembrar isto sempre que uma distância de edição serve de pontuação de semelhança, porque o número é tanto uma propriedade do modelo de custo escolhido como das duas cadeias.

A versão rápida não consegue desenhar esta imagem 🖖

Cada célula precisa apenas da linha acima de si e da célula à sua esquerda, portanto as linhas mais antigas nada ganham em ficar. As implementações reais aceitam o negócio e guardam duas linhas em vez da tabela inteira, o que leva a memória de m × n para min(m, n) — para duas cadeias de mil caracteres, de cerca de um milhão de células para duas mil. Aquilo a que renunciam é exactamente o que está desenhado acima. A distância sobrevive na última célula, mas o caminho até ela vivia nas linhas que foram sobrescritas, pelo que uma implementação de duas linhas lhe pode dizer que duas cadeias estão a três edições de distância e não quais três. Recuperar o caminho sem a grelha completa é mais difícil do que parece; Hirschberg resolveu-o em 1975 cortando a tabela ao meio e descendo recursivamente por ambas as metades.

Problema resolvido na íntegra

A sequência de edições de menor custo para transformar kitten em sitting 5 passos
Transforme kitten em sitting. Encontre a sequência de edições mais económica e prove que não existe nenhuma mais económica — depois, calcule quanto isto custa quando a segunda palavra é um dicionário inteiro.
1. A relação de recorrência é todo o algoritmo. Cada célula calcula quanto custa chegar aqui eliminando, inserindo ou alinhando os dois carateres atuais — sendo a última opção gratuita quando eles coincidem. Uma célula necessita apenas dos três vizinhos acima e à sua esquerda, pelo que um único varrimento da esquerda para a direita preenche a tabela.
  
  $d_{i, j} = min ⎩ ⎨ ⎧ d_{i - 1, j} + 1 d_{i, j - 1} + 1 d_{i - 1, j - 1} + [a_{i} \neq = b_{j}]$
2. Antes de preencher seja o que for, limite o intervalo da resposta. Os comprimentos diferem em um, pelo que pelo menos uma inserção é inevitável; e reescrever a palavra por completo custa 7. A resposta encontra-se no meio, o que elimina logo a maioria dos palpites.
  
  $∣ a ∣ - ∣ b ∣ = 1 \leq d \leq max (∣ a ∣, ∣ b ∣) = 7$
3. Três edições resolvem o problema: substituir k → s, substituir e → i, inserir g. Cada uma é uma única edição válida e a cadeia termina no alvo.
  
  $k \underline{i} tten \to s \underline{i} tten \to sitt \underline{i} n \to sitting$
4. Apresentar três edições apenas prova que a distância é no máximo 3. A tabela prova que é exatamente 3, porque todos os percursos até ao canto inferior direito são pontuados e o mínimo é considerado em cada célula ao longo do caminho. Essa é a diferença entre encontrar uma resposta e saber que ela não pode ser superada.
  
  $d = 3, similarity = 1 - \frac{3}{7} = 0.5714 = 57.14%$
5. O custo é de uma célula por par de carateres — 42 aqui, o que não é nada. Confrontado com um dicionário de 100 000 palavras com sete letras cada uma, são mais de quatro milhões de atualizações de células para uma única pesquisa.
  
  $Θ (∣ a ∣ ∣ b ∣) = 6 \times 7 = 42 cells; d (a, c) \leq d (a, b) + d (b, c)$
Resposta

A ferramenta apresenta 3 e uma semelhança de 57,14%, que é 1 − 3/7: a distância normalizada pela palavra mais longa. Ambas provêm de uma tabela que pode preencher à mão num minuto. O que não se ajusta à escala é a tabela — o trabalho é Θ(mn), pelo que duplicar ambas as cadeias quadruplica-o, e todos os corretores ortográficos que já utilizou foram concebidos para evitar fazer isto. A solução não é uma tabela mais rápida. É o facto de a distância de Levenshtein satisfazer a desigualdade triangular, de modo que d(a, c) ≤ d(a, b) + d(b, c) permite a um índice provar que um candidato está demasiado distante sem nunca medir essa distância.

$d (kitten, sitting) = 3, 1 - \frac{3}{7} = 57.14%$

Referências (4)

The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.

Pela equipa 42Math · Atualizado 2026-05-21

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

kitten → sitting - kitten → sitting é o caso dos manuais, e a resposta é 3: duas substituições e uma inserção, com 57,14% de semelhança
book → back - book → back são 2 operações entre duas palavras de quatro letras, apresentado como 50,00% de semelhança
Saturday → Sunday - Saturday → Sunday exige 3 edições e dá 62,50% de semelhança, duas delas eliminações
form → from (troca) - form → from é uma única troca sob Damerau–Levenshtein, que a ferramenta lê como 75,00% de semelhança
Comparação de ADN - GATTACA → GCATGCG exige 4 operações e 42,86% — a mesma medida aplicada a sequências