#![cfg_attr(not(test), no_std)]
#![forbid(unsafe_code)]
#![deny(missing_docs)]
use micromath::F32Ext;
type Word = u8;
type Rational = f32;
#[allow(clippy::let_and_return)]
pub fn shannon_entropy(word_slice: &[Word]) -> Rational {
debug_assert!((1usize) + (Word::max_value() as usize) <= usize::max_value());
debug_assert_eq!(Word::min_value(), 0);
let mut word_map = [0usize; (1usize) + (Word::max_value() as usize)];
for word in word_slice {
word_map[(*word) as usize] += 1;
}
let rat_len: Rational = word_slice.len() as Rational;
let log_div: Rational = F32Ext::ln(2.0 as Rational);
let en_sum = word_map
.iter()
.fold(0.0 as Rational, |acc, &freq| match freq {
0 => acc,
freq => {
let rat_freq: Rational = freq as Rational;
acc + (rat_freq * F32Ext::ln(rat_freq / rat_len))
}
});
let entropy = en_sum.abs() / (rat_len * log_div);
entropy
}
pub fn shannon_entropy_metric(word_slice: &[Word]) -> Rational {
shannon_entropy(word_slice) / (word_slice.len() as Rational)
}
#[cfg(test)]
mod tests {
use super::*;
const SIGMA: Rational = 10e-1;
const FRACT: Rational = 0.14;
#[test]
fn shannon_expected_value() {
let test_vectors = [
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 0, 1, 0, 1],
[0, 0, 1, 1, 2, 2, 3, 3],
[0, 0, 0, 1, 1, 2, 3, 4],
[1, 2, 3, 4, 5, 6, 7, 8],
];
let test_expect = [0.0, 0.0, 1.0, 2.0, 2.15563906, 3.0];
for i in 0..test_vectors.len() {
let e = test_expect[i];
let l = e - SIGMA;
let r = e + SIGMA;
let s_en = shannon_entropy(&test_vectors[i]);
let e_wid = f32::max(e, s_en) * FRACT;
dbg!(i, l, r, e_wid, e, s_en);
assert!(F32Ext::abs(f32::max(e, s_en) - f32::min(e, s_en)) <= e_wid);
assert!(l <= s_en);
assert!(r >= s_en);
assert!(s_en >= 0.0);
assert!(s_en <= 8.0);
}
}
#[test]
fn shannon_all_unique_bytes() {
let pattern = {
let mut bytes = [0u8; 256usize];
for i in 0..bytes.len() {
bytes[i] = i as u8;
}
bytes
};
let e = 8.0;
let l = e - SIGMA;
let r = e + SIGMA;
let s_en = shannon_entropy(&pattern);
let e_wid = f32::max(e, s_en) * FRACT;
dbg!(l, r, e_wid, e, s_en);
assert!(F32Ext::abs(f32::max(e, s_en) - f32::min(e, s_en)) <= e_wid);
assert!(l <= s_en);
assert!(r >= s_en);
assert!(s_en >= 0.0);
assert!(s_en <= 8.0);
}
#[test]
fn shannon_odd_slice_length() {
let pattern = [0, 0, 0, 0, 1, 1, 2, 2, 3, 4, 5];
let e = 2.04037339;
let l = e - SIGMA;
let r = e + SIGMA;
let s_en = shannon_entropy(&pattern);
let e_wid = f32::max(e, s_en) * FRACT;
dbg!(l, r, e_wid, e, s_en);
assert!(F32Ext::abs(f32::max(e, s_en) - f32::min(e, s_en)) <= e_wid);
assert!(l <= s_en);
assert!(r >= s_en);
assert!(s_en >= 0.0);
assert!(s_en <= 8.0);
}
#[test]
fn shannon_metric_odd_slice_length() {
let pattern = [0, 0, 0, 0, 1, 1, 2, 2, 3, 4, 5];
let e = 0.18548849;
let l = e - (SIGMA / pattern.len() as Rational);
let r = e + (SIGMA / pattern.len() as Rational);
let m_en = shannon_entropy_metric(&pattern);
let e_wid = f32::max(e, m_en) * FRACT;
dbg!(l, r, e_wid, e, m_en);
assert!(F32Ext::abs(f32::max(e, m_en) - f32::min(e, m_en)) <= e_wid);
assert!(l <= m_en);
assert!(r >= m_en);
assert!(m_en >= 0.0);
assert!(m_en <= 1.0);
}
}