nx_damerau_levenshtein.nx

nx_damerau_levenshtein.nx -- edit distance with adjacent transposition. Damerau-Levenshtein extends Levenshtein (insert / delete / substitute) with a fourth edit operation: transposition of two ADJACENT characters. Counts "ab" -> "ba" as one edit (Damerau 1964 found 80% of human typos are one Damerau edit). Optimal-string-alignment (restricted-Damerau) variant -- adjacent-only, no two-step transpositions through previously-edited substrings. USE CASES: - typo correction: "the" vs "teh" -> distance 1 (Damerau) vs distance 2 (Levenshtein); much better fit for human errors - identity name lookup: "Diora Baird" vs "Diroa Baird" -> 1 - prompt-token typo: "blonde" vs "blnode" -> 1 Cross-modal: any byte sequence where adjacent-swap is a natural edit (text, DNA where adjacent base swap is a known mutation). Wagner-Fischer DP O(m*n) time + O(m*n) space, with one extra DP rule at each cell: if i >= 2 AND j >= 2 AND s1[i-1] == s2[j-2] AND s1[i-2] == s2[j-1]: dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) Idea-provenance: Damerau 1964 "A technique for computer detection and correction of spelling errors" Communications of the ACM + Levenshtein 1965 + Wagner-Fischer 1974. Papers only. genealogy_id: damerau_1964_typo_correction + levenshtein_1965 + wagner_fischer_1974 lineage_id: damerau_levenshtein_q10