Distância Damerau–Levenshtein

A distância de Damerau–Levenshtein é uma métrica clássica de edição que conta quantas operações de um único caractere transformam uma cadeia em outra quando as operações permitidas são inserção, exclusão, substituição e transposição de dois caracteres adjacentes. Essa última operação é o que a separa da distância de Levenshtein simples e a torna especialmente útil para typos reais: as pessoas costumam trocar duas teclas vizinhas (form versus from, teh versus the) e isso deve custar um passo, não duas substituições. Esta capacidade implementa a forma Optimal String Alignment da distância com uma tabela pura de programação dinâmica, de modo que cada par de entradas produz o mesmo inteiro em qualquer runtime. Você envia dois textos e um indicador opcional de sensibilidade a maiúsculas; recebe a distância, ambos os comprimentos, uma similaridade normalizada entre zero e um, e um booleano identical.

O que Damerau–Levenshtein mede e como difere da Levenshtein simples

A distância de edição pergunta quantas mudanças unitárias são necessárias para reescrever uma cadeia de origem como uma cadeia de destino. A Levenshtein clássica permite três operações unitárias: inserir um caractere, excluir um caractere ou substituir um caractere por outro. Cada uma custa um.

A extensão de Damerau adiciona uma quarta operação: trocar dois caracteres adjacentes por um único custo unitário. Essa extensão corresponde a como as pessoas realmente digitam errado no teclado. Por exemplo, as cadeias ab e ba diferem por uma transposição adjacente sob Damerau–Levenshtein e por duas substituições sob Levenshtein simples.

Kitten versus sitting ainda custa três (como no exemplo de livro-texto de Levenshtein) porque o caminho mais barato usa substituições e uma inserção, não uma única troca. OSA é a forma que a maioria das bibliotecas rotula como Damerau–Levenshtein para correção de typos; proíbe aplicar duas transposições sobrepostas na mesma subcadeia, o que mantém a métrica simples e O(n·m) em tempo e espaço. Cadeias vazias são válidas: a distância da vazia a qualquer cadeia é o comprimento dessa cadeia, e a distância entre duas vazias é zero.

Cadeias idênticas sempre produzem distância zero e similaridade um, inclusive após o folding opcional de maiúsculas.

Onde essa distância faz diferença

Ferramentas de busca de produtos e inventário usam distância de edição com transposições para ranquear SKUs e marcas quase coincidentes antes de recorrer a modelos semânticos mais lentos. Pipelines de CRM e deduplicação marcam linhas candidatas a duplicata quando a distância é no máximo um ou dois e a similaridade fica acima de um limiar fixo, capturando letras trocadas que a igualdade simples ou mesmo a Levenshtein pura subestimariam.

Demos de corretor ortográfico e exercícios de sala precisam de um oráculo determinístico que marque form versus from como distância um e cobre uma taxa fixa transparente em vez de custo por tokens. Entrada inválida não consome saldo.

Combine a distância inteira com a sua própria política de limiar—aceite distância zero só para chaves exatas, distância um para correção agressiva de typos, similaridade acima de 0.8 para dicas de mescla suave—e você obtém um bloco auditável de correspondência difusa sem montar um motor de busca completo nem um stack de PLN próprio.