什么是有损计数？

Question

有人能给我解释一下有损计数算法吗？它是一种流算法，用于查找流中项目的频率。谢谢。

Answer 1

假设你正在查看facebook个人资料的流量。你有数十亿的点击量。您希望找到最常访问的配置文件。你可以为每个配置文件保留一个计数，但这样你就会有大量的计数需要跟踪，其中绝大多数是没有意义的。

使用有损计数时，您会定期从表中删除计数非常低的元素。最频繁访问的配置文件几乎永远不会有低计数，即使它们有，它们也不太可能在那里停留很长时间。

该算法基本上涉及将输入分组为块或块，并在每个块内进行计数。然后，将每个元素的计数减一，删除计数降为零的所有元素。

点击率最高的个人资料将会在你的列表中出现，并保持不变。任何不经常访问的配置文件将在几个区块内降为零，您将不再需要跟踪它们。

请注意，最终结果依赖于顺序，赋予最后处理的计数更重的权重。在某些情况下，这是非常有意义的，而且是一个好处而不是坏处。(如果你想知道哪些配置文件是现在最受欢迎的，你想要权衡今天的访问而不是上个月的访问。)

对算法进行了大量的改进。但基本思想是这样的--在不跟踪每个元素的情况下找到重量级元素，根据到目前为止的数据定期清除任何看起来不太可能是重量级元素的元素。

Answer 2

您可以在on this blog post和open-source version here中找到有关损失计数(和粘滞采样)如何工作的解释。

最常浏览的项目“幸存下来”。给定频率阈值f、频率误差e和元素总数N，输出可以表示为:计数超过fN - eN的元素。

最坏的情况下，我们需要(1/e) * log (eN)计数器。

例如，我们可能希望打印命中率超过20%的人的Facebook页面，错误阈值为2% (经验法则:错误=频率阈值的10% )。

对于频率f= 20%，e= 2%，所有真实频率超过f= 20%的元素都将被输出-没有假阴性。但我们低估了。一个单元的输出频率最多可以小于其真实频率2%。可能出现假阳性，频率在18% - 20%之间。最后，不会输出频率低于18%的元素。

给定大小为1/e的窗口，以下保证成立：

• 频率被低估了至多e*N
• 无假阳性的真实频率至少为f_N - e_N