nx_damerau_levenshtein.nx source
↩ module page · 139 lines · 4629 B
1// nx_damerau_levenshtein.nx -- edit distance with adjacent transposition.
2//
3// Damerau-Levenshtein extends Levenshtein (insert / delete / substitute)
4// with a fourth edit operation: transposition of two ADJACENT
5// characters. Counts "ab" -> "ba" as one edit (Damerau 1964 found
6// 80% of human typos are one Damerau edit). Optimal-string-alignment
7// (restricted-Damerau) variant -- adjacent-only, no two-step
8// transpositions through previously-edited substrings.
9//
10// USE CASES:
11// - typo correction: "the" vs "teh" -> distance 1 (Damerau)
12// vs distance 2 (Levenshtein); much better fit for human errors
13// - identity name lookup: "Diora Baird" vs "Diroa Baird" -> 1
14// - prompt-token typo: "blonde" vs "blnode" -> 1
15//
16// Cross-modal: any byte sequence where adjacent-swap is a natural
17// edit (text, DNA where adjacent base swap is a known mutation).
18//
19// Wagner-Fischer DP O(m*n) time + O(m*n) space, with one extra DP
20// rule at each cell:
21// if i >= 2 AND j >= 2
22// AND s1[i-1] == s2[j-2] AND s1[i-2] == s2[j-1]:
23// dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)
24//
25// Idea-provenance: Damerau 1964 "A technique for computer detection
26// and correction of spelling errors" Communications of the ACM +
27// Levenshtein 1965 + Wagner-Fischer 1974. Papers only.
28//
29// genealogy_id: damerau_1964_typo_correction + levenshtein_1965 +
30// wagner_fischer_1974
31// lineage_id: damerau_levenshtein_q10
32
33// nx_safety_envelope:
34// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
35// sil_target: SIL1
36// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
37// verdict: NOT_YET_EVALUATED
38
39import "nx_syscalls.nx"
40import "nx_tier.nx"
41import "nx_jaro_winkler.nx"
42
43const NX_DLV_Q: nx_int = 1024
44
45// Helpers
46func _dlv_min2(a: nx_int, b: nx_int) -> nx_int {
47 if a < b { return a }
48 return b
49}
50
51func _dlv_min3(a: nx_int, b: nx_int, c: nx_int) -> nx_int {
52 var m: nx_int = a
53 if b < m { m = b }
54 if c < m { m = c }
55 return m
56}
57
58func _dlv_min4(a: nx_int, b: nx_int, c: nx_int, d: nx_int) -> nx_int {
59 var m: nx_int = a
60 if b < m { m = b }
61 if c < m { m = c }
62 if d < m { m = d }
63 return m
64}
65
66// ===== Damerau-Levenshtein DP (restricted variant) ==================
67
68func nx_damerau_levenshtein(s1: *u8, n1: nx_int, s2: *u8, n2: nx_int) -> nx_int {
69 if n1 == 0 { return n2 }
70 if n2 == 0 { return n1 }
71
72 let cols: nx_int = n2 + 1
73 let rows: nx_int = n1 + 1
74 let dp: *i64 = (sys_mmap(rows * cols * NX_SIZEOF_NX_INT)) as *i64
75
76 var j_init: nx_int = 0
77 while j_init <= n2 {
78 dp[j_init] = j_init
79 j_init = j_init + 1
80 }
81 var i_init: nx_int = 0
82 while i_init <= n1 {
83 dp[i_init * cols] = i_init
84 i_init = i_init + 1
85 }
86
87 var i: nx_int = 1
88 while i <= n1 {
89 var j: nx_int = 1
90 while j <= n2 {
91 var cost: nx_int = 1
92 if s1[i - 1] == s2[j - 1] { cost = 0 }
93 let del_cost: nx_int = dp[(i - 1) * cols + j] + 1
94 let ins_cost: nx_int = dp[i * cols + j - 1] + 1
95 let sub_cost: nx_int = dp[(i - 1) * cols + j - 1] + cost
96 var best: nx_int = _dlv_min3(del_cost, ins_cost, sub_cost)
97
98 // Adjacent transposition: only valid when both prev chars
99 // exist AND the cross-match holds.
100 if i >= 2 {
101 if j >= 2 {
102 if s1[i - 1] == s2[j - 2] {
103 if s1[i - 2] == s2[j - 1] {
104 let trans_cost: nx_int = dp[(i - 2) * cols + j - 2] + 1
105 if trans_cost < best { best = trans_cost }
106 }
107 }
108 }
109 }
110
111 dp[i * cols + j] = best
112 j = j + 1
113 }
114 i = i + 1
115 }
116 return dp[n1 * cols + n2]
117}
118
119// ===== Q10 similarity ===============================================
120
121func nx_damerau_levenshtein_similarity_q10(s1: *u8, n1: nx_int,
122 s2: *u8, n2: nx_int) -> nx_int {
123 if n1 == 0 {
124 if n2 == 0 { return NX_DLV_Q }
125 return 0
126 }
127 if n2 == 0 { return 0 }
128 let d: nx_int = nx_damerau_levenshtein(s1, n1, s2, n2)
129 var nmax: nx_int = n1
130 if n2 > nmax { nmax = n2 }
131 let asym: nx_int = (d * NX_DLV_Q) / nmax
132 if asym >= NX_DLV_Q { return 0 }
133 return NX_DLV_Q - asym
134}
135
136// Shared classifier (same NX_STRSIM_* bands as nx_jaro_winkler).
137func nx_damerau_levenshtein_classify(similarity_q10: nx_int) -> nx_int {
138 return nx_jaro_winkler_classify(similarity_q10)
139}