sketch_entropy.nx source
↩ module page · 128 lines · 4407 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
33import "syscalls.nx"
34import "sketch_hash_map.nx"
35import "sketch_types.nx"
36
37struct StreamingEntropy {
38 counts: *HashMap,
39 n: i64, // total items observed
40}
41
42// === construction =================================================
43
44func nx_ent_alloc(capacity: i64) -> *StreamingEntropy {
45 let m: *HashMap = nx_hmap_alloc(capacity)
46 if m == (0 as *HashMap) { return 0 as *StreamingEntropy }
47 let raw: *u8 = sys_mmap(16)
48 let e: *StreamingEntropy = raw as *StreamingEntropy
49 e.counts = m
50 e.n = 0
51 return e
52}
53
54// === add ==========================================================
55
56func nx_ent_add(e: *StreamingEntropy, key: i64) -> i64 {
57 if key == 0 { return -1 } // hash-map sentinel
58 if key == -1 { return -1 }
59 let cur: i64 = nx_hmap_get(e.counts, key)
60 let r: i64 = nx_hmap_put(e.counts, key, cur + 1)
61 if r < 0 { return r }
62 e.n = e.n + 1
63 return 0
64}
65
66// === log_2 helper (floor) ========================================
67
68func nx_ent_log2_floor(x: i64) -> i64 {
69 if x <= 1 { return 0 }
70 var n: i64 = 0
71 var t: i64 = x
72 while t > 1 {
73 t = t >> 1
74 n = n + 1
75 }
76 return n
77}
78
79// === entropy in PPM (Shannon, log base 2) ========================
80//
81// H_ppm = log_2(N)_ppm - (Σ f_i * log_2(f_i)_ppm) / N
82// where log_2(x)_ppm = nx_ent_log2_floor(x) * 1_000_000
83// (PPM = parts per million = scale factor 10^6).
84
85func nx_ent_bits_ppm(e: *StreamingEntropy) -> i64 {
86 if e.n == 0 { return 0 }
87 if e.n == 1 { return 0 } // single observation: zero entropy
88 let log_n_ppm: i64 = nx_ent_log2_floor(e.n) * 1000000
89 // Iterate over hash-map entries; accumulate f * log_2(f) in PPM.
90 var sum_f_log_f_ppm: i64 = 0
91 var idx: i64 = nx_hmap_next(e.counts, 0)
92 while idx >= 0 {
93 let entry: *HashMapEntry = nx_hmap_entry_at(e.counts, idx)
94 let f: i64 = entry.value
95 if f > 0 {
96 let log_f: i64 = nx_ent_log2_floor(f)
97 sum_f_log_f_ppm = sum_f_log_f_ppm + f * log_f * 1000000
98 }
99 idx = nx_hmap_next(e.counts, idx + 1)
100 }
101 let mean_term_ppm: i64 = sum_f_log_f_ppm / e.n
102 return log_n_ppm - mean_term_ppm
103}
104
105// === number of distinct keys ====================================
106
107func nx_ent_n_distinct(e: *StreamingEntropy) -> i64 {
108 return nx_hmap_size(e.counts)
109}
110
111func nx_ent_n_total(e: *StreamingEntropy) -> i64 {
112 return e.n
113}
114
115// === typed envelope =============================================
116
117func nx_ent_query(e: *StreamingEntropy) -> *ApproxI64 {
118 let h: i64 = nx_ent_bits_ppm(e)
119 return nx_approx_new(h, NX_ENV_ABS,
120 nx_hmap_size(e.counts), // quant bound
121 1000000000,
122 NX_MATURITY_REFERENCE_IMPL,
123 NX_ADV_HONEST)
124}
125
126func nx_ent_memory_bytes(e: *StreamingEntropy) -> i64 {
127 return 16 + nx_hmap_memory_bytes(e.counts)
128}