Calculadora de Similaridade de Strings

A distância de Levenshtein (distância de edição) é o número mínimo de edições de um único caractere necessárias para transformar uma string em outra. As três operações permitidas são: inserção (adicionar um caractere), exclusão (remover um caractere), substituição (substituir um caractere por outro). Exemplo: "kitten" → "sitting" requer 3 operações: k→s, e→i, +g. Nomeada após Vladimir Levenshtein, que descreveu este algoritmo em 1965. Aplicações: verificação ortográfica, alinhamento de sequências de DNA, processamento de linguagem natural, correspondência aproximada de strings.

Similaridade % = (1 − distânciaEdição / max(len1, len2)) × 100. Isso normaliza a distância em relação à string mais longa. Exemplo: distância = 2, comprimento máximo = 8 → similaridade = (1 − 2/8) × 100 = 75%. Uma distância de 0 significa strings idênticas (100% similares). Outras métricas de similaridade incluem Jaro-Winkler (pondera mais o acordo de caracteres iniciais) e similaridade de cosseno (para comparação baseada em tokens).

Damerau-Levenshtein estende o Levenshtein adicionando uma quarta operação: transposição (troca de dois caracteres adjacentes). Exemplo: "ab" → "ba" tem distância de Levenshtein 2 (excluir + inserir), mas distância de Damerau-Levenshtein 1 (uma transposição). Isso é importante para verificação ortográfica, pois muitos erros de digitação são transposições ("teh" → "the"). Esta ferramenta usa o Levenshtein padrão (sem transposições).

Verificadores ortográficos: sugerem palavras com baixa distância de edição da palavra mal escrita. Sequenciamento de DNA: alinha sequências de nucleotídeos para encontrar mutações e inserções. Controle de versão: o git diff usa algoritmos de distância de edição para mostrar alterações no nível de linha. Processamento de linguagem natural: desambiguação de entidades nomeadas, resolução de correferência. Detecção de fraude: detecta variações de nomes (typosquatting, fraude de identidade). Vinculação de registros: corresponde registros em bancos de dados quando nomes/endereços variam ligeiramente.

O algoritmo Wagner-Fischer calcula a distância de Levenshtein usando programação dinâmica com tempo O(m×n) e espaço O(m×n), onde m,n são os comprimentos das strings. Ele constrói uma matriz onde a célula [i][j] = distância de edição entre os primeiros i caracteres da string 1 e os primeiros j caracteres da string 2. Casos base: linha 0 = 0..n, coluna 0 = 0..m. Recorrência: se s1[i] == s2[j], célula = diagonal anterior; caso contrário, célula = 1 + min(esquerda, acima, diagonal).