1use std::f64::consts::LN_2;
33
34use crate::config::Estimator;
35use crate::error::{DimaError, Result};
36use crate::model::{EntropyFallback, EntropyMethod};
37use crate::numeric::{Neumaier, binomial_walk, digamma_difference, lerch_phi1, ols_intercept};
38
39pub const RAREFACTION_MIN_POINTS: usize = 5;
42pub const RAREFACTION_START: u64 = 50;
44pub const RAREFACTION_STEP: u64 = 5;
47
48#[derive(Clone, Debug, PartialEq, Eq)]
50pub struct CountProfile {
51 support: u64,
52 distinct: u64,
53 frequencies: Vec<(u64, u64)>,
55}
56
57impl CountProfile {
58 pub fn from_counts(counts: impl IntoIterator<Item = u64>) -> Result<Self> {
63 let mut v: Vec<u64> = counts.into_iter().filter(|&c| c > 0).collect();
64 v.sort_unstable();
65 let mut support = 0u64;
66 let mut frequencies: Vec<(u64, u64)> = Vec::new();
67 for c in &v {
68 support = support
69 .checked_add(*c)
70 .ok_or(DimaError::Overflow { what: "support" })?;
71 match frequencies.last_mut() {
72 Some((last, f)) if last == c => *f += 1,
73 _ => frequencies.push((*c, 1)),
74 }
75 }
76 Ok(Self {
77 support,
78 distinct: v.len() as u64,
79 frequencies,
80 })
81 }
82
83 #[must_use]
85 pub const fn support(&self) -> u64 {
86 self.support
87 }
88
89 #[must_use]
91 pub const fn distinct(&self) -> u64 {
92 self.distinct
93 }
94
95 #[must_use]
97 pub fn frequencies(&self) -> &[(u64, u64)] {
98 &self.frequencies
99 }
100
101 #[must_use]
103 pub fn with_count(&self, count: u64) -> u64 {
104 self.frequencies
105 .binary_search_by_key(&count, |&(c, _)| c)
106 .map_or(0, |i| self.frequencies[i].1)
107 }
108}
109
110#[derive(Clone, Copy, Debug, PartialEq)]
112pub struct Estimate {
113 pub entropy: Option<f64>,
115 pub observed: Option<f64>,
117 pub method: EntropyMethod,
119 pub fallback: Option<EntropyFallback>,
121}
122
123pub fn estimate(profile: &CountProfile, estimator: Estimator, threshold: u64) -> Result<Estimate> {
130 let Some(observed) = plug_in(profile) else {
131 return Ok(Estimate {
132 entropy: None,
133 observed: None,
134 method: EntropyMethod::NotEstimable,
135 fallback: None,
136 });
137 };
138 let plug = |fallback| Estimate {
139 entropy: Some(observed),
140 observed: Some(observed),
141 method: EntropyMethod::PlugIn,
142 fallback,
143 };
144 let corrected = |value: f64, method| Estimate {
145 entropy: Some(value),
146 observed: Some(observed),
147 method,
148 fallback: None,
149 };
150 let e = match estimator {
151 Estimator::Raw => plug(None),
152 Estimator::Dima => match dima_corrected(profile, threshold) {
153 Ok(v) => corrected(v, EntropyMethod::Dima),
154 Err(reason) => plug(Some(reason)),
155 },
156 Estimator::MillerMadow => match miller_madow(profile) {
157 Some(v) => corrected(v, EntropyMethod::MillerMadow),
158 None => plug(Some(EntropyFallback::SingleObservation)),
159 },
160 Estimator::ChaoWangJost => match chao_wang_jost(profile) {
161 Some(v) => corrected(v, EntropyMethod::ChaoWangJost),
162 None => plug(Some(EntropyFallback::SingleObservation)),
163 },
164 };
165 reportable(e, profile, threshold)
166}
167
168fn reportable(e: Estimate, profile: &CountProfile, threshold: u64) -> Result<Estimate> {
172 let valid = |v: Option<f64>| v.is_none_or(|x| (0.0..f64::INFINITY).contains(&x));
173 if valid(e.entropy) && valid(e.observed) {
174 Ok(e)
175 } else {
176 Err(DimaError::internal(format!(
177 "entropy {:?} (observed {:?}) from {:?} is not a finite number of at least 0 bits \
178 (support {}, threshold {threshold}, counts of counts {:?})",
179 e.entropy,
180 e.observed,
181 e.method,
182 profile.support(),
183 &profile.frequencies()[..profile.frequencies().len().min(8)],
184 )))
185 }
186}
187
188#[must_use]
190pub fn plug_in(profile: &CountProfile) -> Option<f64> {
191 let n = profile.support;
192 if n == 0 {
193 return None;
194 }
195 let nf = n as f64;
196 let mut h = Neumaier::new();
197 for &(c, f) in &profile.frequencies {
198 if c != n {
199 let p = c as f64 / nf;
200 h.add(f as f64 * (-p * libm::log2(p)));
201 }
202 }
203 Some(h.total())
204}
205
206#[must_use]
210pub fn rarefaction_grid(n: u64, t: u64) -> Vec<u64> {
211 if n == 0 {
212 return Vec::new();
213 }
214 let x = (u128::from(t) * 100).div_ceil(u128::from(n));
216 let start = if x < u128::from(RAREFACTION_START) {
217 u128::from(RAREFACTION_START)
218 } else {
219 x.div_ceil(u128::from(RAREFACTION_STEP)) * u128::from(RAREFACTION_STEP)
220 };
221 #[allow(clippy::cast_possible_truncation)] let start = start.min(100) as u64;
223 (start..100).step_by(RAREFACTION_STEP as usize).collect()
224}
225
226#[must_use]
228pub fn subsample_size(n: u64, percent: u64) -> u64 {
229 #[allow(clippy::cast_possible_truncation)] let size = (u128::from(n) * u128::from(percent)).div_ceil(100) as u64;
231 size
232}
233
234#[must_use]
241pub fn expected_subsample_entropy(profile: &CountProfile, size: u64) -> f64 {
242 let n = profile.support;
243 if size <= 1 || n == 0 {
244 return 0.0;
245 }
246 let sf = size as f64;
247 let h = |x: u64| {
248 if x == 0 {
249 0.0
250 } else {
251 let q = x as f64 / sf;
252 -q * libm::log2(q)
253 }
254 };
255 let mut total = Neumaier::new();
256 for &(c, f) in &profile.frequencies {
257 if c == n {
258 continue; }
260 let p = c as f64 / n as f64;
261 let mut e = 0.0;
262 let w = binomial_walk(size, p, |x, w| e += w * h(x));
263 total.add(f as f64 * e / w);
264 }
265 total.total()
266}
267
268pub fn dima_corrected(profile: &CountProfile, threshold: u64) -> Result<f64, EntropyFallback> {
282 let n = profile.support;
283 if n <= threshold {
284 return Err(EntropyFallback::SupportAtOrBelowThreshold);
285 }
286 let grid = rarefaction_grid(n, threshold);
287 if grid.len() + 1 < RAREFACTION_MIN_POINTS {
288 return Err(EntropyFallback::TooFewPoints);
289 }
290 let observed = plug_in(profile).ok_or(EntropyFallback::SupportAtOrBelowThreshold)?;
291 let mut xs = Vec::with_capacity(grid.len() + 1);
292 let mut ys = Vec::with_capacity(grid.len() + 1);
293 for r in grid {
294 let size = subsample_size(n, r);
295 xs.push(1.0 / size as f64);
296 ys.push(expected_subsample_entropy(profile, size));
297 }
298 xs.push(1.0 / n as f64);
300 ys.push(observed);
301 match ols_intercept(&xs, &ys) {
302 None => Err(EntropyFallback::DegenerateRegression),
303 Some(b0) => Ok(if b0 == 0.0 { 0.0 } else { b0 }),
304 }
305}
306
307#[must_use]
309pub fn miller_madow(profile: &CountProfile) -> Option<f64> {
310 let n = profile.support;
311 if n < 2 {
312 return None;
313 }
314 let h = plug_in(profile)?;
315 Some(h + (profile.distinct - 1) as f64 / (2.0 * n as f64 * LN_2))
316}
317
318fn coverage_constant(n: u64, f1: u64, f2: u64) -> f64 {
321 let n1 = u128::from(n - 1);
322 if f2 > 0 {
323 (2 * u128::from(f2)) as f64 / (n1 * u128::from(f1) + 2 * u128::from(f2)) as f64
324 } else if f1 > 0 {
325 2.0 / (n1 * u128::from(f1 - 1) + 2) as f64
326 } else {
327 1.0
328 }
329}
330
331#[must_use]
338pub fn chao_wang_jost(profile: &CountProfile) -> Option<f64> {
339 let n = profile.support;
340 if n < 2 {
341 return None;
342 }
343 let nf = n as f64;
344 let mut part1 = Neumaier::new();
345 for &(c, f) in &profile.frequencies {
346 if c < n {
347 part1.add(f as f64 * (c as f64 / nf) * digamma_difference(n, c));
348 }
349 }
350 let f1 = profile.with_count(1);
351 let f2 = profile.with_count(2);
352 let a = coverage_constant(n, f1, f2);
353 let part2 = if f1 == 0 || a >= 1.0 {
354 0.0
355 } else {
356 f1 as f64 / nf * (1.0 - a) * lerch_phi1(n, a)
357 };
358 let h = (part1.total() + part2) / LN_2;
359 Some(if h == 0.0 { 0.0 } else { h })
360}
361
362#[must_use]
366pub fn sample_coverage(profile: &CountProfile) -> Option<f64> {
367 let n = profile.support;
368 if n < 2 {
369 return None;
370 }
371 let f1 = profile.with_count(1);
372 if f1 == 0 {
373 return Some(1.0);
374 }
375 let f2 = profile.with_count(2);
376 let n1 = u128::from(n - 1);
377 let ratio = if f2 > 0 {
378 (n1 * u128::from(f1)) as f64 / (n1 * u128::from(f1) + 2 * u128::from(f2)) as f64
379 } else {
380 (n1 * u128::from(f1 - 1)) as f64 / (n1 * u128::from(f1 - 1) + 2) as f64
381 };
382 Some(1.0 - f1 as f64 / n as f64 * ratio)
383}
384
385#[cfg(test)]
386mod tests {
387 use super::*;
388
389 fn profile(counts: &[u64]) -> CountProfile {
390 CountProfile::from_counts(counts.iter().copied()).unwrap()
391 }
392
393 const POS25: [u64; 10] = [129, 14, 9, 6, 4, 4, 1, 1, 1, 1];
395
396 fn close(a: f64, b: f64) -> bool {
399 (a - b).abs() <= 1e-13 * b.abs()
400 }
401
402 #[test]
403 fn profile_basics() {
404 let p = profile(&[3, 0, 1, 1, 2, 3, 3]);
405 assert_eq!(p.support(), 13);
406 assert_eq!(p.distinct(), 6);
407 assert_eq!(p.frequencies(), &[(1, 2), (2, 1), (3, 3)]);
408 assert_eq!(p.with_count(1), 2);
409 assert_eq!(p.with_count(4), 0);
410 assert!(matches!(
411 CountProfile::from_counts([u64::MAX, 1]),
412 Err(DimaError::Overflow { .. })
413 ));
414 }
415
416 #[test]
421 fn golden_values_position_25() {
422 let p = profile(&POS25);
423 assert_eq!(p.support(), 170);
424 assert!(close(plug_in(&p).unwrap(), 1.422_388_672_162_913_5));
425 assert!(close(
426 dima_corrected(&p, 30).unwrap(),
427 1.445_053_291_028_629_3
428 ));
429 assert!(close(
430 dima_corrected(&p, 100).unwrap(),
431 1.461_701_237_532_242_2
432 ));
433 assert!(close(miller_madow(&p).unwrap(), 1.460_577_658_539_386_1));
434 assert!(close(chao_wang_jost(&p).unwrap(), 1.490_071_840_297_816));
435 assert!(close(sample_coverage(&p).unwrap(), 42_251.0 / 43_265.0));
437 }
438
439 #[test]
440 fn grid_follows_figure_2() {
441 assert_eq!(
442 rarefaction_grid(170, 30),
443 vec![50, 55, 60, 65, 70, 75, 80, 85, 90, 95]
444 );
445 assert_eq!(
447 rarefaction_grid(170, 100),
448 vec![60, 65, 70, 75, 80, 85, 90, 95]
449 );
450 assert_eq!(rarefaction_grid(100, 55)[0], 55);
452 assert!(rarefaction_grid(101, 100).is_empty());
454 assert_eq!(rarefaction_grid(125, 100), vec![80, 85, 90, 95]);
455 assert_eq!(subsample_size(170, 50), 85);
456 assert_eq!(subsample_size(171, 50), 86);
457 assert_eq!(
458 subsample_size(u64::MAX, 95),
459 (u128::from(u64::MAX) * 95).div_ceil(100) as u64
460 );
461 }
462
463 #[test]
464 fn dima_fallbacks() {
465 let p = profile(&POS25);
466 assert_eq!(
467 dima_corrected(&p, 170),
468 Err(EntropyFallback::SupportAtOrBelowThreshold)
469 );
470 assert_eq!(
471 dima_corrected(&p, 500),
472 Err(EntropyFallback::SupportAtOrBelowThreshold)
473 );
474 let q = profile(&[100, 20, 5]);
476 assert!(dima_corrected(&q, 100).is_ok());
477 let q = profile(&[100, 15, 5]);
479 assert_eq!(dima_corrected(&q, 100), Err(EntropyFallback::TooFewPoints));
480 assert_eq!(dima_corrected(&profile(&[500]), 100), Ok(0.0));
482 let e = estimate(&profile(&[500]), Estimator::Dima, 100).unwrap();
483 assert_eq!(e.entropy, Some(0.0));
484 assert!(e.entropy.unwrap().is_sign_positive());
485 }
486
487 #[test]
488 fn estimate_methods_and_fallbacks() {
489 let empty = profile(&[]);
490 let e = estimate(&empty, Estimator::Dima, 100).unwrap();
491 assert_eq!(e.entropy, None);
492 assert_eq!(e.observed, None);
493 assert_eq!(e.method, EntropyMethod::NotEstimable);
494 let one = profile(&[1]);
495 for est in [Estimator::MillerMadow, Estimator::ChaoWangJost] {
496 let e = estimate(&one, est, 100).unwrap();
497 assert_eq!(e.entropy, Some(0.0));
498 assert_eq!(e.method, EntropyMethod::PlugIn);
499 assert_eq!(e.fallback, Some(EntropyFallback::SingleObservation));
500 }
501 let e = estimate(&one, Estimator::Dima, 100).unwrap();
502 assert_eq!(e.fallback, Some(EntropyFallback::SupportAtOrBelowThreshold));
503 let p = profile(&POS25);
504 let e = estimate(&p, Estimator::Raw, 100).unwrap();
505 assert_eq!((e.method, e.fallback), (EntropyMethod::PlugIn, None));
506 assert_eq!(e.entropy, e.observed);
507 let e = estimate(&p, Estimator::Dima, 30).unwrap();
508 assert_eq!(e.method, EntropyMethod::Dima);
509 assert!(e.entropy.unwrap() > e.observed.unwrap());
510 }
511
512 #[test]
514 fn expected_subsample_entropy_matches_enumeration() {
515 fn enumerate(probs: &[f64], n: u64) -> f64 {
516 fn rec(probs: &[f64], n: u64, left: u64, counts: &mut Vec<u64>, acc: &mut f64) {
518 if counts.len() + 1 == probs.len() {
519 counts.push(left);
520 let mut logp = libm::lgamma(n as f64 + 1.0);
521 let mut h = 0.0;
522 for (&c, &p) in counts.iter().zip(probs) {
523 logp += c as f64 * p.ln() - libm::lgamma(c as f64 + 1.0);
524 if c > 0 {
525 let q = c as f64 / n as f64;
526 h -= q * q.log2();
527 }
528 }
529 *acc += logp.exp() * h;
530 counts.pop();
531 return;
532 }
533 for c in 0..=left {
534 counts.push(c);
535 rec(probs, n, left - c, counts, acc);
536 counts.pop();
537 }
538 }
539 let mut acc = 0.0;
540 rec(probs, n, n, &mut Vec::new(), &mut acc);
541 acc
542 }
543 for counts in [
544 &[3u64, 1][..],
545 &[2, 2, 1],
546 &[5, 3, 2, 1, 1],
547 &[1, 1, 1, 1],
548 &[7, 4],
549 ] {
550 let p = profile(counts);
551 let total: u64 = counts.iter().sum();
552 let probs: Vec<f64> = counts.iter().map(|&c| c as f64 / total as f64).collect();
553 for size in 1..=12 {
554 let got = expected_subsample_entropy(&p, size);
555 let want = enumerate(&probs, size);
556 assert!(
557 (got - want).abs() < 1e-12,
558 "{counts:?} n={size}: {got} vs {want}"
559 );
560 }
561 }
562 assert_eq!(expected_subsample_entropy(&profile(&POS25), 1), 0.0);
564 assert_eq!(expected_subsample_entropy(&profile(&[50]), 30), 0.0);
565 }
566
567 #[test]
568 fn miller_madow_and_cwj_edge_cases() {
569 let p = profile(&[40]);
571 assert_eq!(miller_madow(&p), Some(0.0));
572 assert_eq!(chao_wang_jost(&p), Some(0.0));
573 assert_eq!(sample_coverage(&p), Some(1.0));
574 let p = profile(&[10, 1]);
576 let part1 = (10.0 / 11.0 * digamma_difference(11, 10)
577 + 1.0 / 11.0 * digamma_difference(11, 1))
578 / LN_2;
579 assert!(close(chao_wang_jost(&p).unwrap(), part1));
580 let p = profile(&[1; 50]);
582 assert!(chao_wang_jost(&p).unwrap() > 50f64.log2());
583 assert!(sample_coverage(&p).unwrap() < 0.05);
584 for (f1, f2) in [(30u64, 3u64), (20, 1), (200, 50), (3, 1)] {
586 let mut counts = vec![1; f1 as usize];
587 counts.extend(std::iter::repeat_n(2, f2 as usize));
588 counts.push(1000);
589 let v = chao_wang_jost(&profile(&counts)).unwrap();
590 assert!(v.is_finite() && v > 0.0);
591 }
592 let mut counts = vec![17_490_100u64];
595 counts.extend(std::iter::repeat_n(1, 1000));
596 counts.extend(std::iter::repeat_n(2, 4450));
597 let v = chao_wang_jost(&profile(&counts)).unwrap();
598 assert!(
599 (v - 0.014_173_273_093_526_109).abs() <= 2.0 * f64::EPSILON * v,
600 "{v}"
601 );
602 let mut big = vec![1_000_000u64, 50_000, 3, 2, 2];
604 big.extend(std::iter::repeat_n(1, 1000));
605 let p = profile(&big);
606 let c = chao_wang_jost(&p).unwrap();
607 let h = plug_in(&p).unwrap();
608 assert!(c > h && c.is_finite());
609 }
610
611 #[test]
612 fn coverage_cases() {
613 assert_eq!(sample_coverage(&profile(&[1])), None);
614 assert_eq!(sample_coverage(&profile(&[])), None);
615 assert_eq!(
617 sample_coverage(&profile(&[3, 1])).map(|c| c.to_bits()),
618 Some(1.0f64.to_bits())
619 );
620 let c = sample_coverage(&profile(&[3, 1, 1])).unwrap();
621 assert!(close(c, 1.0 - 0.4 * (2.0 / 3.0)));
623 }
624
625 fn points(p: &CountProfile, threshold: u64) -> Vec<(f64, f64)> {
627 let n = p.support;
628 let mut out: Vec<(f64, f64)> = rarefaction_grid(n, threshold)
629 .into_iter()
630 .map(|r| {
631 let size = subsample_size(n, r);
632 (1.0 / size as f64, expected_subsample_entropy(p, size))
633 })
634 .collect();
635 out.push((1.0 / n as f64, plug_in(p).unwrap()));
636 out
637 }
638
639 fn intercept_bounds_hold(counts: &[u64], threshold: u64) {
643 let p = profile(counts);
644 let observed = plug_in(&p).unwrap();
645 let tol = |x: f64| 1e-12 * x.abs().max(1e-300) + 1e-15;
646 let mut pts = points(&p, threshold);
647 pts.sort_by(|a, b| b.0.total_cmp(&a.0)); for w in pts.windows(2) {
649 assert!(
650 w[1].1 >= w[0].1 - tol(w[1].1),
651 "{counts:?}: E[H_n] fell: {w:?}"
652 );
653 }
654 for &(_, y) in &pts {
655 assert!(
656 y <= observed + tol(observed),
657 "{counts:?}: {y} > {observed}"
658 );
659 }
660 let mean = pts.iter().map(|&(_, y)| y).sum::<f64>() / pts.len() as f64;
661 if let Ok(h) = dima_corrected(&p, threshold) {
662 assert!(
663 h >= mean - tol(mean) && h >= 0.0,
664 "{counts:?}: {h} < {mean}"
665 );
666 }
667 }
668
669 #[test]
670 fn a_degenerate_regression_falls_back() {
671 assert_eq!(
674 dima_corrected(&profile(&[2, 1]), 2),
675 Err(EntropyFallback::DegenerateRegression)
676 );
677 }
678
679 #[test]
680 fn reported_entropies_are_finite_and_not_negative() {
681 let p = profile(&[3, 1]);
682 let e = |entropy, observed| Estimate {
683 entropy,
684 observed,
685 method: EntropyMethod::Dima,
686 fallback: None,
687 };
688 for ok in [Some(0.0), Some(-0.0), Some(1.5), None] {
689 assert!(reportable(e(ok, ok), &p, 1).is_ok());
690 }
691 for bad in [-1e-300, -0.1, f64::NAN, f64::INFINITY, f64::NEG_INFINITY] {
692 for (a, b) in [(Some(bad), Some(0.5)), (Some(0.5), Some(bad))] {
693 let err = reportable(e(a, b), &p, 1).unwrap_err();
694 assert!(matches!(err, DimaError::Internal { .. }), "{err}");
695 }
696 }
697 }
698
699 #[test]
700 fn the_expected_intercept_is_never_negative_near_conservation() {
701 for n in [101, 110, 125, 130, 171, 500, 1_000, 10_000, 1_000_000] {
704 for minor in [vec![1], vec![1, 1], vec![2], vec![1, 1, 1, 1, 1], vec![5]] {
705 let mut counts = vec![n - minor.iter().sum::<u64>()];
706 counts.extend(&minor);
707 for t in [1, 30, 100, n / 2, n - 1] {
708 intercept_bounds_hold(&counts, t);
709 }
710 }
711 }
712 }
713
714 proptest::proptest! {
715 #[test]
716 fn the_expected_intercept_is_never_negative(
717 counts in proptest::collection::vec(1u64..400, 1..12),
718 t_fraction in 0.0f64..1.0,
719 ) {
720 let n: u64 = counts.iter().sum();
721 #[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
722 let threshold = ((n as f64 * t_fraction) as u64).max(1);
723 intercept_bounds_hold(&counts, threshold);
724 }
725 }
726}