Calculadora de Distância Levenshtein

Calculadora de distância Levenshtein

Este exemplo calcula a distância Levenshtein do String Tools, já carregado com a comparação clássica de “kitten” para “sitting”. Digite duas strings e veja o número mínimo de edições de um caractere só para transformar uma na outra.

Como funciona

A distância Levenshtein usa programação dinâmica. Uma matriz é construída onde cada célula representa a distância de edição entre substrings. O algoritmo preenche a matriz considerando três operações em cada posição:

O valor final na célula inferior direita da matriz é a distância Levenshtein.

O exemplo de “kitten” para “sitting”

O exemplo clássico exige 3 edições:

1. kitten → sitten (substituir k por s)
2. sitten → sittin (substituir e por i)
3. sittin → sitting (inserir g no fim)

Distância = 3.

Complexidade de tempo e espaço

O algoritmo roda em tempo e espaço O(m x n), onde m e n são os tamanhos das duas strings. Para a maioria das comparações práticas de texto (menos de 1000 caracteres), isso executa na hora no navegador.

Variações

Vários algoritmos adaptam o Levenshtein para casos de uso específicos:

• Damerau-Levenshtein adiciona transposição (trocar caracteres adjacentes) como quarta operação
• Weighted Levenshtein atribui custos diferentes às operações (por ex. substituição custa mais que inserção)
• Restricted edit distance limita quais operações são permitidas

Como usar

1. Digite a primeira string no campo de entrada
2. Digite a segunda string no segundo campo
3. A distância de edição aparece na área de resultado
4. A ferramenta também mostra a transformação passo a passo

Perguntas comuns

Qual é a distância máxima possível?

A distância máxima é o tamanho da string mais longa, o que acontece quando uma string está totalmente vazia e você precisa inserir cada caractere. Para duas strings de tamanhos m e n, a distância é no máximo max(m, n).

Como o case sensitivity afeta o resultado?

A comparação é case-sensitive. Hello e hello têm distância 1 (a diferença de H/h). Para uma comparação case-insensitive, converta as duas strings para minúsculas primeiro.

Posso usar isso para comparar sequências de DNA?

Sim. A distância Levenshtein é muito usada em bioinformática para medir similaridade entre sequências de DNA ou proteínas. Cada caractere representa um nucleotídeo ou aminoácido, e a edit distance reflete o número de mutações entre as sequências.