nx_sketch_markov.nx source
↩ module page · 204 lines · 6290 B
1// sketch_markov.nx -- discrete-state Markov chain transition tracker.
2//
3// Streaming primitive for sequence modeling. Maintains transition
4// counts t[i][j] = number of times we saw state i followed by state j.
5// At query time, transition probabilities P[i][j] = t[i][j] / Σ_k t[i][k]
6// in PPM (parts per million).
7//
8// USE CASES:
9// - log-event sequence modeling (predict next event class)
10// - DNA / protein sequence analysis
11// - user-behavior modeling (page A -> page B transitions)
12// - failure-mode chains (state transitions toward outage)
13// - text generation (character / word n-grams via k-step extension)
14//
15// CAPABILITY:
16// - online learning: every observation updates state
17// - O(1) per observation
18// - O(N²) memory (N states); caller-bounded
19// - exact integer counts; probabilities in PPM at query time
20//
21// MOST-LIKELY-NEXT-STATE prediction:
22// nx_markov_predict(s) returns the j with max t[s][j]. When ties
23// exist, smallest j wins (deterministic).
24//
25// LOSSLESS-LANGUAGE DISCIPLINE: probabilities in PPM with NX_ENV_ABS
26// param_a = 1 (PPM quantization). Production tier.
27
28// nx_safety_envelope:
29// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
30// sil_target: SIL1
31// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
32// verdict: NOT_YET_EVALUATED
33
34import "nx_syscalls.nx"
35import "nx_sketch_types.nx"
36
37const NX_MARKOV_MIN_N: i64 = 2
38const NX_MARKOV_MAX_N: i64 = 1024
39
40struct Markov {
41 counts: *i64, // N x N transition matrix, row-major
42 n_states: i64,
43 row_sums: *i64, // Σ_j t[i][j] for fast probability calc
44 last_state: i64, // for nx_markov_step convenience
45 has_prev: i64, // 0 if first observation, 1 otherwise
46 total_obs: i64,
47}
48
49// === construction =================================================
50
51func nx_markov_alloc(n_states: i64) -> *Markov {
52 if n_states < NX_MARKOV_MIN_N { return 0 as *Markov }
53 if n_states > NX_MARKOV_MAX_N { return 0 as *Markov }
54 let raw: *u8 = sys_mmap(56)
55 let m: *Markov = raw as *Markov
56 let cells: i64 = n_states * n_states
57 m.counts = sys_mmap(cells * 8) as *i64
58 m.row_sums = sys_mmap(n_states * 8) as *i64
59 var i: i64 = 0
60 while i < cells {
61 m.counts[i] = 0
62 i = i + 1
63 }
64 i = 0
65 while i < n_states {
66 m.row_sums[i] = 0
67 i = i + 1
68 }
69 m.n_states = n_states
70 m.last_state = -1
71 m.has_prev = 0
72 m.total_obs = 0
73 return m
74}
75
76// === cell access =================================================
77
78func nx_markov_cell_idx(m: *Markov, from: i64, to: i64) -> i64 {
79 return from * m.n_states + to
80}
81
82// === observe (explicit prev/next) =================================
83//
84// Direct transition observation: increment t[from][to].
85
86func nx_markov_observe(m: *Markov, from: i64, to: i64) -> i64 {
87 if from < 0 { return -1 }
88 if from >= m.n_states { return -1 }
89 if to < 0 { return -1 }
90 if to >= m.n_states { return -1 }
91 let idx: i64 = nx_markov_cell_idx(m, from, to)
92 m.counts[idx] = m.counts[idx] + 1
93 m.row_sums[from] = m.row_sums[from] + 1
94 m.total_obs = m.total_obs + 1
95 return 0
96}
97
98// === step (sequential streaming) ==================================
99//
100// Stream-friendly API: caller feeds states one at a time, primitive
101// internally tracks previous state. First call sets the seed without
102// recording a transition.
103
104func nx_markov_step(m: *Markov, state: i64) -> i64 {
105 if state < 0 { return -1 }
106 if state >= m.n_states { return -1 }
107 if m.has_prev == 1 {
108 nx_markov_observe(m, m.last_state, state)
109 }
110 m.last_state = state
111 m.has_prev = 1
112 return 0
113}
114
115// === probability query (PPM) ======================================
116
117func nx_markov_probability_ppm(m: *Markov, from: i64, to: i64) -> i64 {
118 if from < 0 { return 0 }
119 if from >= m.n_states { return 0 }
120 if to < 0 { return 0 }
121 if to >= m.n_states { return 0 }
122 let row_sum: i64 = m.row_sums[from]
123 if row_sum == 0 { return 0 }
124 let idx: i64 = nx_markov_cell_idx(m, from, to)
125 return (m.counts[idx] * 1000000) / row_sum
126}
127
128// === count query =================================================
129
130func nx_markov_count(m: *Markov, from: i64, to: i64) -> i64 {
131 if from < 0 { return 0 }
132 if from >= m.n_states { return 0 }
133 if to < 0 { return 0 }
134 if to >= m.n_states { return 0 }
135 let idx: i64 = nx_markov_cell_idx(m, from, to)
136 return m.counts[idx]
137}
138
139func nx_markov_row_sum(m: *Markov, from: i64) -> i64 {
140 if from < 0 { return 0 }
141 if from >= m.n_states { return 0 }
142 return m.row_sums[from]
143}
144
145// === most-likely-next prediction =================================
146//
147// Returns the state j with max t[from][j]. Tie-break: smallest j.
148// Returns -1 if from is an unobserved state.
149
150func nx_markov_predict(m: *Markov, from: i64) -> i64 {
151 if from < 0 { return -1 }
152 if from >= m.n_states { return -1 }
153 if m.row_sums[from] == 0 { return -1 }
154 var best: i64 = -1
155 var best_count: i64 = -1
156 var j: i64 = 0
157 while j < m.n_states {
158 let c: i64 = nx_markov_count(m, from, j)
159 if c > best_count {
160 best = j
161 best_count = c
162 }
163 j = j + 1
164 }
165 return best
166}
167
168// === typed envelope ==============================================
169
170func nx_markov_query_probability(m: *Markov, from: i64, to: i64) -> *ApproxI64 {
171 let p: i64 = nx_markov_probability_ppm(m, from, to)
172 return nx_approx_new(p, NX_ENV_ABS, 1,
173 1000000000,
174 NX_MATURITY_PRODUCTION,
175 NX_ADV_HONEST)
176}
177
178// === introspection ================================================
179
180func nx_markov_total(m: *Markov) -> i64 {
181 return m.total_obs
182}
183
184func nx_markov_memory_bytes(m: *Markov) -> i64 {
185 return 56 + m.n_states * m.n_states * 8 + m.n_states * 8
186}
187
188func nx_markov_reset(m: *Markov) -> i64 {
189 let cells: i64 = m.n_states * m.n_states
190 var i: i64 = 0
191 while i < cells {
192 m.counts[i] = 0
193 i = i + 1
194 }
195 i = 0
196 while i < m.n_states {
197 m.row_sums[i] = 0
198 i = i + 1
199 }
200 m.last_state = -1
201 m.has_prev = 0
202 m.total_obs = 0
203 return 0
204}