什么是计数分钟草图？你什么时候使用它？
What is a count-min sketch? When would you use it?
什么是 count-min sketch？在什么情况下会有用？
Mile-High 概述
直观上，您可以将 count-min 草图视为 space-efficient 数据结构，用于估算您在数据流中看到给定项目的次数。从client-side的角度来看，count-min草图支持两种操作：
- increment(x)，上面写着“我又看了 x 次”，
- estimate(x)，上面写着“请估计我见过 x 的次数。”
如果你只看这个界面，你可能会想“这不是我可以用哈希 table 或 BST 做的事情吗？”你是对的——你可以创建一个 BST，它的键是元素，它的值是每个项目被看到的次数，或者用散列 table 做同样的事情。如果您有足够的内存来跟踪您遇到的所有键，这不是不合理的。但是想象一下，您正在使用亚马逊服务器，并且您正在跟踪每个产品的浏览量。突然间，即使写下所有访问过的页面的名称也会占用 吨 的内存。或者假设您是 Google，并且希望每天查找 most-commonly-visited 页。仅仅为了写下所有搜索查询而获得足够的 RAM 将是非常昂贵的，而且分页到磁盘会太慢。
count-min 草图的亮点在于 用户可以调整 count-min 草图所需的内存量。 如果您给它有更多的内存，它将更好地估计它所看到的元素的真实频率。如果你给它更少的内存，它会产生 lower-quality 估计值，但可以量化保证这些估计值接近真实值的可能性。这意味着，如果您只有 1MB 专用于此目的，您可以获得频率的粗略估计，而如果您有 128MB，您可以获得更好的估计。
count-min 草图给出的估计永远不会低估元素的真实频率。例如，如果 count-min sketch 说某个项目出现了 50 次，那么该元素可能出现了 50 次，或 49 次，或 48 次等，但它不可能有出现100次。这使得 count-min 草图对于查找 high-frequency 项目很有用：low-frequency 项目的频率可能被高估了一点，但 high-frequency 项目总是很受欢迎。
内部细节
count-min sketch 是一个相当容易实现的数据结构。基本思想如下。假设我们有一个计数器数组，我们想使用该数组来跟踪我们所看到的项目的频率。我们将使用散列函数将每个项目分配给某个计数器（计算其散列码并 mod 它的 table 大小）。每当我们 增加 那个项目时，我们将转到适当的计数器，然后增加它。为提供 估计值 ，我们只需转到该计数器并 return 那里存储的值。
思考 count-min 草图如何工作的一种方法是将每个计数器想象成一个“桶”，其中包含某种类型的所有项目。然后，我们通过查看其存储桶中有多少项来估计某项的出现频率，而不管这些项是什么，如下所示：
如您所见，我们对频繁出现的项目获得了相当不错的估计，而不经常出现的项目的出现频率可能被严重高估了。这也给出了一个很好的直觉，为什么 count-min 草图从不低估元素的频率。在查看桶时，您总是至少会计算项目本身。
如果我们对正在使用的散列函数做出一些合理的假设，我们就可以正式证明，平均而言，一个项目的频率给出的估计最多是它的实际频率加上项目总数除以计数器总数。这具有直觉意义。如果你有很多计数器，在某个时候每个项目都有自己的计数器并且估计将非常准确。在另一个极端，如果您几乎没有计数器，那么您会期望所有项目都被塞进少量的桶中，并且总数将开始相差甚远。
虽然这种方法保证 预期 估计 return 会很好，但这并不意味着你有 高概率 得到一个好的估计。思考这个问题的一种方法是思考“按预期”进行良好估计意味着什么。直觉上，这意味着如果你要构建一堆这样的数据结构，那么估计的平均值可能会非常好。但是，任何一个单独的估计都不一定那么好。
count-min sketch 将这个想法牢记在心，而不是只有一个计数器数组，maintans 几个独立的计数器数组，每个数组都有不同的哈希函数将项目放入桶中。这提供了一定程度的冗余，意味着您不太可能因为物品以不良方式碰撞而“倒霉”。
为了获得总体估计，count-min 草图做了一些比将估计平均在一起更聪明的事情。请记住，count-min 草图永远不会低估存储项目的实际频率，而只会高估它们。这意味着如果你有一组不同的估计返回，估计越大，它就越糟糕。为什么？因为估计值越大，我们关心的项目以外的项目就越多。 （回想一下桶 - 如果桶中除了我们关心的那个之外还有一堆其他物品，我们不想使用那个桶的大小作为估计）。
这是“count-min草图”的“最小”部分的用武之地。当return估算时，count-min草图return是最小值estimate 在所有生成的估计中。这是其中噪声最少的估计。直觉上，这很可能会给你一个很好的估计 - 它失败的唯一方法是如果每个估计都不好，这是不太可能的。
这意味着整个数据结构和操作它的逻辑相当简单：
了解更多
关于 count-min 草图还有更多内容需要探索。例如，您如何正式分析 count-min 草图以确定每行需要多少个计数器或需要多少个独立结构？您可以使用哪些类型的哈希函数？要了解更多信息，请查看 these lecture slides，其中详细介绍了该主题。
如果你想同时支持递增和递减会怎样？如何使用 count-min 草图查找数据流中出现频率最高的元素？ The original paper on the topic 是一个很好的资源。
你能得到与没有随机性的 count-min 草图相同的结果吗？ Yes, using some clever number theory.
什么是 count-min sketch？在什么情况下会有用？
Mile-High 概述
直观上，您可以将 count-min 草图视为 space-efficient 数据结构，用于估算您在数据流中看到给定项目的次数。从client-side的角度来看，count-min草图支持两种操作：
- increment(x)，上面写着“我又看了 x 次”，
- estimate(x)，上面写着“请估计我见过 x 的次数。”
如果你只看这个界面，你可能会想“这不是我可以用哈希 table 或 BST 做的事情吗？”你是对的——你可以创建一个 BST，它的键是元素，它的值是每个项目被看到的次数，或者用散列 table 做同样的事情。如果您有足够的内存来跟踪您遇到的所有键，这不是不合理的。但是想象一下，您正在使用亚马逊服务器，并且您正在跟踪每个产品的浏览量。突然间，即使写下所有访问过的页面的名称也会占用 吨 的内存。或者假设您是 Google，并且希望每天查找 most-commonly-visited 页。仅仅为了写下所有搜索查询而获得足够的 RAM 将是非常昂贵的，而且分页到磁盘会太慢。
count-min 草图的亮点在于 用户可以调整 count-min 草图所需的内存量。 如果您给它有更多的内存，它将更好地估计它所看到的元素的真实频率。如果你给它更少的内存，它会产生 lower-quality 估计值，但可以量化保证这些估计值接近真实值的可能性。这意味着，如果您只有 1MB 专用于此目的，您可以获得频率的粗略估计，而如果您有 128MB，您可以获得更好的估计。
count-min 草图给出的估计永远不会低估元素的真实频率。例如，如果 count-min sketch 说某个项目出现了 50 次，那么该元素可能出现了 50 次，或 49 次，或 48 次等，但它不可能有出现100次。这使得 count-min 草图对于查找 high-frequency 项目很有用：low-frequency 项目的频率可能被高估了一点，但 high-frequency 项目总是很受欢迎。
内部细节
count-min sketch 是一个相当容易实现的数据结构。基本思想如下。假设我们有一个计数器数组，我们想使用该数组来跟踪我们所看到的项目的频率。我们将使用散列函数将每个项目分配给某个计数器（计算其散列码并 mod 它的 table 大小）。每当我们 增加 那个项目时，我们将转到适当的计数器，然后增加它。为提供 估计值 ，我们只需转到该计数器并 return 那里存储的值。
思考 count-min 草图如何工作的一种方法是将每个计数器想象成一个“桶”，其中包含某种类型的所有项目。然后，我们通过查看其存储桶中有多少项来估计某项的出现频率，而不管这些项是什么，如下所示：
如您所见，我们对频繁出现的项目获得了相当不错的估计，而不经常出现的项目的出现频率可能被严重高估了。这也给出了一个很好的直觉，为什么 count-min 草图从不低估元素的频率。在查看桶时，您总是至少会计算项目本身。
如果我们对正在使用的散列函数做出一些合理的假设，我们就可以正式证明，平均而言，一个项目的频率给出的估计最多是它的实际频率加上项目总数除以计数器总数。这具有直觉意义。如果你有很多计数器，在某个时候每个项目都有自己的计数器并且估计将非常准确。在另一个极端，如果您几乎没有计数器，那么您会期望所有项目都被塞进少量的桶中，并且总数将开始相差甚远。
虽然这种方法保证 预期 估计 return 会很好，但这并不意味着你有 高概率 得到一个好的估计。思考这个问题的一种方法是思考“按预期”进行良好估计意味着什么。直觉上，这意味着如果你要构建一堆这样的数据结构，那么估计的平均值可能会非常好。但是，任何一个单独的估计都不一定那么好。
count-min sketch 将这个想法牢记在心，而不是只有一个计数器数组，maintans 几个独立的计数器数组，每个数组都有不同的哈希函数将项目放入桶中。这提供了一定程度的冗余，意味着您不太可能因为物品以不良方式碰撞而“倒霉”。
为了获得总体估计，count-min 草图做了一些比将估计平均在一起更聪明的事情。请记住，count-min 草图永远不会低估存储项目的实际频率，而只会高估它们。这意味着如果你有一组不同的估计返回，估计越大，它就越糟糕。为什么？因为估计值越大，我们关心的项目以外的项目就越多。 （回想一下桶 - 如果桶中除了我们关心的那个之外还有一堆其他物品，我们不想使用那个桶的大小作为估计）。
这是“count-min草图”的“最小”部分的用武之地。当return估算时，count-min草图return是最小值estimate 在所有生成的估计中。这是其中噪声最少的估计。直觉上，这很可能会给你一个很好的估计 - 它失败的唯一方法是如果每个估计都不好，这是不太可能的。
这意味着整个数据结构和操作它的逻辑相当简单：
了解更多
关于 count-min 草图还有更多内容需要探索。例如，您如何正式分析 count-min 草图以确定每行需要多少个计数器或需要多少个独立结构？您可以使用哪些类型的哈希函数？要了解更多信息，请查看 these lecture slides，其中详细介绍了该主题。
如果你想同时支持递增和递减会怎样？如何使用 count-min 草图查找数据流中出现频率最高的元素？ The original paper on the topic 是一个很好的资源。
你能得到与没有随机性的 count-min 草图相同的结果吗？ Yes, using some clever number theory.