Distanza Damerau–Levenshtein

La distanza di Damerau–Levenshtein è una metrica classica di edit distance che conta quante operazioni su un singolo carattere trasformano una stringa in un’altra quando le operazioni consentite sono inserimento, cancellazione, sostituzione e trasposizione di due caratteri adiacenti. Quest’ultima operazione la distingue dalla distanza di Levenshtein semplice e la rende particolarmente utile per i refusi reali: le persone scambiano spesso due tasti vicini (form contro from, teh contro the) e ciò deve costare un passo, non due sostituzioni. Questa capacità implementa la forma Optimal String Alignment della distanza con una tabella pura di programmazione dinamica, così ogni coppia di input produce lo stesso intero su ogni runtime. Lei invia due testi e un flag opzionale di sensibilità al maiuscolo; riceve la distanza, entrambe le lunghezze, una similarità normalizzata tra zero e uno, e un booleano identical.

Cosa misura Damerau–Levenshtein e come differisce da Levenshtein semplice

La distanza di edit chiede quanti cambiamenti unitari servono per riscrivere una stringa sorgente come stringa destinazione. La Levenshtein classica consente tre operazioni unitarie: inserire un carattere, cancellare un carattere o sostituire un carattere con un altro. Ognuna costa uno.

L’estensione di Damerau aggiunge una quarta operazione: scambiare due caratteri adiacenti per un solo costo unitario. Questa estensione rispecchia come si sbaglia davvero a digitare sulla tastiera. Ad esempio, le stringhe ab e ba differiscono di una trasposizione adiacente sotto Damerau–Levenshtein e di due sostituzioni sotto Levenshtein semplice.

Kitten contro sitting costa ancora tre (come nell’esempio da manuale di Levenshtein) perché il percorso più economico usa sostituzioni e un inserimento piuttosto che un solo scambio. OSA è la forma che la maggior parte delle librerie chiama Damerau–Levenshtein per la correzione dei refusi; vieta di applicare due trasposizioni sovrapposte sulla stessa sottostringa, mantenendo la metrica semplice e O(n·m) in tempo e spazio. Le stringhe vuote sono valide: la distanza dalla stringa vuota a qualsiasi stringa è la lunghezza di quella stringa, e la distanza tra due vuote è zero.

Stringhe identiche danno sempre distanza zero e similarità uno, anche dopo il folding opzionale del maiuscolo.

Dove questa distanza si rivela utile

Gli strumenti di ricerca prodotto e inventario usano la distanza di edit con trasposizioni per ordinare SKU e marchi quasi coincidenti prima di ricorrere a modelli semantici più lenti. Le pipeline CRM e di deduplicazione segnalano righe candidate a duplicato quando la distanza è al massimo uno o due e la similarità supera una soglia fissa, catturando lettere scambiate che l’uguaglianza pura o anche la Levenshtein semplice sottovaluterebbero.

Le demo di correttore ortografico e gli esercizi in aula necessitano di un oracolo deterministico che segni form contro from come distanza uno e addebiti una tariffa fissa trasparente anziché un costo a token. L’input non valido non consuma saldo. Abbini la distanza intera alla propria politica di soglia—accetti distanza zero solo per chiavi esatte, distanza uno per correzione aggressiva dei refusi, similarità sopra 0.8 per indizi di unione soft—e ottenga un blocco verificabile di abbinamento fuzzy senza erigere un motore di ricerca completo né uno stack NLP proprio.