nx_didyoumean.nx source
↩ module page · 310 lines · 15204 B
1// nx_didyoumean.nx -- SEARCH RUNG F4: THE DID-YOU-MEAN LINE, BUILT FROM THE INDEX'S OWN TERM DICTIONARY (2026-09-18).
2//
3// WHAT IT DECIDES. For each eligible word of a query, one question: is the word RARE in the index while a one-edit
4// neighbour of it is COMMON? When it is, the commonest such neighbour is offered in the word's place ("Did you mean
5// ...?"), every other byte of the query kept. It ranks, filters and rewrites nothing: the typed query is still the one
6// searched, and the line only offers the alternative.
7//
8// THE CANDIDATES ARE GENERATED, NOT SEARCHED FOR. The seg's zero-hit corrector (dss_correct_raw) walks the sorted run of
9// dictionary terms sharing the word's first byte and runs a bounded Levenshtein per entry -- the right shape for a
10// two-edit repair, and the reason it only runs when a query finds nothing: that run is a large slice of a multi-segment
11// dictionary. This lib asks the converse question. It writes out every string exactly ONE Damerau edit from the word --
12// deletion, adjacent transposition, substitution, insertion over the tokenizer's letter class -- and asks the dictionary
13// for each one's document frequency by EXACT lookup (ss_term_dcount, the sampled-window path the ranker's idf already
14// reads). The work is a function of the word's LENGTH and never of the dictionary's size, which is what lets it run on
15// queries that DO find results.
16//
17// EVERY BOUND IS DERIVED FROM THE RESOURCE IT DESCRIBES:
18// - THE EDIT BOUND comes from the word's length: an edit is admitted only while it leaves a strict majority of the typed
19// characters untouched (2 x edits < length). A two-letter word is never corrected; a word of three or more letters may
20// take the one edit this lib generates. Two-edit repairs stay where they already live, in the zero-result fallback
21// (dss_correct), unchanged.
22// - RARE and COMMON come from the index's own document-frequency scale, the one the ranker weighs terms by (nx_intlog
23// idf_q10). The widest idf the index can give any term is idf(N, 1). A word is RARE when its idf exceeds half that
24// span; a candidate is COMMON when its idf does not. That is the midpoint of the log-df scale -- df below, or at or
25// above, sqrt(N + 1) -- found without a square root and drawn from the LIVE document count N, so it moves with the
26// corpus. dym_mid names the value by bisecting the predicate itself, so the announced number and the decision agree.
27// - THE FIRST BYTE IS KEPT: the zero-hit corrector's documented choice, kept for the same determinism and because an
28// edit at position 0 is where a short rare word most often lands on an unrelated common one.
29// - THE WORK IS BOUNDED BY THE QUERY: at most `maxwords` words (the caller passes the ranker's own term cap), each
30// costing at most dym_lookup_bound(length) exact lookups, every one of them counted in the stats the caller publishes.
31// DOCUMENTED IMPRECISION -- the price of document frequency alone, with no query log and no context:
32// - a rare real word one edit from a far commoner real word draws a suggestion. The typed word's results are still
33// served, so this error costs one line of text and never a result.
34// - a misspelling that is itself common (df at or above the midpoint) is taken at its word.
35// - a slip in the FIRST letter is out of scope (uantum is not offered quantum), as it is for the incumbent corrector.
36// license_tier: ORIGINAL No hw writes (Rule 26). Read-only on the index.
37import "nx_seg_store.nx"
38import "nx_intlog.nx"
39
40const DYM_LOW_A: i64 = 97 // 'a' -- the edit alphabet is the tokenizer's lowercase letter class, a..z
41const DYM_LOW_Z: i64 = 122 // 'z'
42const DYM_UP_A: i64 = 65 // 'A'
43const DYM_UP_Z: i64 = 90 // 'Z'
44const DYM_CASE: i64 = 32 // 'a' - 'A'
45const DYM_DIG_0: i64 = 48 // '0'
46const DYM_DIG_9: i64 = 57 // '9'
47const DYM_HIGH: i64 = 128 // a byte of a multi-byte UTF-8 sequence: a word holding one is left as typed
48const DYM_COLON: i64 = 58 // site:host, inurl:frag -- an operator name, or the value bound to it
49const DYM_DOT: i64 = 46 // host labels (reddit.com)
50const DYM_SLASH: i64 = 47 // paths and the r/<name> idiom
51const DYM_EDIT: i64 = 1 // the neighbourhood this lib generates is exactly one edit wide
52const DYM_KEEP: i64 = 1 // edits start at byte 1: the first byte of the word is kept
53// the stats vector every caller publishes, one word per slot
54const DYM_ST_DOCS: i64 = 0 // N, the live document count the scale is drawn from
55const DYM_ST_MID: i64 = 1 // the smallest COMMON df on that scale (dym_mid)
56const DYM_ST_WORDS: i64 = 2 // eligible words examined
57const DYM_ST_RARE: i64 = 3 // of them, rare
58const DYM_ST_LOOKUPS: i64 = 4 // one-edit candidates looked up
59const DYM_ST_HELD: i64 = 5 // of them, held by the dictionary (df > 0)
60const DYM_ST_FIXED: i64 = 6 // words replaced in the suggestion
61const DYM_ST_US: i64 = 7 // microseconds this answer cost
62const DYM_ST_TDF: i64 = 8 // df of the last rare word examined
63const DYM_ST_CDF: i64 = 9 // df of its commonest neighbour (0 = the dictionary holds none)
64const DYM_ST_ABSTAIN: i64 = 10 // 1 = the dictionary could not be read or the answer did not fit: nothing is offered
65const DYM_ST_MEMO: i64 = 11 // set by a caller that answered from a memo; this lib always writes 0
66const DYM_ST_SLOTS: i64 = 12 // the vector's size: the slots above
67
68func dym_is_letter(c: i64) -> i64 {
69 if c >= DYM_LOW_A { if c <= DYM_LOW_Z { return 1 } }
70 if c >= DYM_UP_A { if c <= DYM_UP_Z { return 1 } }
71 return 0
72}
73func dym_is_wordbyte(c: i64) -> i64 {
74 if dym_is_letter(c) == 1 { return 1 }
75 if c >= DYM_DIG_0 { if c <= DYM_DIG_9 { return 1 } }
76 if c >= DYM_HIGH { return 1 }
77 return 0
78}
79// bytes that bind a word to an operator, a host or a path: such a word is not free text and is never corrected
80func dym_is_joiner(c: i64) -> i64 {
81 if c == DYM_COLON { return 1 }
82 if c == DYM_DOT { return 1 }
83 if c == DYM_SLASH { return 1 }
84 return 0
85}
86func dym_lower(c: i64) -> i64 {
87 if c >= DYM_UP_A { if c <= DYM_UP_Z { return c + DYM_CASE } }
88 return c
89}
90// the size of the edit alphabet
91func dym_letters() -> i64 { return DYM_LOW_Z - DYM_LOW_A + 1 }
92// THE EDIT BOUND FROM THE WORD'S LENGTH: the edits a word of n bytes may take, 0 or DYM_EDIT -- an edit is admitted
93// only while it leaves a strict majority of the typed characters untouched
94func dym_edits_allowed(n: i64) -> i64 {
95 if 2 * DYM_EDIT < n { return DYM_EDIT }
96 return 0
97}
98// the most lookups one word of n bytes can cost -- deletions, adjacent swaps, substitutions and insertions, all past the
99// kept first byte. The envelope the gate holds the counter to.
100func dym_lookup_bound(n: i64) -> i64 {
101 if dym_edits_allowed(n) == 0 { return 0 }
102 let l: i64 = dym_letters()
103 let m: i64 = n - DYM_KEEP
104 return m + (m - 1) + (l - 1) * m + l * (m + 1)
105}
106// RARE: idf above half the widest idf the index can assign, idf(N, 1). A word the dictionary does not hold is the
107// rarest a word can be.
108func dym_rare(bign: i64, df: i64) -> i64 {
109 if df <= 0 { return 1 }
110 if idf_q10(bign, df) * 2 > idf_q10(bign, 1) { return 1 }
111 return 0
112}
113// COMMON: held, and not rare -- the other side of the same midpoint
114func dym_common(bign: i64, df: i64) -> i64 {
115 if df <= 0 { return 0 }
116 if dym_rare(bign, df) == 1 { return 0 }
117 return 1
118}
119// the smallest COMMON df for a corpus of N documents (the midpoint, sqrt(N + 1) on the Q10 log scale), found by
120// bisecting the predicate itself, so the value every answer announces can never disagree with the decision
121func dym_mid(bign: i64) -> i64 {
122 var lo: i64 = 1
123 var hi: i64 = bign + 1
124 if hi < 1 { hi = 1 }
125 while lo < hi {
126 let m: i64 = (lo + hi) / 2
127 if dym_rare(bign, m) == 1 { lo = m + 1 } else { hi = m }
128 }
129 return lo
130}
131// one exact lookup; keeps the neighbour with the highest df, the FIRST seen on a tie, so the answer is a function of the
132// word and the dictionary alone
133func dym_consider(h: *i64, cand: *u8, cl: i64, bestdf: i64, best: *u8, st: *i64) -> i64 {
134 cand[cl] = 0 as u8
135 let df: i64 = ss_term_dcount(h, cand)
136 st[DYM_ST_LOOKUPS] = st[DYM_ST_LOOKUPS] + 1
137 if df < 0 { st[DYM_ST_ABSTAIN] = 1; return bestdf }
138 if df > 0 { st[DYM_ST_HELD] = st[DYM_ST_HELD] + 1 }
139 if df > bestdf {
140 var i: i64 = 0
141 while i <= cl { best[i] = cand[i]; i = i + 1 }
142 return df
143 }
144 return bestdf
145}
146// THE ONE-EDIT NEIGHBOURHOOD of t[0..n) past its first byte, every member looked up exactly. Returns the commonest
147// neighbour's df (0 = the dictionary holds none) and leaves that neighbour, NUL-terminated, in best. cand and best must
148// hold n + DYM_EDIT + 1 bytes.
149func dym_best_edit1(h: *i64, t: *u8, n: i64, cand: *u8, best: *u8, st: *i64) -> i64 {
150 var bestdf: i64 = 0
151 best[0] = 0 as u8
152 if dym_edits_allowed(n) == 0 { return 0 }
153 // deletions
154 var i: i64 = DYM_KEEP
155 while i < n {
156 var o: i64 = 0
157 var j: i64 = 0
158 while j < n { if j != i { cand[o] = t[j]; o = o + 1 } j = j + 1 }
159 bestdf = dym_consider(h, cand, o, bestdf, best, st)
160 i = i + 1
161 }
162 // adjacent swaps (a swap of two equal bytes is the word itself, not a neighbour)
163 i = DYM_KEEP
164 while i + 1 < n {
165 if t[i] != t[i + 1] {
166 var j2: i64 = 0
167 while j2 < n { cand[j2] = t[j2]; j2 = j2 + 1 }
168 cand[i] = t[i + 1]
169 cand[i + 1] = t[i]
170 bestdf = dym_consider(h, cand, n, bestdf, best, st)
171 }
172 i = i + 1
173 }
174 // substitutions
175 i = DYM_KEEP
176 while i < n {
177 var c: i64 = DYM_LOW_A
178 while c <= DYM_LOW_Z {
179 if c != (t[i] as i64) {
180 var j3: i64 = 0
181 while j3 < n { cand[j3] = t[j3]; j3 = j3 + 1 }
182 cand[i] = c as u8
183 bestdf = dym_consider(h, cand, n, bestdf, best, st)
184 }
185 c = c + 1
186 }
187 i = i + 1
188 }
189 // insertions before byte i (i == n appends)
190 i = DYM_KEEP
191 while i <= n {
192 var c2: i64 = DYM_LOW_A
193 while c2 <= DYM_LOW_Z {
194 var o2: i64 = 0
195 var j4: i64 = 0
196 while j4 < i { cand[o2] = t[j4]; o2 = o2 + 1; j4 = j4 + 1 }
197 cand[o2] = c2 as u8
198 o2 = o2 + 1
199 while j4 < n { cand[o2] = t[j4]; o2 = o2 + 1; j4 = j4 + 1 }
200 bestdf = dym_consider(h, cand, o2, bestdf, best, st)
201 c2 = c2 + 1
202 }
203 i = i + 1
204 }
205 return bestdf
206}
207// copy src[0..n) lower-cased into out at o, keeping room for the NUL; returns the new length, or -1 when it would not fit
208func dym_emit(out: *u8, o: i64, cap: i64, src: *u8, n: i64) -> i64 {
209 if o + n >= cap { return 0 - 1 }
210 var k: i64 = 0
211 while k < n { out[o + k] = dym_lower(src[k] as i64) as u8; k = k + 1 }
212 return o + n
213}
214// THE SUGGESTION FOR A WHOLE QUERY. Writes the query, lower-cased, with every rare free-text word replaced by its common
215// one-edit neighbour into out and returns its length. Returns 0 when nothing was replaced, when the dictionary could not
216// be read, or when the answer would not fit in outcap -- an abstention, never a truncated suggestion. st receives
217// DYM_ST_SLOTS words. The output is lower-cased whole so that it is a function of the case-folded query, which is
218// what a caller's memo keys on.
219func dym_suggest(h: *i64, q: *u8, qn: i64, maxwords: i64, out: *u8, outcap: i64, st: *i64) -> i64 {
220 var z: i64 = 0
221 while z < DYM_ST_SLOTS { st[z] = 0; z = z + 1 }
222 let t0: i64 = sys_now_us()
223 if outcap > 0 { out[0] = 0 as u8 }
224 if (h as i64) == 0 { st[DYM_ST_ABSTAIN] = 1; return 0 }
225 if qn <= 0 { return 0 }
226 let bign: i64 = ss_doc_count(h)
227 st[DYM_ST_DOCS] = bign
228 st[DYM_ST_MID] = dym_mid(bign)
229 // scratch sized from the query: no word is longer than the query, and a neighbour is DYM_EDIT byte longer plus a NUL
230 let scr: i64 = qn + DYM_EDIT + 1
231 let wbuf: *u8 = sys_mmap(scr)
232 let cand: *u8 = sys_mmap(scr)
233 let best: *u8 = sys_mmap(scr)
234 var o: i64 = 0
235 var fit: i64 = 1
236 var words: i64 = 0
237 var fixed: i64 = 0
238 var i: i64 = 0
239 while i < qn {
240 let c0: i64 = q[i] as i64
241 if dym_is_wordbyte(c0) == 0 {
242 if fit == 1 { let o1: i64 = dym_emit(out, o, outcap, (q as i64 + i) as *u8, 1); if o1 < 0 { fit = 0 } else { o = o1 } }
243 i = i + 1
244 } else {
245 var j: i64 = i
246 var letters: i64 = 1
247 var go: i64 = 1
248 while go == 1 {
249 if j >= qn { go = 0 } else {
250 let cj: i64 = q[j] as i64
251 if dym_is_wordbyte(cj) == 0 { go = 0 } else {
252 if dym_is_letter(cj) == 0 { letters = 0 }
253 j = j + 1
254 }
255 }
256 }
257 let wl: i64 = j - i
258 var elig: i64 = letters
259 if dym_edits_allowed(wl) == 0 { elig = 0 }
260 if words >= maxwords { elig = 0 }
261 if i > 0 { if dym_is_joiner(q[i - 1] as i64) == 1 { elig = 0 } }
262 if j < qn {
263 let nb: i64 = q[j] as i64
264 if nb == DYM_COLON { elig = 0 }
265 if dym_is_joiner(nb) == 1 { if j + 1 < qn { if dym_is_wordbyte(q[j + 1] as i64) == 1 { elig = 0 } } }
266 }
267 var took: i64 = 0
268 if elig == 1 {
269 words = words + 1
270 st[DYM_ST_WORDS] = st[DYM_ST_WORDS] + 1
271 var k: i64 = 0
272 while k < wl { wbuf[k] = dym_lower(q[i + k] as i64) as u8; k = k + 1 }
273 wbuf[wl] = 0 as u8
274 let tdf: i64 = ss_term_dcount(h, wbuf)
275 if tdf < 0 { st[DYM_ST_ABSTAIN] = 1 } else {
276 if dym_rare(bign, tdf) == 1 {
277 st[DYM_ST_RARE] = st[DYM_ST_RARE] + 1
278 st[DYM_ST_TDF] = tdf
279 let cdf: i64 = dym_best_edit1(h, wbuf, wl, cand, best, st)
280 st[DYM_ST_CDF] = cdf
281 if dym_common(bign, cdf) == 1 {
282 var bl: i64 = 0
283 while best[bl] != (0 as u8) { bl = bl + 1 }
284 if fit == 1 { let o2: i64 = dym_emit(out, o, outcap, best, bl); if o2 < 0 { fit = 0 } else { o = o2 } }
285 took = 1
286 fixed = fixed + 1
287 }
288 }
289 }
290 }
291 if took == 0 {
292 if fit == 1 { let o3: i64 = dym_emit(out, o, outcap, (q as i64 + i) as *u8, wl); if o3 < 0 { fit = 0 } else { o = o3 } }
293 }
294 i = j
295 }
296 }
297 sys_munmap(wbuf, scr)
298 sys_munmap(cand, scr)
299 sys_munmap(best, scr)
300 if fit == 0 { st[DYM_ST_ABSTAIN] = 1 }
301 if st[DYM_ST_ABSTAIN] == 1 { fixed = 0 }
302 st[DYM_ST_FIXED] = fixed
303 st[DYM_ST_US] = sys_now_us() - t0
304 if fixed == 0 {
305 if outcap > 0 { out[0] = 0 as u8 }
306 return 0
307 }
308 out[o] = 0 as u8
309 return o
310}