我试图理解为什么 Flajolet-Martin 算法 (FM) 工作时间过长。这里对算法的描述（第 4.4.2 节）很有希望，但并不完美。
为什么任何元素的最大尾部长度（尾随零的数量）可以作为流中不同元素数量的估计值？想象一下只有两个不同的元素 {1,2}，它们分别散列到 {10001, 10000}。这意味着不同元素的数量是 2^4，这显然是不正确的。
有什么诀窍？
问问题
326 次
2 回答
3
让我们从一个简单的问题开始：如果你将一枚公平的硬币抛了 3 次，你得到三个连续反面的概率是多少？那将是 1/8，因为每个硬币都有 50/50 的机会出现反面。
现在我们可以问 - 如果你要反复掷硬币 3 次，大约需要多少组 3 次翻转才能让其中一个连续出现三个反面？好吧，既然有 1/8 的机会得到三个尾巴，你会认为你需要这样做八次。事实上，这正是您需要执行此操作的预期次数。
更一般地说，在您期望看到 k 个连续的反面之前，您需要翻转一系列 k 个硬币多少次？这可能是大约 2 k次，因为有 1/2 k的机会获得 k 个连续的尾巴。
现在，假设有人来找你说：“嘿！我连续掷硬币十次，连续得到十次反面。” 如果您认为此人仅尝试抛十个硬币一次，您会对此说法有点怀疑，因为一次尝试您有大约 1/1000 的机会获得连续十个反面。但如果你想象这个人一遍又一遍地连续抛十个硬币，现在这更合理一些。你可能会说“哇！你可能不得不把那些硬币扔了，什么，2 10次？” 虽然你可能离得很远——也许他们真的很幸运——你仍然可能对他们必须做多少次硬币翻转试验有一个很好的估计。
谢谢你纵容这个小小的离开。让我们回到 Flajolet-Martin。:-)
Flajolet-Martin 估计器通过散列元素并跟踪出现在每个散列末尾的 0 位的数量来工作。不要将哈希视为数字，而是将其视为编码一系列硬币翻转的 0 和 1 序列。例如，哈希 0110 将被解释为“尾、头、头、尾”。
在这个模型中，“计算有多少尾随零”的想法最终基本上等同于“计算有多少连续的尾巴被翻转”。使用上面的推理，你不太可能看到大量的尾巴，所以如果你确实看到很多尾巴连续，这可能意味着你已经看到了很多项目。
当然，正如您所指出的，这并不完美，即使您只看到少量项目，哈希码的后面也有大量连续零，您可能会很不走运。这就是你上面的例子中发生的事情。为了解决这个问题，您可以并行运行多个 Flajolet-Martin 副本并将结果汇总在一起，这样一个错误的估计就不会破坏整体结果。（这个，再加上一点，给你著名的 HyperLogLog 估计器！）
希望这可以帮助！
于 2020-06-19T01:09:05.600 回答
0
这个问题最好在https://cs.stackexchange.com/之类的网站上提出
Flajolet-Martin 算法是一种流式算法。许多这样的算法是随机的，并提供预期的正确答案。我认为这就是他们在论文中所说的“估计”一词的意思。
不幸的是，这个算法有很大的方差。为了保证您以高概率获得接近正确的答案，您应该减少方差和/或使用中值技巧等方法。减少方差的一个简单方法是多次运行相同的算法，然后取平均值。您可以查看此部分：https ://en.wikipedia.org/wiki/Flajolet%E2%80%93Martin_algorithm#Improving_accuracy
于 2020-06-18T22:22:29.333 回答