3

什么是count-min 草图？在什么情况下会有用？

4

1 回答 1

6

英里高概述

直观地说，您可以将 count-min 草图视为一种节省空间的数据结构，用于估算您在数据流中看到给定项目的次数。从客户端的角度来看，count-min 草图支持两种操作：

  • increment(x)，表示“我又见过 x 一次”，以及
  • 估计（x），它说“请给我一个估计我见过x的次数。”

如果你只看这个界面，你可能会想“这不是我可以用哈希表或 BST 做的吗？” 你是对的——你可以创建一个 BST，其键是元素，其值是每个项目被看到的次数，或者对哈希表做同样的事情。如果你有足够的内存来跟踪你遇到的所有键，这不是不合理的。但是想象一下，你正在开发一个亚马逊服务器，并且你正在跟踪每个产品的浏览量。突然之间，即使写下所有访问过的页面的名称也将花费大量时间的记忆。或者想象一下你是谷歌，你想找到每天访问量最大的页面。仅仅为了写下所有搜索查询而获得足够的 RAM 将非常昂贵，并且分页到磁盘会太慢。

让 count-min 草图大放异彩的是，用户可以调整 count-min 草图所需的内存量。如果你给它更多的内存，它会更好地估计它看到的元素的真实频率。如果你给它更少的内存，它会产生较低质量的估计，但可以量化保证这些估计接近真实值的可能性。这意味着，如果你只有 1MB 专用于此目的，你可以粗略估计频率，而如果你有 128MB，你可以得到更好的估计。

由 count-min 草图给出的估计值永远不会低估元素的真实频率。例如，如果一个 count-min 草图说一个项目出现了 50 次，那么该元素可能出现了 50 次、49 次或 48 次等，但它不可能出现 100 次次。这使得 count-min 草图对于查找高频项目很有用：低频项目的频率可能被高估了一点，但高频项目总是会显得很受欢迎。

内部细节

count-min 草图是一个相当简单的数据结构来实现。基本思路如下。想象一下，我们有一个计数器数组，我们想使用该数组来跟踪我们看到的项目的频率。我们将使用哈希函数将每个项目分配给某个计数器（计算其哈希码并根据表大小对其进行修改）。每当我们增加该项目时，我们只需转到适当的计数器，然后将其增加。为了提供一个估计值，我们只需去那个计数器并返回存储在那里的值。

考虑 count-min 草图如何工作的一种方法是将每个计数器想象成一个“桶”，其中包含某种类型的所有项目。然后，我们通过查看存储桶中有多少项目来估计某件事的频率，无论这些项目是什么，如下所示：

分配到桶中的项目集合

正如你所看到的，我们对频繁项得到了相当好的估计，而不频繁项的频率可能被严重高估了。这也给出了一个很好的直觉，为什么 count-min 草图永远不会低估元素的频率。在查看存储桶时，您至少会计算项目本身。

如果我们对我们使用的散列函数做出一些合理的假设，我们可以正式证明，平均而言，对一个项目的频率给出的估计最多是它的实际频率，加上项目的总数除以总数的计数器。这很直观。如果你有很多很多的柜台，在某些时候每个项目都有自己的柜台，估计会非常准确。在另一个极端，如果您几乎没有计数器，那么您会期望所有项目都被塞进少数几个桶中，并且总数将开始偏离。

虽然这种方法保证了预期返回的估计值是好的，但这并不意味着你很有可能得到一个好的估计值。考虑这一点的一种方法是考虑“对预期”进行良好估计意味着什么。直观地说，这意味着如果你要构建一堆这样的数据结构，那么估计的平均值可能会相当不错。然而，任何一个单独的估计都不一定会那么好。

count-min 草图将这个想法牢记在心，而不是只有一个计数器数组，而是维护几个独立的计数器数组，每个计数器都有不同的哈希函数将项目放入桶中。这提供了一定程度的冗余，并且意味着您不太可能因物品以不良方式碰撞而“不走运”。

为了得到它的总体估计，count-min 草图做了一些比仅仅平均估计值更聪明的事情。请记住，count-min 草图永远不能低估被存储项目的实际频率，而只能高估它们。这意味着，如果您返回一组不同的估计值，则估计值越大，情况就越差。为什么？因为估计值越大，我们关心的项目以外的项目就越多。（回想一下桶——如果桶中除了我们关心的项目之外还有一堆其他项目，我们不想使用该桶的大小作为估计值）。

这就是“count-min sketch”的“min”部分的用武之地。当返回一个估计值时，count-min sketch 返回所有生成的估计值中的最小估计值。这是其中噪声最小的估计值。直观地说，这很可能会给你一个很好的估计——它失败的唯一方法是如果每一个估计都是坏的，这是不太可能的。

这意味着整个数据结构以及操作它的逻辑相当简单：

代表多行计数器的 2D 网格的图像，以及总结结构如何工作的伪代码。

了解更多

还有更多关于 count-min 草图的探索。例如，您如何正式分析 count-min 草图以确定每行需要多少个计数器或需要多少个独立结构？您可以使用哪些类型的哈希函数？要了解更多信息，请查看这些讲座幻灯片，其中详细介绍了该主题。

如果你想同时支持增量和减量会发生什么？您如何使用 count-min 草图来查找数据流中最常见的元素？关于该主题的原始论文是一个很好的资源。

你能得到与没有随机性的 count-min 草图相同的结果吗？是的，使用一些聪明的数论。

于 2020-10-17T00:14:59.730 回答