nx_jaro_winkler.nx source
↩ module page · 160 lines · 5476 B
1// nx_jaro_winkler.nx -- Jaro-Winkler string-similarity primitive.
2//
3// Operates on byte buffers. For ASCII / UTF-8 byte-by-byte matching;
4// caller normalizes case / Unicode beforehand if needed.
5//
6// USE CASES (image-gen prompting + general):
7// - Prompt deduplication: "blonde girl, beach" vs "blonde girl on
8// beach" near-IDENTICAL -> reuse cached render.
9// - Identity-name fuzzy lookup: "Diora-Baird" vs "diora baird".
10// - Caption-vs-prompt alignment (failure_attribution L2 signal).
11// - Typo correction: nearest match across a small candidate set.
12// - Prompt clustering for recommendation (pairwise Q10 grid).
13//
14// Algorithm:
15// matching window w = max(|s1|, |s2|) / 2 - 1
16// m = #chars in s1 found in s2 within +/- w positions (each char used once)
17// t = #matched-pairs in different order, halved
18// Jaro = (m/|s1| + m/|s2| + (m - t)/m) / 3
19// L = common prefix length, clamped at NX_JW_PREFIX_MAX (= 4)
20// p = 0.1 (Winkler 1990 canonical)
21// Jaro-Winkler = Jaro + L * p * (1 - Jaro)
22//
23// All math Q10. Output in [0, Q10]. Idea-provenance: Jaro 1989,
24// Winkler 1990, Cohen-Ravikumar-Fienberg 2003 secondstring survey
25// (papers; no code referenced -- patent-clean-absorption discipline).
26//
27// genealogy_id: jaro_1989_advances + winkler_1990_string_comparator +
28// cohen_ravikumar_fienberg_2003_secondstring_survey
29// lineage_id: jaro_winkler_q10
30
31// nx_safety_envelope:
32// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
33// sil_target: SIL1
34// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
35// verdict: NOT_YET_EVALUATED
36
37import "nx_syscalls.nx"
38import "nx_tier.nx"
39
40const NX_JW_Q: nx_int = 1024
41const NX_JW_PREFIX_MAX: nx_int = 4
42// Winkler scaling p = 0.1 -> Q10 = 102.
43const NX_JW_PREFIX_SCALE_Q10: nx_int = 102
44
45const NX_STRSIM_DISTINCT: nx_int = 0
46const NX_STRSIM_LOOSE_MATCH: nx_int = 1
47const NX_STRSIM_MATCH: nx_int = 2
48const NX_STRSIM_NEAR_DUPLICATE: nx_int = 3
49const NX_STRSIM_IDENTICAL: nx_int = 4
50const NX_STRSIM_N_BANDS: nx_int = 5
51
52// ===== Common-prefix length, clamped at NX_JW_PREFIX_MAX ==============
53
54func _jw_common_prefix(s1: *u8, n1: nx_int, s2: *u8, n2: nx_int) -> nx_int {
55 var lim: nx_int = NX_JW_PREFIX_MAX
56 if n1 < lim { lim = n1 }
57 if n2 < lim { lim = n2 }
58 var i: nx_int = 0
59 while i < lim {
60 if s1[i] != s2[i] { return i }
61 i = i + 1
62 }
63 return lim
64}
65
66// ===== Jaro-Winkler =================================================
67
68func nx_jaro_winkler(s1: *u8, n1: nx_int, s2: *u8, n2: nx_int) -> nx_int {
69 if n1 == 0 {
70 if n2 == 0 { return NX_JW_Q }
71 return 0
72 }
73 if n2 == 0 { return 0 }
74
75 var nmax: nx_int = n1
76 if n2 > nmax { nmax = n2 }
77 var window: nx_int = nmax / 2 - 1
78 if window < 0 { window = 0 }
79
80 // mark1 / mark2 are zero-initialized by sys_mmap.
81 let mark1: *u8 = sys_mmap(n1)
82 let mark2: *u8 = sys_mmap(n2)
83
84 // Pass 1: count matches within +/- window.
85 var matches: nx_int = 0
86 var i: nx_int = 0
87 while i < n1 {
88 var lo: nx_int = i - window
89 if lo < 0 { lo = 0 }
90 var hi: nx_int = i + window + 1
91 if hi > n2 { hi = n2 }
92 var j: nx_int = lo
93 while j < hi {
94 if mark2[j] == 0 {
95 if s1[i] == s2[j] {
96 mark1[i] = 1
97 mark2[j] = 1
98 matches = matches + 1
99 break
100 }
101 }
102 j = j + 1
103 }
104 i = i + 1
105 }
106
107 if matches == 0 { return 0 }
108
109 // Pass 2: count transpositions. Walk matched chars of s1 in order;
110 // pair each with the next matched char of s2 in order. Mismatch
111 // count is the (double-counted) transposition tally.
112 var transpositions: nx_int = 0
113 var k: nx_int = 0
114 var ii: nx_int = 0
115 while ii < n1 {
116 if mark1[ii] == 1 {
117 // Advance k to the next matched position in s2.
118 while k < n2 {
119 if mark2[k] == 1 { break }
120 k = k + 1
121 }
122 if s1[ii] != s2[k] { transpositions = transpositions + 1 }
123 k = k + 1
124 }
125 ii = ii + 1
126 }
127 let t_half: nx_int = transpositions / 2
128
129 // Jaro = (m/n1 + m/n2 + (m - t/2)/m) / 3, all in Q10.
130 let p1: nx_int = (matches * NX_JW_Q) / n1
131 let p2: nx_int = (matches * NX_JW_Q) / n2
132 let p3: nx_int = ((matches - t_half) * NX_JW_Q) / matches
133 let jaro_q10: nx_int = (p1 + p2 + p3) / 3
134
135 // Winkler bonus: + L * p * (1 - Jaro).
136 // Q10 math: bonus = L * p_q10 * (Q - jaro_q10) / Q.
137 let L: nx_int = _jw_common_prefix(s1, n1, s2, n2)
138 let bonus: nx_int = (L * NX_JW_PREFIX_SCALE_Q10 * (NX_JW_Q - jaro_q10)) / NX_JW_Q
139
140 var jw_q10: nx_int = jaro_q10 + bonus
141 if jw_q10 > NX_JW_Q { jw_q10 = NX_JW_Q }
142 if jw_q10 < 0 { jw_q10 = 0 }
143 return jw_q10
144}
145
146// ===== Qualitative classifier (dual-reading) ========================
147
148func nx_jaro_winkler_classify(similarity_q10: nx_int) -> nx_int {
149 if similarity_q10 < 256 { return NX_STRSIM_DISTINCT }
150 if similarity_q10 < 512 { return NX_STRSIM_LOOSE_MATCH }
151 if similarity_q10 < 768 { return NX_STRSIM_MATCH }
152 if similarity_q10 < 921 { return NX_STRSIM_NEAR_DUPLICATE }
153 return NX_STRSIM_IDENTICAL
154}
155
156func nx_strsim_band_is_valid(band: nx_int) -> nx_int {
157 if band < 0 { return 0 }
158 if band >= NX_STRSIM_N_BANDS { return 0 }
159 return 1
160}