Flajolet-Martin 算法背后的直觉是什么？
What is the intuition behind the Flajolet-Martin algorithm?
我试图理解为什么 Flajolet-Martin 算法 (FM) 工作时间过长。算法 here 的描述（第 4.4.2 节）很有前途但并不完美。
为什么任何元素的最大尾部长度（尾随零的数量）都可以作为对不同元素数量的估计在流？想象只有两个不同的元素 {1,2}，它们分别散列为 {10001, 10000}。这意味着不同元素的数量是 2^4，这显然是不正确的。
有什么诀窍？
这个问题最好在 https://cs.stackexchange.com/
这样的网站上问
Flajolet-Martin 算法是一种 streaming 算法。许多这样的算法是随机的，并期望提供正确的答案。我想这就是论文中 "estimate" 这个词的意思。
不幸的是，这个算法有很大的方差。为了保证您以高概率获得接近正确的答案，您应该减少方差 and/or 使用中值技巧等方法。一个简单的降低方差的方法就是运行同一个算法多次，然后取平均值。您可以查看此部分：https://en.wikipedia.org/wiki/Flajolet%E2%80%93Martin_algorithm#Improving_accuracy
我们先从一个简单的问题开始：如果你抛了三次均匀的硬币，你得到连续三个反面的概率是多少？那将是 1/8，因为每枚硬币都有 50/50 的机会出现反面。
现在我们可以问——如果你要反复抛硬币 3 次，大约需要抛多少次，每抛 3 次才能让其中一次连续出现 3 个反面？好吧，因为有 1/8 的机会得到三个反面，所以你预计你需要这样做八次。事实上，这正是您需要执行此操作的预期次数。
更一般地说，在您期望看到 k 个连续的尾巴之前，您需要抛掷一系列 k 个硬币多少次？大概是 2k 次，因为有 1/2k 的机会得到 k 个连续的尾巴。
现在，假设有人来找你说 "hey! I flipped a coin ten times in a row and got ten consecutive tails." 如果你认为这个人只是试过掷 10 个硬币一次，你会对这个说法有点怀疑，因为一次尝试你大约有 1 /1000 几率获得十个连续的尾巴。但是如果你想象这个人试图连续抛十个硬币 over 和 over 和 over，现在这更合理了。你可能会说类似 "wow! You probably had to flip those coins like, what, 210 times?" 的东西，虽然你可能离题很远——也许他们真的很幸运——你仍然可能对他们必须进行多少次抛硬币试验有一个很好的估计。
感谢您容忍这次小小的离开。让我们回到 Flajolet-Martin。 :-)
Flajolet-Martin 估算器通过散列元素并跟踪出现在每个散列末尾的 0 位的数量来工作。不要将哈希视为数字，而应将其视为对一系列抛硬币进行编码的 0 和 1 序列。例如，散列 0110 将被解释为 "tails, heads, heads, tails."
在这个模型中，"count how many trailing zeros there are" 的想法最终基本上等同于 "count how many consecutive tails were flipped." 并且使用上面的推理，你不太可能看到大的 运行 的尾巴，所以如果你 连续看到很多尾巴，这可能意味着你已经看到了很多项目。
当然，正如您所指出的，这并不完美，如果哈希码后面有大量 运行 个连续的零，即使您只看到项目数量少。这就是您上面的示例中发生的情况。为了抵消这一点，您可以 运行 并行 Flajolet-Martin 的多个副本并将结果汇总在一起，这样单个错误的估计就不会破坏整体结果。 （这个，加上更多，给你著名的 HyperLogLog 估计器！）
希望对您有所帮助！
我试图理解为什么 Flajolet-Martin 算法 (FM) 工作时间过长。算法 here 的描述（第 4.4.2 节）很有前途但并不完美。
为什么任何元素的最大尾部长度（尾随零的数量）都可以作为对不同元素数量的估计在流？想象只有两个不同的元素 {1,2}，它们分别散列为 {10001, 10000}。这意味着不同元素的数量是 2^4，这显然是不正确的。
有什么诀窍？
这个问题最好在 https://cs.stackexchange.com/
这样的网站上问Flajolet-Martin 算法是一种 streaming 算法。许多这样的算法是随机的，并期望提供正确的答案。我想这就是论文中 "estimate" 这个词的意思。
不幸的是，这个算法有很大的方差。为了保证您以高概率获得接近正确的答案，您应该减少方差 and/or 使用中值技巧等方法。一个简单的降低方差的方法就是运行同一个算法多次，然后取平均值。您可以查看此部分：https://en.wikipedia.org/wiki/Flajolet%E2%80%93Martin_algorithm#Improving_accuracy
我们先从一个简单的问题开始：如果你抛了三次均匀的硬币，你得到连续三个反面的概率是多少？那将是 1/8，因为每枚硬币都有 50/50 的机会出现反面。
现在我们可以问——如果你要反复抛硬币 3 次，大约需要抛多少次，每抛 3 次才能让其中一次连续出现 3 个反面？好吧，因为有 1/8 的机会得到三个反面，所以你预计你需要这样做八次。事实上，这正是您需要执行此操作的预期次数。
更一般地说，在您期望看到 k 个连续的尾巴之前，您需要抛掷一系列 k 个硬币多少次？大概是 2k 次，因为有 1/2k 的机会得到 k 个连续的尾巴。
现在，假设有人来找你说 "hey! I flipped a coin ten times in a row and got ten consecutive tails." 如果你认为这个人只是试过掷 10 个硬币一次，你会对这个说法有点怀疑，因为一次尝试你大约有 1 /1000 几率获得十个连续的尾巴。但是如果你想象这个人试图连续抛十个硬币 over 和 over 和 over，现在这更合理了。你可能会说类似 "wow! You probably had to flip those coins like, what, 210 times?" 的东西，虽然你可能离题很远——也许他们真的很幸运——你仍然可能对他们必须进行多少次抛硬币试验有一个很好的估计。
感谢您容忍这次小小的离开。让我们回到 Flajolet-Martin。 :-)
Flajolet-Martin 估算器通过散列元素并跟踪出现在每个散列末尾的 0 位的数量来工作。不要将哈希视为数字，而应将其视为对一系列抛硬币进行编码的 0 和 1 序列。例如，散列 0110 将被解释为 "tails, heads, heads, tails."
在这个模型中，"count how many trailing zeros there are" 的想法最终基本上等同于 "count how many consecutive tails were flipped." 并且使用上面的推理，你不太可能看到大的 运行 的尾巴，所以如果你 连续看到很多尾巴，这可能意味着你已经看到了很多项目。
当然，正如您所指出的，这并不完美，如果哈希码后面有大量 运行 个连续的零，即使您只看到项目数量少。这就是您上面的示例中发生的情况。为了抵消这一点，您可以 运行 并行 Flajolet-Martin 的多个副本并将结果汇总在一起，这样单个错误的估计就不会破坏整体结果。 （这个，加上更多，给你著名的 HyperLogLog 估计器！）
希望对您有所帮助！