弗拉约莱特·马丁素描是如何工作的

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的说法一致。

Answer 2

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

我们

有一个很好的随机哈希函数，它作用于字符串并生成整数，我们能对生成的整数说些什么？由于它们本身是随机的，我们期望：

1/2 of them to have their binary representation end in 0(i.e. divisible by 2),
1/4 of them to have their binary representation end in 00 (i.e. divisible by 4)
1/8 of them to have their binary representation end in 000 (i.e. divisible by 8)

扭转问题，如果哈希函数生成一个以 0^m 位结尾的整数。直观地，唯一字符串的数量约为 2^m。

Answer 3

真正重要的是要记住，Flajolet Martin 算法旨在从一组 N 个元素中计算不同的元素（假设 M 个不同的元素），而 M 预计非常非常大。

如果 N 或 M 足够小，我们可以将所有不同的元素存储在内存中，则使用该算法是没有意义的。

在 N 和 M 非常大的情况下，估计接近 2^k 的概率实际上是非常合理的。

对此

有解释：http://infolab.stanford.edu/~ullman/mmds/ch4.pdf（第143页）