我们现在，简单地，redis
Count-min草图（也称为cm sketch）是一种概率数据结构，一旦掌握其工作方式，更重要的是，就如何使用它，这是一个非常有用的数据结构。
幸运的是，CM素描的简单特性使得新手比较容易理解（让我的许多朋友无法跟随上个月Top-K博客）。
CM素描已有几年的Redis模块最近作为RedisBloom模块2.0版本的一部分进行了重写。但是在我们深入研究CM草图之前，理解为什么要使用CM是很重要的任何概率数据结构。在速度，空间和准确性的三角形中，概率数据结构牺牲了一些准确性以获得空间 - 可能很多空间！对速度的影响因算法和集合大小而异。
正确的概率数据结构允许您仅在数据集中保留部分信息，以降低准确性。当然，在许多情况下(例如，银行账户)，准确性降低是不可接受的。但对于向网站用户推荐一部电影或播放广告，一个相对罕见的错误的成本很低，节省的空间可能是巨大的。
基本上，CM示意图的工作原理是将数据集中所有项的计数聚合到几个计数器数组中。在查询时，它返回项的最小计数在所有阵列中，这承诺最大限度地减少由碰撞引起的计数通货膨胀。外观速率低或分数（“鼠标流”）的物品在下面的计数出错率，这样你就丢失了所有关于它们真实数量的数据，它们就会被当作噪音对待。具有高出现率或得分的项目(“大象流”)，只需使用收到的计数。考虑到CM草图的大小是恒定的，并且它可以用于无限数量的项目，您可以看到存储空间的巨大节省。
对于背景来说，草图是一类数据结构及其伴随的算法。他们捕捉数据的性质，以便回答有关它的问题，同时使用常量或乘以空间。CM素描由Graham Cormode和S. Muthu Muthukrishnan描述于2005张纸中“改进的数据流摘要：Count-min草图及其应用。“
CM草图使用几个计数器数组来支持它的主要用例。让我们将数组的数量称为“深度”，将每个数组中的计数器的数量称为“宽度”。
每当我们收到项目时，我们都使用哈希函数（将元素 - 一个单词，句子，数字或二进制变为可以用作SET /阵列中的位置或指纹的数字）来计算项目的位置并增加每个阵列的计数器。每个关联计数器的值等于或高于项目的实际值。当我们进行查询时，我们通过所有阵列进行相同的哈希函数，并获取与我们项目相关联的计数器。然后我们回来了最低限度我们遇到的价值，因为我们知道我们的价值观（或等于）。
尽管我们知道许多物品会对大多数计数器产生影响，但由于自然冲突(当不同物品接收到相同位置时)，我们接受“噪音”，只要它仍在我们期望的错误率内。
数学计算表明，深度为10，宽度为2000，不出错的概率为99.9%，错误率为0.1%。(这是总增量的百分比，而不是独特道具的百分比)。
在实数，这意味着如果您平均增加100万个独特物品，则每个项目将获得500（1M / 2K）的值。虽然这似乎不成比例，但在我们的错误率为0.1％的情况下，这是100万项的错误率。
同样，如果10只大象每次出现10,000次，则它们对所有集合的价值将是10,000或以上。每当我们将来算上它们时，我们都会在我们面前看到一只大象。For all other numbers (i.e., all mice whose real count is 1), they are unlikely to collide with an elephant on all sets (since CM sketch considers only the minimum count) since the probability of this happening is slim and diminishes further if you increase the depth as you initialized CM sketch.
现在我们理解了CM草图的行为，我们可以对这个小怪兽做什么?以下是一些常见的用例:
在redisbloom.， CM草图的API是简单和容易的:
以下命令用于在此帖子顶部创建动画示例：
如您所见，“Redis”的值为4而不是3.此行为是预期的，因为在CM素描中，物品的计数可能会膨胀。
如果您喜欢这篇文章或想要了解更多有关概率数据结构的信息，请随时与我联系。
[算盘照片Crissy Jarvis.在uns．]
万博app手机客户端下载