sketch_markov.nx source
↩ module page · 198 lines · 6231 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
28import "syscalls.nx"
29import "sketch_types.nx"
30
31const NX_MARKOV_MIN_N: i64 = 2
32const NX_MARKOV_MAX_N: i64 = 1024
33
34struct Markov {
35 counts: *i64, // N x N transition matrix, row-major
36 n_states: i64,
37 row_sums: *i64, // Σ_j t[i][j] for fast probability calc
38 last_state: i64, // for nx_markov_step convenience
39 has_prev: i64, // 0 if first observation, 1 otherwise
40 total_obs: i64,
41}
42
43// === construction =================================================
44
45func nx_markov_alloc(n_states: i64) -> *Markov {
46 if n_states < NX_MARKOV_MIN_N { return 0 as *Markov }
47 if n_states > NX_MARKOV_MAX_N { return 0 as *Markov }
48 let raw: *u8 = sys_mmap(56)
49 let m: *Markov = raw as *Markov
50 let cells: i64 = n_states * n_states
51 m.counts = sys_mmap(cells * 8) as *i64
52 m.row_sums = sys_mmap(n_states * 8) as *i64
53 var i: i64 = 0
54 while i < cells {
55 m.counts[i] = 0
56 i = i + 1
57 }
58 i = 0
59 while i < n_states {
60 m.row_sums[i] = 0
61 i = i + 1
62 }
63 m.n_states = n_states
64 m.last_state = -1
65 m.has_prev = 0
66 m.total_obs = 0
67 return m
68}
69
70// === cell access =================================================
71
72func nx_markov_cell_idx(m: *Markov, from: i64, to: i64) -> i64 {
73 return from * m.n_states + to
74}
75
76// === observe (explicit prev/next) =================================
77//
78// Direct transition observation: increment t[from][to].
79
80func nx_markov_observe(m: *Markov, from: i64, to: i64) -> i64 {
81 if from < 0 { return -1 }
82 if from >= m.n_states { return -1 }
83 if to < 0 { return -1 }
84 if to >= m.n_states { return -1 }
85 let idx: i64 = nx_markov_cell_idx(m, from, to)
86 m.counts[idx] = m.counts[idx] + 1
87 m.row_sums[from] = m.row_sums[from] + 1
88 m.total_obs = m.total_obs + 1
89 return 0
90}
91
92// === step (sequential streaming) ==================================
93//
94// Stream-friendly API: caller feeds states one at a time, primitive
95// internally tracks previous state. First call sets the seed without
96// recording a transition.
97
98func nx_markov_step(m: *Markov, state: i64) -> i64 {
99 if state < 0 { return -1 }
100 if state >= m.n_states { return -1 }
101 if m.has_prev == 1 {
102 nx_markov_observe(m, m.last_state, state)
103 }
104 m.last_state = state
105 m.has_prev = 1
106 return 0
107}
108
109// === probability query (PPM) ======================================
110
111func nx_markov_probability_ppm(m: *Markov, from: i64, to: i64) -> i64 {
112 if from < 0 { return 0 }
113 if from >= m.n_states { return 0 }
114 if to < 0 { return 0 }
115 if to >= m.n_states { return 0 }
116 let row_sum: i64 = m.row_sums[from]
117 if row_sum == 0 { return 0 }
118 let idx: i64 = nx_markov_cell_idx(m, from, to)
119 return (m.counts[idx] * 1000000) / row_sum
120}
121
122// === count query =================================================
123
124func nx_markov_count(m: *Markov, from: i64, to: i64) -> i64 {
125 if from < 0 { return 0 }
126 if from >= m.n_states { return 0 }
127 if to < 0 { return 0 }
128 if to >= m.n_states { return 0 }
129 let idx: i64 = nx_markov_cell_idx(m, from, to)
130 return m.counts[idx]
131}
132
133func nx_markov_row_sum(m: *Markov, from: i64) -> i64 {
134 if from < 0 { return 0 }
135 if from >= m.n_states { return 0 }
136 return m.row_sums[from]
137}
138
139// === most-likely-next prediction =================================
140//
141// Returns the state j with max t[from][j]. Tie-break: smallest j.
142// Returns -1 if from is an unobserved state.
143
144func nx_markov_predict(m: *Markov, from: i64) -> i64 {
145 if from < 0 { return -1 }
146 if from >= m.n_states { return -1 }
147 if m.row_sums[from] == 0 { return -1 }
148 var best: i64 = -1
149 var best_count: i64 = -1
150 var j: i64 = 0
151 while j < m.n_states {
152 let c: i64 = nx_markov_count(m, from, j)
153 if c > best_count {
154 best = j
155 best_count = c
156 }
157 j = j + 1
158 }
159 return best
160}
161
162// === typed envelope ==============================================
163
164func nx_markov_query_probability(m: *Markov, from: i64, to: i64) -> *ApproxI64 {
165 let p: i64 = nx_markov_probability_ppm(m, from, to)
166 return nx_approx_new(p, NX_ENV_ABS, 1,
167 1000000000,
168 NX_MATURITY_PRODUCTION,
169 NX_ADV_HONEST)
170}
171
172// === introspection ================================================
173
174func nx_markov_total(m: *Markov) -> i64 {
175 return m.total_obs
176}
177
178func nx_markov_memory_bytes(m: *Markov) -> i64 {
179 return 56 + m.n_states * m.n_states * 8 + m.n_states * 8
180}
181
182func nx_markov_reset(m: *Markov) -> i64 {
183 let cells: i64 = m.n_states * m.n_states
184 var i: i64 = 0
185 while i < cells {
186 m.counts[i] = 0
187 i = i + 1
188 }
189 i = 0
190 while i < m.n_states {
191 m.row_sums[i] = 0
192 i = i + 1
193 }
194 m.last_state = -1
195 m.has_prev = 0
196 m.total_obs = 0
197 return 0
198}