algorithm - flajolet martin 素描是如何工作的？

Question

我试图理解这个草图，但无法理解。如果我错了，请纠正我，但基本上，假设我有一个文本数据..单词..我有一个散列函数..它接受一个单词并创建一个整数散列，然后我将该散列转换为二进制位向量？正确的..然后我跟踪我从左边看到的第一个 1.. 以及那个 1 所在的位置(比如 , k)... 这个集合的基数是 2^k？

http://ravi-bhide.blogspot.com/2011/04/flajolet-martin-algorithm.html

但是...说我只有一个词。并且它的散列函数使得它生成的散列是 2^5，那么我猜有 5 个(？？)尾随 0？所以它会预测 2^5 (??) 基数？听起来不对？我错过了什么

Answer 1

对于单个单词，R的分布是p = 1/2的几何分布，其标准差为sqrt(2) ≈ 1.41。

因此对于散列以 100000_b 结尾的单词，算法确实会产生 2⁵/0.77351 = 41.37。但其概率仅为1/64，符合R的标准差接近1的说法。