nx_ngram.nx source
↩ module page · 361 lines · 12741 B
1// nx_ngram.nx -- n-gram extraction + frequency + dispersion.
2//
3// Second brick of the corpus-linguistics S-class substrate per cardinal
4// feedback-corpus-linguistics-s-class-substrate-sketch-engine-displacement.
5//
6// === What this primitive answers ====================================
7//
8// Given a stream of token IDs and N (unigram / bigram / trigram / ...),
9// produce:
10// - extraction of every n-gram in the stream
11// - hash-interned IDs for each n-gram (FNV-1a over the token-ID sequence)
12// - frequency count per n-gram
13// - dispersion: how evenly the n-gram is distributed across the corpus
14// (Juilland's D — close to 1 = uniform, close to 0 = clumped)
15// - top-K most-frequent extraction
16//
17// === Composition ====================================================
18//
19// nx_string_ops.nx (nx_str_hash_fnv1a) -- token-sequence interning
20// nx_essentials.nx (nx_log2_floor) -- log2 for dispersion
21// nx_tier.nx -- nx_int alias
22//
23// === Sealed-enum frequency bands ====================================
24//
25// Per dual-reading cardinal: every primitive emits BOTH a quantitative
26// count AND a qualitative sealed-enum band derived from log-rank.
27// log2(freq) buckets:
28// 0..3 -> SINGLETON_RARE (hapax / once or twice)
29// 3..7 -> RARE (3-127)
30// 7..12 -> COMMON (128-4095)
31// 12.. -> VERY_COMMON (4096+)
32//
33// === Dispersion bands ===============================================
34//
35// Juilland's D in Q10:
36// 0..256 -> CLUMPED (very uneven; <25% uniform)
37// 256..614 -> MODERATELY_SPREAD
38// 614..870 -> WELL_SPREAD
39// 870..1024 -> EVEN
40//
41// genealogy_id: shannon_1948_entropy + juilland_1970_dispersion +
42// carroll_1972_d_metric + church_1988_ngram +
43// fowler_noll_vo_1991_hash
44// lineage_id: nx_ngram_v1
45
46// Import nx_string_ops transitively brings nx_essentials + nx_tier +
47// nx_syscalls. Direct re-import of those broke parse with "type nx_int
48// = i64" not accepted at top level — the import dedup canonicalises
49// paths but my direct imports + transitive imports may resolve to
50// distinct keys. Rely on the chain via nx_string_ops only.
51// nx_safety_envelope:
52// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
53// sil_target: SIL1
54// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
55// verdict: NOT_YET_EVALUATED
56
57import "nx_string_ops.nx"
58const NX_MAGIC_4096: i64 = 4096
59
60const NX_NG_Q: nx_int = 1024 // Q10 fixed-point base
61
62// ===== Sealed-enum: frequency band ===================================
63
64const NX_NG_FREQ_SINGLETON_RARE: nx_int = 0 // freq <= 7
65const NX_NG_FREQ_RARE: nx_int = 1 // 8..127
66const NX_NG_FREQ_COMMON: nx_int = 2 // 128..4095
67const NX_NG_FREQ_VERY_COMMON: nx_int = 3 // 4096+
68const NX_NG_FREQ_N_BANDS: nx_int = 4
69
70func nx_ng_freq_band_is_valid(b: nx_int) -> nx_int {
71 if b < 0 { return 0 }
72 if b >= NX_NG_FREQ_N_BANDS { return 0 }
73 return 1
74}
75
76func nx_ng_classify_freq(freq: nx_int) -> nx_int {
77 if freq < 8 { return NX_NG_FREQ_SINGLETON_RARE }
78 if freq < 128 { return NX_NG_FREQ_RARE }
79 if freq < NX_MAGIC_4096 { return NX_NG_FREQ_COMMON }
80 return NX_NG_FREQ_VERY_COMMON
81}
82
83// ===== Sealed-enum: dispersion band =================================
84
85const NX_NG_DISP_CLUMPED: nx_int = 0 // D < 0.25
86const NX_NG_DISP_MODERATELY_SPREAD: nx_int = 1 // D < 0.60
87const NX_NG_DISP_WELL_SPREAD: nx_int = 2 // D < 0.85
88const NX_NG_DISP_EVEN: nx_int = 3 // D >= 0.85
89const NX_NG_DISP_N_BANDS: nx_int = 4
90
91func nx_ng_disp_band_is_valid(b: nx_int) -> nx_int {
92 if b < 0 { return 0 }
93 if b >= NX_NG_DISP_N_BANDS { return 0 }
94 return 1
95}
96
97func nx_ng_classify_disp(d_q10: nx_int) -> nx_int {
98 if d_q10 < 256 { return NX_NG_DISP_CLUMPED }
99 if d_q10 < 614 { return NX_NG_DISP_MODERATELY_SPREAD }
100 if d_q10 < 870 { return NX_NG_DISP_WELL_SPREAD }
101 return NX_NG_DISP_EVEN
102}
103
104// ===== N-gram hash interning =========================================
105//
106// Each n-gram is a sequence of n token IDs (i64 each). We compute
107// FNV-1a over the byte representation of those IDs, giving a stable
108// i64 hash that serves as the n-gram's interned ID.
109//
110// Same n-gram in different corpus positions hashes to the same ID.
111// FNV-1a collisions are negligible for n_distinct < 2^32 (which
112// covers any human-readable corpus).
113//
114// The caller passes a *i64 buffer of token IDs and n (the n in n-gram).
115
116func nx_ng_hash(tokens: *i64, n: nx_int) -> nx_int {
117 // FNV-1a over the BYTES of the n token IDs. Each i64 is 8 bytes.
118 // We feed bytes from least-significant to most-significant per token.
119 var h: nx_int = nx_fnv1a_offset_basis()
120 var i: nx_int = 0
121 while i < n {
122 var tok: nx_int = tokens[i]
123 var bi: nx_int = 0
124 while bi < NX_SIZEOF_NX_INT {
125 let byte_val: nx_int = tok - (tok / 256) * 256
126 // Make positive byte regardless of sign of tok
127 var b: nx_int = byte_val
128 if b < 0 { b = b + 256 }
129 h = h ^ b
130 h = h * NX_FNV1A_PRIME
131 tok = tok / 256
132 bi = bi + 1
133 }
134 i = i + 1
135 }
136 return h
137}
138
139// ===== N-gram extraction =============================================
140//
141// Walk the token stream, emitting one n-gram hash per starting position.
142// Caller supplies token_stream buffer of length stream_len, plus an
143// output buffer of size (stream_len - n + 1) to receive hashes.
144//
145// Returns the number of n-grams extracted (or 0 if stream too short).
146
147func nx_ng_extract(stream: *i64, stream_len: nx_int, n: nx_int,
148 out_hashes: *i64) -> nx_int {
149 if stream_len < n { return 0 }
150 if n <= 0 { return 0 }
151 let n_grams: nx_int = stream_len - n + 1
152 var i: nx_int = 0
153 while i < n_grams {
154 // Build a temporary view: stream[i..i+n)
155 // Pass pointer-arithmetic via the per-token loop in nx_ng_hash;
156 // here we just feed the pointer (stream + i) directly.
157 var h: nx_int = nx_fnv1a_offset_basis()
158 var j: nx_int = 0
159 while j < n {
160 var tok: nx_int = stream[i + j]
161 var bi: nx_int = 0
162 while bi < NX_SIZEOF_NX_INT {
163 let byte_val: nx_int = tok - (tok / 256) * 256
164 var b: nx_int = byte_val
165 if b < 0 { b = b + 256 }
166 h = h ^ b
167 h = h * NX_FNV1A_PRIME
168 tok = tok / 256
169 bi = bi + 1
170 }
171 j = j + 1
172 }
173 out_hashes[i] = h
174 i = i + 1
175 }
176 return n_grams
177}
178
179// ===== Frequency counting with open-addressing hash table ==========
180//
181// Caller supplies:
182// hashes[n_hashes] -- n-gram hash IDs to count
183// table_keys[cap] -- output hash-table keys (parallel to counts)
184// table_counts[cap] -- output hash-table counts
185// cap -- table capacity (must be power of 2)
186//
187// Returns the number of distinct n-grams in the table.
188//
189// Empty slot sentinel: table_keys[slot] == 0 indicates unused. Because
190// FNV-1a output 0 is possible (vanishingly rare), we treat it as a
191// reserved sentinel; the one-in-2^64 collision is acceptable for v1.
192
193func nx_ng_count(hashes: *i64, n_hashes: nx_int,
194 table_keys: *i64, table_counts: *i64, cap: nx_int) -> nx_int {
195 // Zero the table
196 var i: nx_int = 0
197 while i < cap {
198 table_keys[i] = 0
199 table_counts[i] = 0
200 i = i + 1
201 }
202 let mask: nx_int = cap - 1 // assumes power-of-2 cap
203 var distinct: nx_int = 0
204 var h_idx: nx_int = 0
205 while h_idx < n_hashes {
206 let h: nx_int = hashes[h_idx]
207 var probe: nx_int = h & mask
208 // Linear-probe to find empty slot or matching key
209 var done: nx_int = 0
210 while done == 0 {
211 if table_keys[probe] == 0 {
212 // Empty slot — insert
213 table_keys[probe] = h
214 table_counts[probe] = 1
215 distinct = distinct + 1
216 done = 1
217 } else {
218 if table_keys[probe] == h {
219 // Match — increment
220 table_counts[probe] = table_counts[probe] + 1
221 done = 1
222 } else {
223 probe = (probe + 1) & mask
224 }
225 }
226 }
227 h_idx = h_idx + 1
228 }
229 return distinct
230}
231
232// ===== Lookup: get count for a hash ================================
233
234func nx_ng_lookup(h: nx_int,
235 table_keys: *i64, table_counts: *i64, cap: nx_int) -> nx_int {
236 if cap <= 0 { return 0 }
237 let mask: nx_int = cap - 1
238 var probe: nx_int = h & mask
239 var iter: nx_int = 0
240 while iter < cap {
241 if table_keys[probe] == 0 { return 0 }
242 if table_keys[probe] == h { return table_counts[probe] }
243 probe = (probe + 1) & mask
244 iter = iter + 1
245 }
246 return 0
247}
248
249// ===== Juilland's D dispersion (Q10) ==================================
250//
251// Standard corpus-dispersion measure (Juilland 1970, refined by Carroll 1972).
252// Given the n-gram's frequency in each of K corpus parts (parts[0..K)),
253// compute:
254// mean = total / K
255// sd = sqrt( Σ (parts[i] - mean)^2 / K )
256// cv = sd / mean (coefficient of variation)
257// D = 1 - cv / sqrt(K - 1)
258//
259// All in Q10. D in [0, 1024]; close to 1024 = uniform, close to 0 = clumped.
260//
261// Caller supplies the per-part counts.
262
263func _ng_isqrt(n: nx_int) -> nx_int {
264 if n <= 0 { return 0 }
265 if n < 2 { return 1 }
266 var x: nx_int = n
267 var shift: nx_int = 0
268 while x > 0 { x = x / 2; shift = shift + 1 }
269 var r: nx_int = 1
270 var i: nx_int = 0
271 while i < (shift / 2 + 1) { r = r * 2; i = i + 1 }
272 var iter: nx_int = 0
273 while iter < 20 {
274 if r <= 0 { return 0 }
275 let next: nx_int = (r + n / r) / 2
276 if next >= r { return r }
277 r = next
278 iter = iter + 1
279 }
280 return r
281}
282
283func nx_ng_dispersion_q10(parts: *i64, k: nx_int) -> nx_int {
284 if k <= 1 { return NX_NG_Q } // single part -> trivially "uniform"
285 var total: nx_int = 0
286 var i: nx_int = 0
287 while i < k {
288 total = total + parts[i]
289 i = i + 1
290 }
291 if total <= 0 { return 0 }
292 let mean: nx_int = total / k
293 if mean <= 0 { return 0 }
294 // Sum of squared deviations
295 var ssq: nx_int = 0
296 var j: nx_int = 0
297 while j < k {
298 let dev: nx_int = parts[j] - mean
299 ssq = ssq + dev * dev
300 j = j + 1
301 }
302 let variance: nx_int = ssq / k
303 let sd: nx_int = _ng_isqrt(variance)
304 // cv_q10 = (sd * Q) / mean
305 let cv_q10: nx_int = (sd * NX_NG_Q) / mean
306 // sqrt(K - 1) in Q10
307 let sqrt_k_minus_1_q10: nx_int = _ng_isqrt((k - 1) * NX_NG_Q * NX_NG_Q)
308 if sqrt_k_minus_1_q10 <= 0 { return NX_NG_Q }
309 // D = 1 - cv / sqrt(K - 1) ; in Q10: D = Q - (cv_q10 * Q / sqrt_k_minus_1_q10)
310 let frac_q10: nx_int = (cv_q10 * NX_NG_Q) / sqrt_k_minus_1_q10
311 var d: nx_int = NX_NG_Q - frac_q10
312 if d < 0 { d = 0 }
313 if d > NX_NG_Q { d = NX_NG_Q }
314 return d
315}
316
317// ===== Top-K extraction =============================================
318//
319// Walk the counts table; collect the K most-frequent n-grams.
320// Simple O(N*K) selection — fine for substrate use where K is small.
321// Caller supplies out_hashes[k] + out_counts[k] buffers.
322//
323// Returns the actual number collected (min(K, distinct n-grams)).
324
325func nx_ng_top_k(table_keys: *i64, table_counts: *i64, cap: nx_int,
326 k: nx_int,
327 out_hashes: *i64, out_counts: *i64) -> nx_int {
328 if k <= 0 { return 0 }
329 // Init out buffers to (0, 0)
330 var i: nx_int = 0
331 while i < k {
332 out_hashes[i] = 0
333 out_counts[i] = 0
334 i = i + 1
335 }
336 var collected: nx_int = 0
337 var ti: nx_int = 0
338 while ti < cap {
339 let h: nx_int = table_keys[ti]
340 let c: nx_int = table_counts[ti]
341 if h != 0 {
342 if c > 0 {
343 // Insert into out_* if greater than current min
344 // Find min slot in out_counts
345 var min_slot: nx_int = 0
346 var slot: nx_int = 1
347 while slot < k {
348 if out_counts[slot] < out_counts[min_slot] { min_slot = slot }
349 slot = slot + 1
350 }
351 if c > out_counts[min_slot] {
352 out_hashes[min_slot] = h
353 out_counts[min_slot] = c
354 if collected < k { collected = collected + 1 }
355 }
356 }
357 }
358 ti = ti + 1
359 }
360 return collected
361}