nx_sketch_entropy.nx source
↩ module page · 134 lines · 4539 B
1// sketch_entropy.nx -- streaming Shannon entropy estimator.
2//
3// Maintains exact frequency counts via the sovereign hash-map primitive
4// (sketch_hash_map.nx), then computes entropy at query time:
5//
6// H = -Σ p_i log_2(p_i) bits
7// = log_2(N) - (Σ f_i log_2(f_i)) / N
8//
9// USE CASES:
10// - anomaly detection (sudden entropy drop = repetition spike)
11// - change-point detection (entropy distribution shift)
12// - feature extraction for ML over streams
13// - DDoS detection (low entropy = single-source flood)
14// - load-balancer fairness (high entropy = uniform distribution)
15//
16// EXACT WITHIN BOUNDED UNIVERSE: works for streams where distinct
17// keys fit in the hash map (bounded by caller-chosen capacity).
18// For unbounded universes, compose with CountSketch or SpaceSaving
19// for approximate frequencies first.
20//
21// INTEGER LOG-BASE-2 (no f64):
22// log_2(n) ≈ bitlen(n) - 1 (floor)
23// For finer resolution: use top-bit position + fractional bits via
24// mantissa interpolation. v1 uses floor(log_2) -- entropy under-
25// estimates by O(1/N) per term.
26//
27// LOSSLESS-LANGUAGE DISCIPLINE:
28// Returns entropy in PPM ([0, log_2(N) * 1_000_000]).
29// ApproxI64 with NX_ENV_ABS, param_a = n_distinct (quantization
30// bound from floor-log). Maturity = ReferenceImpl (Production
31// when we ship the precise log-fp lookup table).
32
33// nx_safety_envelope:
34// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
35// sil_target: SIL1
36// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
37// verdict: NOT_YET_EVALUATED
38
39import "nx_syscalls.nx"
40import "nx_sketch_hash_map.nx"
41import "nx_sketch_types.nx"
42
43struct StreamingEntropy {
44 counts: *HashMap,
45 n: i64, // total items observed
46}
47
48// === construction =================================================
49
50func nx_ent_alloc(capacity: i64) -> *StreamingEntropy {
51 let m: *HashMap = nx_hmap_alloc(capacity)
52 if m == (0 as *HashMap) { return 0 as *StreamingEntropy }
53 let raw: *u8 = sys_mmap(16)
54 let e: *StreamingEntropy = raw as *StreamingEntropy
55 e.counts = m
56 e.n = 0
57 return e
58}
59
60// === add ==========================================================
61
62func nx_ent_add(e: *StreamingEntropy, key: i64) -> i64 {
63 if key == 0 { return -1 } // hash-map sentinel
64 if key == -1 { return -1 }
65 let cur: i64 = nx_hmap_get(e.counts, key)
66 let r: i64 = nx_hmap_put(e.counts, key, cur + 1)
67 if r < 0 { return r }
68 e.n = e.n + 1
69 return 0
70}
71
72// === log_2 helper (floor) ========================================
73
74func nx_ent_log2_floor(x: i64) -> i64 {
75 if x <= 1 { return 0 }
76 var n: i64 = 0
77 var t: i64 = x
78 while t > 1 {
79 t = t >> 1
80 n = n + 1
81 }
82 return n
83}
84
85// === entropy in PPM (Shannon, log base 2) ========================
86//
87// H_ppm = log_2(N)_ppm - (Σ f_i * log_2(f_i)_ppm) / N
88// where log_2(x)_ppm = nx_ent_log2_floor(x) * 1_000_000
89// (PPM = parts per million = scale factor 10^6).
90
91func nx_ent_bits_ppm(e: *StreamingEntropy) -> i64 {
92 if e.n == 0 { return 0 }
93 if e.n == 1 { return 0 } // single observation: zero entropy
94 let log_n_ppm: i64 = nx_ent_log2_floor(e.n) * 1000000
95 // Iterate over hash-map entries; accumulate f * log_2(f) in PPM.
96 var sum_f_log_f_ppm: i64 = 0
97 var idx: i64 = nx_hmap_next(e.counts, 0)
98 while idx >= 0 {
99 let entry: *HashMapEntry = nx_hmap_entry_at(e.counts, idx)
100 let f: i64 = entry.value
101 if f > 0 {
102 let log_f: i64 = nx_ent_log2_floor(f)
103 sum_f_log_f_ppm = sum_f_log_f_ppm + f * log_f * 1000000
104 }
105 idx = nx_hmap_next(e.counts, idx + 1)
106 }
107 let mean_term_ppm: i64 = sum_f_log_f_ppm / e.n
108 return log_n_ppm - mean_term_ppm
109}
110
111// === number of distinct keys ====================================
112
113func nx_ent_n_distinct(e: *StreamingEntropy) -> i64 {
114 return nx_hmap_size(e.counts)
115}
116
117func nx_ent_n_total(e: *StreamingEntropy) -> i64 {
118 return e.n
119}
120
121// === typed envelope =============================================
122
123func nx_ent_query(e: *StreamingEntropy) -> *ApproxI64 {
124 let h: i64 = nx_ent_bits_ppm(e)
125 return nx_approx_new(h, NX_ENV_ABS,
126 nx_hmap_size(e.counts), // quant bound
127 1000000000,
128 NX_MATURITY_REFERENCE_IMPL,
129 NX_ADV_HONEST)
130}
131
132func nx_ent_memory_bytes(e: *StreamingEntropy) -> i64 {
133 return 16 + nx_hmap_memory_bytes(e.counts)
134}