CVM算法的Rust实现，用于计数不同元素

此库实现了以下算法：

Chakraborty, S., Vinodchandran, N. V., & Meel, K. S. (2022). Distinct Elements in Streams: An Algorithm for the (Text) Book. 6 pages, 727571 bytes. https://doi.org/10.4230/LIPIcs.ESA.2022.34

相关文章在Quanta上的地址： https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/

这是什么意思

计数不同元素问题或基数估计问题是指计算数据流中重复元素的数量。具体来说，如果你想计算一本书中的独特单词数量。如果你有足够的内存，你可以记录你遇到的所有独特元素。然而，由于资源限制，你可能没有足够的运行内存，或者潜在元素的数量可能非常庞大。这种限制在文献中被称为有限存储限制。

为了克服这种限制，已经开发出了流式算法：Flajolet-Martin，LogLog，HyperLogLog。此库实现的算法在这些算法中具有一个特定优势：它非常简单。它不使用哈希，而是使用采样方法计算基数的一个无偏估计。

什么是元素

在此实现中，元素是指实现了Eq + PartialEq + Hash特质的任何事物：各种整数类型、字符串、你实现了这些特质的任何结构体。但是不包括f32 / f64。

所有权

缓冲区必须保留其元素的所有权。在实际操作中，这并不是一个问题：与输入流的大小相比，缓冲区非常小。这也是算法的关键点：你的数据集非常大，而你的工作内存很小；你不想保留原始数据以存储对其的引用！因此，如果你有&str元素，你需要创建新的String来存储它们。如果你在处理文本数据，你可能想要去除标点符号并规范化大小写，因此你无论如何都需要新的String。如果你在处理包含数字值的字符串，首先将它们解析为适当的整数类型（实现了Copy）似乎是一种合理的方法。

更多细节

Don Knuth在其关于算法的论文中（他称之为算法D）中对此进行了描述（https://cs.stanford.edu/~knuth/papers/cvm-note.pdf），比我做得更好。你会注意到在第1页，他描述了他用作数据结构的缓冲区——称为treap——作为一个二叉树。

"它可以容纳至多s个有序对（a，u），其中a是流中的一个元素，u是一个实数，0 ≤ u < 1。"

其中s >= 1。我们的实现不使用treap作为缓冲区；它使用具有FxHash算法的快速HashSet：我们在插入时支付哈希成本，但在步骤D4中的搜索是O(1)。该库最终可能切换到treap实现。

cvmcount -t file.txt -e 0.8 -d 0.1 -s 5000

Mean: 9015.744000
Std: 534.076058
Min 7552.000000
25% 8672.000000
50% 9024.000000
75% 9344.000000
Max 11072.00000