nx_collocation.nx source

1// nx_collocation.nx -- statistical association metrics for word pairs. 2// 3// First brick of the corpus-linguistics S-class substrate per cardinal 4// feedback-corpus-linguistics-s-class-substrate-sketch-engine-displacement. 5// Substrate goal: benchmark + exceed Sketch Engine on every measurable 6// axis, patent-clean, all NishiLang. 7// 8// === What this primitive answers ==================================== 9// 10// Given a co-occurrence count table (n_a, n_b, n_ab, n_total) — the 11// fundamental contingency-table summary of how often word A appears, 12// how often word B appears, how often they co-occur, and the corpus 13// size — emit the standard statistical association metrics: 14// 15// PMI Church & Hanks 1990 log2( p(a,b) / (p(a)*p(b)) ) 16// log-likelihood Dunning 1993 -2 * sum(O * ln(O/E)) 17// T-score Manning & Schütze (O - E) / sqrt(O) 18// log-Dice Rychly 2008 14 + log2( 2*n_ab / (n_a + n_b) ) 19// 20// All Q10 fixed-point. No f64. All patent-clean (public NLP literature 21// from 1990-2008). 22// 23// === Composition ==================================================== 24// 25// nx_essentials.log2_floor -- integer log2 used everywhere 26// nx_tier.nx -- nx_int aliases 27// 28// === Sealed-enum strength bands ==================================== 29// 30// Per dual-reading cardinal: every primitive emits BOTH a quantitative 31// Q10 number AND a qualitative sealed-enum band. Downstream tooling 32// consumes the band without re-deriving thresholds. 33// 34// genealogy_id: church_hanks_1990_pmi + dunning_1993_log_likelihood + 35// manning_schutze_1999_t_score + rychly_2008_log_dice + 36// firth_1957_collocations + halliday_1961_categories 37// lineage_id: nx_collocation_v1 38 39// nx_safety_envelope: 40// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 41// sil_target: SIL1 42// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 43// verdict: NOT_YET_EVALUATED 44 45import "nx_syscalls.nx" 46import "nx_tier.nx" 47import "nx_essentials.nx" 48const NX_MAGIC_20480: i64 = 20480 49const NX_MAGIC_14336: i64 = 14336 50 51const NX_COL_Q: nx_int = 1024 // Q10 fixed-point base 52 53// ===== Sealed-enum: strength bands ================================= 54// 55// Universal across all four metrics. Each metric has its own threshold 56// constants but the band names + ordering match. 57 58const NX_COL_BAND_NONE: nx_int = 0 // no association 59const NX_COL_BAND_WEAK: nx_int = 1 60const NX_COL_BAND_MODERATE: nx_int = 2 61const NX_COL_BAND_STRONG: nx_int = 3 62const NX_COL_BAND_VERY_STRONG: nx_int = 4 63const NX_COL_N_BANDS: nx_int = 5 64 65func nx_col_band_is_valid(b: nx_int) -> nx_int { 66 if b < 0 { return 0 } 67 if b >= NX_COL_N_BANDS { return 0 } 68 return 1 69} 70 71// ===== Sealed-enum: metric type ==================================== 72// 73// Lets a downstream caller request a specific metric or iterate over 74// all of them. 75 76const NX_COL_METRIC_PMI: nx_int = 0 77const NX_COL_METRIC_LOG_LIKELIHOOD: nx_int = 1 78const NX_COL_METRIC_T_SCORE: nx_int = 2 79const NX_COL_METRIC_LOG_DICE: nx_int = 3 80const NX_COL_N_METRICS: nx_int = 4 81 82func nx_col_metric_is_valid(m: nx_int) -> nx_int { 83 if m < 0 { return 0 } 84 if m >= NX_COL_N_METRICS { return 0 } 85 return 1 86} 87 88// ===== Internal: Q10 natural-log approximation ===================== 89// 90// ln(x) for integer x >= 1. Uses log2(x) * NX_LN2_Q20 / 2^10 — we 91// already have nx_log2_floor; combining with the constant ln(2) in 92// Q10 yields a workable ln(x). Approximation error < 5% for x in 93// [2, 2^32] which covers every realistic corpus frequency. 94// 95// Returns ln(x) in Q10. ln(1) = 0; ln(2) ≈ 0.693 → 710; ln(1024) ≈ 96// 6.93 → 7099. 97const NX_LN2_Q10: nx_int = 710 // 0.693147 * 1024 98 99func _col_ln_q10(x: nx_int) -> nx_int { 100 if x <= 0 { return 0 } 101 if x == 1 { return 0 } 102 let lg: nx_int = nx_log2_floor(x) 103 // log2(x) refined: log2_floor undercounts by up to 1 bit. Linear 104 // refinement using the bottom part: 105 // x = 2^lg + r where 0 <= r < 2^lg 106 // log2(x) ≈ lg + r/2^lg 107 // In Q10: refinement = (r * 1024) / 2^lg 108 var pow_lg: nx_int = 1 109 var i: nx_int = 0 110 while i < lg { pow_lg = pow_lg * 2; i = i + 1 } 111 let r: nx_int = x - pow_lg 112 var refine: nx_int = 0 113 if pow_lg > 0 { refine = (r * NX_COL_Q) / pow_lg } 114 let log2_q10: nx_int = lg * NX_COL_Q + refine 115 // ln = log2 * ln(2) -> Q10 multiply then divide by Q 116 return (log2_q10 * NX_LN2_Q10) / NX_COL_Q 117} 118 119// ===== Internal: Q10 log2 with linear refinement ==================== 120// 121// log2(x) in Q10. Same refinement as _col_ln_q10 but skipping the 122// ln(2) multiply. Useful for PMI + log-Dice which are defined in log2. 123 124func _col_log2_q10(x: nx_int) -> nx_int { 125 if x <= 0 { return 0 } 126 if x == 1 { return 0 } 127 let lg: nx_int = nx_log2_floor(x) 128 var pow_lg: nx_int = 1 129 var i: nx_int = 0 130 while i < lg { pow_lg = pow_lg * 2; i = i + 1 } 131 let r: nx_int = x - pow_lg 132 var refine: nx_int = 0 133 if pow_lg > 0 { refine = (r * NX_COL_Q) / pow_lg } 134 return lg * NX_COL_Q + refine 135} 136 137// ===== Internal: Newton-Raphson integer sqrt ======================= 138// 139// Used by T-score's sqrt(O) denominator. Returns floor(sqrt(n)) for 140// n >= 0. 141 142func _col_isqrt(n: nx_int) -> nx_int { 143 if n <= 0 { return 0 } 144 if n < 2 { return 1 } 145 var x: nx_int = n 146 var shift: nx_int = 0 147 while x > 0 { x = x / 2; shift = shift + 1 } 148 var r: nx_int = 1 149 var i: nx_int = 0 150 while i < (shift / 2 + 1) { r = r * 2; i = i + 1 } 151 var iter: nx_int = 0 152 while iter < 20 { 153 if r <= 0 { return 0 } 154 let next: nx_int = (r + n / r) / 2 155 if next >= r { return r } 156 r = next 157 iter = iter + 1 158 } 159 return r 160} 161 162// ===== Public: PMI in Q10 ========================================= 163// 164// Pointwise Mutual Information. Church & Hanks 1990. 165// 166// PMI(a, b) = log2( p(a,b) / (p(a) * p(b)) ) 167// = log2( N * n_ab / (n_a * n_b) ) 168// 169// where N = n_total. 170// 171// Returns Q10. 0 = independence; positive = association; negative = 172// repulsion. For typical corpora the practical range is roughly 173// [-10, +15] before bands saturate (so Q10 outputs roughly 174// [-10240, +15360]). 175// 176// Edge cases: 177// n_ab = 0 -> -inf substituted with sentinel NX_COL_PMI_FLOOR 178// n_a = 0 or n_b = 0 -> 0 (undefined; treat as no observation) 179 180// NishiLang consts must be plain literals (no compile-time arith). 181// PMI floor = -20.0 in Q10 = -20480. Exposed via getter. 182func nx_col_pmi_floor() -> nx_int { return 0 - NX_MAGIC_20480 } 183 184func nx_col_pmi_q10(n_a: nx_int, n_b: nx_int, 185 n_ab: nx_int, n_total: nx_int) -> nx_int { 186 if n_a <= 0 { return 0 } 187 if n_b <= 0 { return 0 } 188 if n_total <= 0 { return 0 } 189 if n_ab <= 0 { return nx_col_pmi_floor() } 190 // numerator = N * n_ab; denominator = n_a * n_b 191 // log2 of ratio = log2(N * n_ab) - log2(n_a * n_b) 192 // = log2(N) + log2(n_ab) - log2(n_a) - log2(n_b) 193 let log_N: nx_int = _col_log2_q10(n_total) 194 let log_ab: nx_int = _col_log2_q10(n_ab) 195 let log_a: nx_int = _col_log2_q10(n_a) 196 let log_b: nx_int = _col_log2_q10(n_b) 197 return log_N + log_ab - log_a - log_b 198} 199 200// PMI band thresholds in Q10. 201// PMI >= 6.0 -> VERY_STRONG (very rare elsewhere; idioms) 202// PMI >= 3.0 -> STRONG 203// PMI >= 1.0 -> MODERATE 204// PMI >= 0.0 -> WEAK 205// PMI < 0.0 -> NONE (or repulsion) 206 207const NX_COL_PMI_VERY_STRONG_Q10: nx_int = 6144 208const NX_COL_PMI_STRONG_Q10: nx_int = 3072 209const NX_COL_PMI_MODERATE_Q10: nx_int = 1024 210const NX_COL_PMI_WEAK_Q10: nx_int = 0 211 212func nx_col_pmi_band(pmi_q10: nx_int) -> nx_int { 213 if pmi_q10 >= NX_COL_PMI_VERY_STRONG_Q10 { return NX_COL_BAND_VERY_STRONG } 214 if pmi_q10 >= NX_COL_PMI_STRONG_Q10 { return NX_COL_BAND_STRONG } 215 if pmi_q10 >= NX_COL_PMI_MODERATE_Q10 { return NX_COL_BAND_MODERATE } 216 if pmi_q10 >= NX_COL_PMI_WEAK_Q10 { return NX_COL_BAND_WEAK } 217 return NX_COL_BAND_NONE 218} 219 220// ===== Public: log-likelihood in Q10 =============================== 221// 222// Dunning 1993. -2 * sum over 2x2 contingency table of O * ln(O/E). 223// More robust than PMI for low-frequency events. 224// 225// Contingency table for word A x word B in N-token corpus: 226// O11 = n_ab (a + b co-occur) 227// O12 = n_a - n_ab (a without b) 228// O21 = n_b - n_ab (b without a) 229// O22 = N - n_a - n_b + n_ab (neither) 230// 231// Expected: E_ij = (row_total * col_total) / N 232// E11 = n_a * n_b / N 233// E12 = n_a * (N - n_b) / N 234// E21 = (N - n_a) * n_b / N 235// E22 = (N - n_a) * (N - n_b) / N 236// 237// Returns Q10. Range typically [0, 1e6+] for strong associations in 238// large corpora; we clamp via the Q10 representation. 239 240func _col_ll_term(o: nx_int, e: nx_int) -> nx_int { 241 if o <= 0 { return 0 } // 0 * ln(0/e) = 0 by convention 242 if e <= 0 { return 0 } // skip degenerate cells 243 // O * ln(O/E) = O * (ln(O) - ln(E)) 244 let ln_o: nx_int = _col_ln_q10(o) 245 let ln_e: nx_int = _col_ln_q10(e) 246 let diff: nx_int = ln_o - ln_e 247 return o * diff // O is integer, diff is Q10 -> result is Q10 248} 249 250func nx_col_log_likelihood_q10(n_a: nx_int, n_b: nx_int, 251 n_ab: nx_int, n_total: nx_int) -> nx_int { 252 if n_total <= 0 { return 0 } 253 if n_a <= 0 { return 0 } 254 if n_b <= 0 { return 0 } 255 if n_ab < 0 { return 0 } 256 // Observed 257 let o11: nx_int = n_ab 258 let o12: nx_int = n_a - n_ab 259 let o21: nx_int = n_b - n_ab 260 let o22: nx_int = n_total - n_a - n_b + n_ab 261 // Expected 262 let e11: nx_int = (n_a * n_b) / n_total 263 let e12: nx_int = (n_a * (n_total - n_b)) / n_total 264 let e21: nx_int = ((n_total - n_a) * n_b) / n_total 265 let e22: nx_int = ((n_total - n_a) * (n_total - n_b)) / n_total 266 let s11: nx_int = _col_ll_term(o11, e11) 267 let s12: nx_int = _col_ll_term(o12, e12) 268 let s21: nx_int = _col_ll_term(o21, e21) 269 let s22: nx_int = _col_ll_term(o22, e22) 270 let s: nx_int = s11 + s12 + s21 + s22 271 // G² = 2 * Σ O · ln(O/E) (Dunning 1993) 272 // Non-negative by maximum-likelihood property; large when O ≠ E. 273 return 2 * s 274} 275 276// log-likelihood bands (Q10). Sketch Engine uses these thresholds for 277// statistical-significance roundtripping (Dunning 1993 critical values). 278// LL >= 30000 (~30 nats) -> VERY_STRONG (Pearson critical at p < 1e-7 for 1 df) 279// LL >= 15000 -> STRONG 280// LL >= 6000 -> MODERATE 281// LL >= 3000 -> WEAK 282// LL < 3000 -> NONE (not significant at p < 0.05) 283 284const NX_COL_LL_VERY_STRONG_Q10: nx_int = 30720 // ~30 285const NX_COL_LL_STRONG_Q10: nx_int = 15360 // ~15 286const NX_COL_LL_MODERATE_Q10: nx_int = 6144 // ~6 287const NX_COL_LL_WEAK_Q10: nx_int = 3072 // ~3 288 289func nx_col_log_likelihood_band(ll_q10: nx_int) -> nx_int { 290 if ll_q10 >= NX_COL_LL_VERY_STRONG_Q10 { return NX_COL_BAND_VERY_STRONG } 291 if ll_q10 >= NX_COL_LL_STRONG_Q10 { return NX_COL_BAND_STRONG } 292 if ll_q10 >= NX_COL_LL_MODERATE_Q10 { return NX_COL_BAND_MODERATE } 293 if ll_q10 >= NX_COL_LL_WEAK_Q10 { return NX_COL_BAND_WEAK } 294 return NX_COL_BAND_NONE 295} 296 297// ===== Public: T-score in Q10 ====================================== 298// 299// Manning & Schütze 1999. Compares observed to expected, normalised 300// by sqrt of observed. Useful for filtering low-frequency noise. 301// 302// T = (O11 - E11) / sqrt(O11) 303// 304// Returns Q10. Sketch Engine treats T >= 2.0 as moderate, T >= 4.0 305// as strong. 306 307func nx_col_t_score_q10(n_a: nx_int, n_b: nx_int, 308 n_ab: nx_int, n_total: nx_int) -> nx_int { 309 if n_total <= 0 { return 0 } 310 if n_a <= 0 { return 0 } 311 if n_b <= 0 { return 0 } 312 if n_ab <= 0 { return 0 } 313 let e11: nx_int = (n_a * n_b) / n_total 314 let diff: nx_int = n_ab - e11 // integer 315 let sqrt_o: nx_int = _col_isqrt(n_ab) 316 if sqrt_o <= 0 { return 0 } 317 // T = diff / sqrt_o, scaled to Q10 318 return (diff * NX_COL_Q) / sqrt_o 319} 320 321// T-score bands (Q10). 322// T >= 6.0 -> VERY_STRONG 323// T >= 4.0 -> STRONG 324// T >= 2.0 -> MODERATE 325// T >= 1.0 -> WEAK 326// T < 1.0 -> NONE 327 328const NX_COL_T_VERY_STRONG_Q10: nx_int = 6144 329const NX_COL_T_STRONG_Q10: nx_int = 4096 330const NX_COL_T_MODERATE_Q10: nx_int = 2048 331const NX_COL_T_WEAK_Q10: nx_int = 1024 332 333func nx_col_t_score_band(t_q10: nx_int) -> nx_int { 334 if t_q10 >= NX_COL_T_VERY_STRONG_Q10 { return NX_COL_BAND_VERY_STRONG } 335 if t_q10 >= NX_COL_T_STRONG_Q10 { return NX_COL_BAND_STRONG } 336 if t_q10 >= NX_COL_T_MODERATE_Q10 { return NX_COL_BAND_MODERATE } 337 if t_q10 >= NX_COL_T_WEAK_Q10 { return NX_COL_BAND_WEAK } 338 return NX_COL_BAND_NONE 339} 340 341// ===== Public: log-Dice in Q10 ===================================== 342// 343// Rychly 2008 (Sketch Engine's preferred metric — Sketch Engine's 344// own innovation for the FrameNet-style word sketch, but the FORMULA 345// itself is a simple log of the Dice coefficient, public math). 346// 347// logDice = 14 + log2( 2 * n_ab / (n_a + n_b) ) 348// 349// The +14 offset normalises the typical range to roughly [0, 14] 350// so most useful collocations appear in [5, 14] regardless of 351// corpus size. This is its key advantage over PMI (corpus-size- 352// independent) and over LL (better dynamic range). 353 354func nx_col_log_dice_q10(n_a: nx_int, n_b: nx_int, n_ab: nx_int) -> nx_int { 355 if n_a <= 0 { return 0 } 356 if n_b <= 0 { return 0 } 357 if n_ab <= 0 { return 0 } 358 // log2(2 * n_ab / (n_a + n_b)) 359 let num: nx_int = 2 * n_ab 360 let den: nx_int = n_a + n_b 361 if den <= 0 { return 0 } 362 // log2(num / den) = log2(num) - log2(den) 363 let log_num: nx_int = _col_log2_q10(num) 364 let log_den: nx_int = _col_log2_q10(den) 365 // 14 in Q10 = 14336 366 return NX_MAGIC_14336 + log_num - log_den 367} 368 369// log-Dice bands (Q10). Rychly's published thresholds: 370// logDice >= 10 -> VERY_STRONG (top collocations: "Bahasa Indonesia") 371// logDice >= 7 -> STRONG (idiomatic: "look forward") 372// logDice >= 4 -> MODERATE 373// logDice >= 1 -> WEAK 374// logDice < 1 -> NONE 375 376const NX_COL_DICE_VERY_STRONG_Q10: nx_int = 10240 377const NX_COL_DICE_STRONG_Q10: nx_int = 7168 378const NX_COL_DICE_MODERATE_Q10: nx_int = 4096 379const NX_COL_DICE_WEAK_Q10: nx_int = 1024 380 381func nx_col_log_dice_band(dice_q10: nx_int) -> nx_int { 382 if dice_q10 >= NX_COL_DICE_VERY_STRONG_Q10 { return NX_COL_BAND_VERY_STRONG } 383 if dice_q10 >= NX_COL_DICE_STRONG_Q10 { return NX_COL_BAND_STRONG } 384 if dice_q10 >= NX_COL_DICE_MODERATE_Q10 { return NX_COL_BAND_MODERATE } 385 if dice_q10 >= NX_COL_DICE_WEAK_Q10 { return NX_COL_BAND_WEAK } 386 return NX_COL_BAND_NONE 387} 388 389// ===== Composite: emit all four metrics into a buffer ============= 390// 391// Single call yields all four metrics + their bands, written into a 392// caller-supplied flat i64 buffer of length 8 (4 metric Q10 values 393// + 4 band sealed-enum values). Lets a downstream caller filter on 394// the band closest to their evaluation criterion. 395 396const NX_COL_OUT_PMI_Q10: nx_int = 0 397const NX_COL_OUT_LL_Q10: nx_int = 1 398const NX_COL_OUT_T_Q10: nx_int = 2 399const NX_COL_OUT_DICE_Q10: nx_int = 3 400const NX_COL_OUT_PMI_BAND: nx_int = 4 401const NX_COL_OUT_LL_BAND: nx_int = 5 402const NX_COL_OUT_T_BAND: nx_int = 6 403const NX_COL_OUT_DICE_BAND: nx_int = 7 404const NX_COL_OUT_FIELDS: nx_int = 8 405 406func nx_col_emit_all(n_a: nx_int, n_b: nx_int, n_ab: nx_int, n_total: nx_int, 407 out: *i64) -> nx_int { 408 let pmi: nx_int = nx_col_pmi_q10(n_a, n_b, n_ab, n_total) 409 let ll: nx_int = nx_col_log_likelihood_q10(n_a, n_b, n_ab, n_total) 410 let t: nx_int = nx_col_t_score_q10(n_a, n_b, n_ab, n_total) 411 let dice: nx_int = nx_col_log_dice_q10(n_a, n_b, n_ab) 412 out[NX_COL_OUT_PMI_Q10] = pmi 413 out[NX_COL_OUT_LL_Q10] = ll 414 out[NX_COL_OUT_T_Q10] = t 415 out[NX_COL_OUT_DICE_Q10] = dice 416 out[NX_COL_OUT_PMI_BAND] = nx_col_pmi_band(pmi) 417 out[NX_COL_OUT_LL_BAND] = nx_col_log_likelihood_band(ll) 418 out[NX_COL_OUT_T_BAND] = nx_col_t_score_band(t) 419 out[NX_COL_OUT_DICE_BAND] = nx_col_log_dice_band(dice) 420 return 0 421}