nx_term_cooccur.nx source
↩ module page · 329 lines · 11853 B
1// nx_term_cooccur.nx -- pairwise term co-occurrence counts.
2//
3// Tracks how often every (term_a, term_b) pair appears together
4// within the same beat (or, optionally, within the same scene).
5// Foundation for arc-anchor discovery: the most-common (OUTFIT +
6// LOCATION) pair in a corpus is a candidate "scene anchor" that
7// the director-initiative layer can surface as a recurring motif.
8//
9// Per cardinals:
10// feedback-self-surfacing-intelligence:
11// Counts are LIVE measurements; STAGE2 promotion of a pair to
12// an arc-anchor proposal happens at NX_COOCCUR_PROMOTE_N (5)
13// joint sightings with 0 user dismissals.
14// feedback-loras-and-negatives-are-patches:
15// Pure integer counts; no opaque embedding distance. Auditable.
16// feedback-user-owns-every-bit:
17// Snapshots to nishi-library only via explicit caller request.
18//
19// Storage: bounded open-addressing hash table keyed by the canonical
20// pair-key (term_a << 32 | term_b) with term_a < term_b enforced
21// at insertion. Cap defaults to 65536 pairs; caller sizes via
22// nx_cooccur_alloc_sized for larger corpora.
23//
24// nx_safety_envelope:
25// intended_use: "Pairwise co-occurrence counts of registered
26// terms within ingestion groupings (per-beat
27// or per-scene)."
28// sil_target: SIL2
29// asil_target: QM
30// dal_target: DAL C
31// iec_62304_class: NONE
32// evidence: [no_floating_point,
33// fixed_capacity_hash_table,
34// bounded_probe_length_per_jpl_rule_2,
35// canonical_pair_ordering_enforced,
36// counts_are_monotonic_non_decreasing]
37// hazard_register: [bug-tape-pair-key-hash-collision,
38// bug-tape-overflow-returns-error,
39// bug-tape-self-pair-silently-skipped]
40// residual_risk: "Open-addressing probe limit caps recall on
41// very dense hash collisions. Caller resizes
42// cap on overflow."
43// verdict: NOT_YET_EVALUATED
44
45import "nx_syscalls.nx"
46import "nx_storybeat.nx"
47import "nx_storydb.nx"
48import "nx_term_registry.nx"
49
50// ===== sealed grouping mode =======================================
51
52const NX_COOCCUR_GROUP_BEAT: i64 = 1
53const NX_COOCCUR_GROUP_SCENE: i64 = 2
54
55// ===== promotion threshold ========================================
56
57const NX_COOCCUR_PROMOTE_N: i64 = 5
58
59// ===== CooccurPair record =========================================
60
61struct CooccurPair {
62 pair_key: i64, // (term_a << 32) | term_b with a < b; 0 = empty
63 term_a: i64,
64 term_b: i64,
65 count: i64,
66 last_beat: i64,
67 flags: i64,
68}
69
70const NX_COOCCUR_PAIR_BYTES: i64 = 48
71
72// ===== Cooccur container ==========================================
73
74const NX_COOCCUR_DEFAULT_CAP: i64 = 65536
75const NX_COOCCUR_PROBE_LIMIT: i64 = 64
76const NX_COOCCUR_PER_GROUP_TERMS_MAX: i64 = 64
77
78struct Cooccur {
79 pairs: *CooccurPair,
80 cap: i64,
81 n_pairs: i64,
82}
83
84const NX_COOCCUR_BYTES: i64 = 24
85
86// ===== allocation =================================================
87
88func nx_cooccur_alloc_sized(cap: i64) -> *Cooccur {
89 var c: i64 = cap
90 if c <= 0 { c = NX_COOCCUR_DEFAULT_CAP }
91 let raw: *u8 = sys_mmap(NX_COOCCUR_BYTES)
92 let r: *Cooccur = raw as *Cooccur
93 r.pairs = (sys_mmap(c * NX_COOCCUR_PAIR_BYTES)) as *CooccurPair
94 r.cap = c
95 r.n_pairs = 0
96 return r
97}
98
99func nx_cooccur_alloc() -> *Cooccur {
100 return nx_cooccur_alloc_sized(0)
101}
102
103func nx_cooccur_pair_at(co: *Cooccur, i: i64) -> *CooccurPair {
104 return (((co.pairs as i64) + i * NX_COOCCUR_PAIR_BYTES) as *CooccurPair)
105}
106
107// ===== pair-key helpers ===========================================
108
109func nx_cooccur_make_key(a: i64, b: i64) -> i64 {
110 if a < b { return (a << 32) | (b & 0xFFFFFFFF) }
111 return (b << 32) | (a & 0xFFFFFFFF)
112}
113
114// Small mix to spread keys before modulo.
115func nx_cooccur_mix(k: i64) -> i64 {
116 var h: i64 = k
117 h = h ^ (h >> 33)
118 h = h * 0xff51afd7ed558ccd
119 h = h ^ (h >> 33)
120 h = h * 0xc4ceb9fe1a85ec53
121 h = h ^ (h >> 33)
122 return h
123}
124
125// ===== observe a pair =============================================
126//
127// Insert or increment (a, b) co-occurrence. Skips self-pairs.
128// Returns the slot index on success, or -1 on probe-overflow.
129
130func nx_cooccur_observe(co: *Cooccur, a: i64, b: i64,
131 beat_id: i64) -> i64 {
132 if a < 0 { return -1 }
133 if b < 0 { return -1 }
134 if a == b { return -1 }
135 let key: i64 = nx_cooccur_make_key(a, b)
136 let h: i64 = nx_cooccur_mix(key)
137 var start: i64 = h & 0x7FFFFFFFFFFFFFFF
138 let cap: i64 = co.cap
139 start = start - ((start / cap) * cap)
140 var probe: i64 = 0
141 while probe < NX_COOCCUR_PROBE_LIMIT {
142 let slot: i64 = (start + probe) - (((start + probe) / cap) * cap)
143 let p: *CooccurPair = nx_cooccur_pair_at(co, slot)
144 if p.pair_key == 0 {
145 // Fresh insert.
146 p.pair_key = key
147 if a < b { p.term_a = a; p.term_b = b }
148 if a >= b { p.term_a = b; p.term_b = a }
149 p.count = 1
150 p.last_beat = beat_id
151 p.flags = 0
152 co.n_pairs = co.n_pairs + 1
153 return slot
154 }
155 if p.pair_key == key {
156 p.count = p.count + 1
157 p.last_beat = beat_id
158 return slot
159 }
160 probe = probe + 1
161 }
162 return -1
163}
164
165// ===== per-beat / per-corpus observe ==============================
166//
167// Walks the candidates a caller has already collected for a beat
168// (typically the registry slot ids assigned during term-extract)
169// and emits every pairwise combination.
170
171func nx_cooccur_observe_group(co: *Cooccur, term_ids: *i64,
172 n_terms: i64, beat_id: i64) -> i64 {
173 if n_terms < 2 { return 0 }
174 var emitted: i64 = 0
175 let OUTER_BUDGET: i64 = n_terms + 1
176 var outer: i64 = 0
177 var i: i64 = 0
178 while i < n_terms {
179 if outer >= OUTER_BUDGET { return emitted }
180 let a: i64 = term_ids[i]
181 let INNER_BUDGET: i64 = n_terms + 1
182 var inner: i64 = 0
183 var j: i64 = i + 1
184 while j < n_terms {
185 if inner >= INNER_BUDGET { j = n_terms }
186 if j < n_terms {
187 let b: i64 = term_ids[j]
188 let slot: i64 = nx_cooccur_observe(co, a, b, beat_id)
189 if slot >= 0 { emitted = emitted + 1 }
190 j = j + 1
191 inner = inner + 1
192 }
193 }
194 i = i + 1
195 outer = outer + 1
196 }
197 return emitted
198}
199
200// ===== full-corpus walk ===========================================
201//
202// For each beat in db, gather the registry slot ids the beat
203// references (outfit_id, location_id, character_id) into a small
204// stack buffer and emit pairwise co-occurrences.
205//
206// V1: only the three primary beat-field slots are considered.
207// V2: nx_term_extract emits the full candidate list per beat and
208// we walk that for richer associations.
209
210func nx_cooccur_observe_db(co: *Cooccur, db: *StoryDb) -> i64 {
211 let stack_raw: *u8 = sys_mmap(NX_COOCCUR_PER_GROUP_TERMS_MAX * 8)
212 let stack: *i64 = stack_raw as *i64
213 var total: i64 = 0
214 let BUDGET: i64 = db.n_beats + 1
215 var iter: i64 = 0
216 var i: i64 = 0
217 while i < db.n_beats {
218 if iter >= BUDGET { return total }
219 let b: *StoryBeat = nx_storydb_beat_at(db, i)
220 var k: i64 = 0
221 if b.outfit_id > 0 { stack[k] = b.outfit_id; k = k + 1 }
222 if b.location_id > 0 { stack[k] = b.location_id; k = k + 1 }
223 if b.character_id > 0 { stack[k] = b.character_id; k = k + 1 }
224 if k >= 2 {
225 total = total + nx_cooccur_observe_group(co, stack, k, i)
226 }
227 i = i + 1
228 iter = iter + 1
229 }
230 return total
231}
232
233// ===== top-K query ================================================
234//
235// Caller passes a pre-allocated array of size K; we fill with the
236// K highest-count pairs (descending). Returns count filled. V1
237// implementation: O(n*K) linear scan -- good enough for cap <= 64k.
238
239func nx_cooccur_top_k(co: *Cooccur, out: *CooccurPair, k: i64) -> i64 {
240 if k <= 0 { return 0 }
241 // Zero out the output array.
242 var z: i64 = 0
243 while z < k {
244 let op: *CooccurPair =
245 (((out as i64) + z * NX_COOCCUR_PAIR_BYTES) as *CooccurPair)
246 op.pair_key = 0
247 op.term_a = 0
248 op.term_b = 0
249 op.count = 0
250 op.last_beat = 0
251 op.flags = 0
252 z = z + 1
253 }
254 var filled: i64 = 0
255 let BUDGET: i64 = co.cap + 1
256 var iter: i64 = 0
257 var i: i64 = 0
258 while i < co.cap {
259 if iter >= BUDGET { return filled }
260 let p: *CooccurPair = nx_cooccur_pair_at(co, i)
261 if p.pair_key != 0 {
262 // Find insertion point in out[0..filled] (descending by count).
263 var pos: i64 = filled
264 if filled >= k {
265 // Smallest tracked count is at out[k-1].
266 let tail: *CooccurPair =
267 (((out as i64) + (k - 1) * NX_COOCCUR_PAIR_BYTES) as *CooccurPair)
268 if p.count > tail.count { pos = k - 1 }
269 if p.count <= tail.count { pos = -1 }
270 }
271 if pos >= 0 {
272 // Walk back while out[pos-1].count < p.count.
273 let WALK_BUDGET: i64 = k + 1
274 var walk_iter: i64 = 0
275 var moving: i64 = 1
276 while moving == 1 {
277 if walk_iter >= WALK_BUDGET { moving = 0 }
278 if moving == 1 {
279 if pos == 0 { moving = 0 }
280 if moving == 1 {
281 let prev: *CooccurPair =
282 (((out as i64) + (pos - 1) * NX_COOCCUR_PAIR_BYTES)
283 as *CooccurPair)
284 if prev.count >= p.count { moving = 0 }
285 if moving == 1 { pos = pos - 1 }
286 }
287 }
288 walk_iter = walk_iter + 1
289 }
290 // Shift entries [pos..filled-1] right by one (within k).
291 var shift_end: i64 = filled
292 if shift_end >= k { shift_end = k - 1 }
293 var s: i64 = shift_end
294 let SHIFT_BUDGET: i64 = k + 1
295 var s_iter: i64 = 0
296 while s > pos {
297 if s_iter >= SHIFT_BUDGET { s = pos }
298 if s > pos {
299 let dst_p: *CooccurPair =
300 (((out as i64) + s * NX_COOCCUR_PAIR_BYTES) as *CooccurPair)
301 let src_p: *CooccurPair =
302 (((out as i64) + (s - 1) * NX_COOCCUR_PAIR_BYTES) as *CooccurPair)
303 dst_p.pair_key = src_p.pair_key
304 dst_p.term_a = src_p.term_a
305 dst_p.term_b = src_p.term_b
306 dst_p.count = src_p.count
307 dst_p.last_beat = src_p.last_beat
308 dst_p.flags = src_p.flags
309 s = s - 1
310 }
311 s_iter = s_iter + 1
312 }
313 // Write the new entry at pos.
314 let dst2: *CooccurPair =
315 (((out as i64) + pos * NX_COOCCUR_PAIR_BYTES) as *CooccurPair)
316 dst2.pair_key = p.pair_key
317 dst2.term_a = p.term_a
318 dst2.term_b = p.term_b
319 dst2.count = p.count
320 dst2.last_beat = p.last_beat
321 dst2.flags = p.flags
322 if filled < k { filled = filled + 1 }
323 }
324 }
325 i = i + 1
326 iter = iter + 1
327 }
328 return filled
329}