# Module quantiles::misra_gries
[−]
[src]

Misra-Gries calculates an ε-approximate frequency count for a stream of N elements. The output is the k most frequent elements.

- the approximate count f'[e] is smaller than the true frequency f[e] of e, but by at most εN, i.e., (f[e] - εN) ≤ f'[e] ≤ f[e]
- any element e with a frequency f[e] ≥ εN appears in the result set

The error bound ε = 1/(k+1) where k is the number of counters used in the algorithm. When k = 1 i.e. a single counter, the algorithm is equivalent to the Boyer-Moore Majority algorithm.

If you want to check for elements that appear at least εN times, you will want to perform a second pass to calculate the exact frequencies of the values in the result set which can be done in constant space.

`@article{MISRA1982143, title = "Finding repeated elements", journal = "Science of Computer Programming", volume = "2", number = "2", pages = "143 - 152", year = "1982", issn = "0167-6423", doi = "http://dx.doi.org/10.1016/0167-6423(82)90012-0", url = "http://www.sciencedirect.com/science/article/pii/0167642382900120", author = "J. Misra and David Gries", }`

# Examples

use quantiles::misra_gries::*; let k: usize = 3; let numbers: Vec<u32> = vec![1,3,2,1,3,4,3,1,2,1]; let counts = misra_gries(numbers.iter(), k); let bound = numbers.len() / (k+1); let in_range = |f_expected: usize, f_approx: usize| { f_approx <= f_expected && (bound >= f_expected || f_approx >= (f_expected - bound)) }; assert!(in_range(4usize, *counts.get(&1).unwrap())); assert!(in_range(2usize, *counts.get(&2).unwrap())); assert!(in_range(3usize, *counts.get(&3).unwrap()));

## Functions

misra_gries |
Calculates the |