如何开始与概率数据结构:计数-最小素描

Count-min草图(也称为CM草图)是一种概率数据结构，一旦掌握了它的工作方式，更重要的是掌握了如何使用它，它将非常有用。

幸运的是，CM sketch的简单特性使新手相对容易理解（原来我的许多朋友都无法理解上个月的内容）Top-K博客).

CM sketch作为Redis模块已经有好几年了最近作为RedisBloom模块2.0版本的一部分进行了重写。但是在我们深入研究CM草图之前，理解为什么要使用CM是很重要的任何概率的数据结构。在速度、空间和准确性的三角关系中，概率数据结构可能会牺牲一些准确性来获得空间很大的空间！对速度的影响因算法和集合大小而异。

• 精度：根据定义，仅保留部分数据并允许在存储中发生冲突会降低准确性。但您可以根据您的用例设置最大错误率。
• 存储空间：在记录了数十亿事件的大数据世界中，仅存储部分数据可以极大地减少存储空间需求和成本。
• 速度：某些传统数据结构的运行效率相对较低，从而降低了响应时间。（例如，排序集维护其中所有元素的顺序，但您可能只对最上面的元素感兴趣。由于概率算法只维护部分列表，因此效率更高，通常可以更快地回答查询。）。

正确的概率数据结构允许您仅保留数据集中的部分信息，以降低准确性但对于向网站用户推荐电影或播放广告而言，一个相对罕见的错误的成本很低，而且节省的空间也相当可观。

基本上，CM sketch的工作原理是将数据集中所有项的计数聚合到几个计数器数组中最小计数在所有数组中，它承诺将冲突导致的计数膨胀降至最低。出现率或分数较低的项目（“鼠标流”）的计数低于出错率，这样你就丢失了所有关于它们真实数量的数据，它们就会被当作噪音对待。具有高出现率或得分的项目(“大象流”)，只需使用收到的计数。考虑到CM草图的大小是恒定的，并且它可以用于无限数量的项目，您可以看到存储空间的巨大节省。

对于背景，草图是一类数据结构及其相应的算法。在使用常数或次线性空间时，它们捕获数据的性质，以便回答有关它的问题。CM草图是由Graham Cormode和S. Muthu Muthukrishnan在2005年的一篇论文中描述的“一种改进的数据流摘要:计数最小草图及其应用”。

CM素描:什么和怎么做

CM sketch使用多个计数器数组来支持其主要用例

每当我们接收到一个项目时，我们使用哈希函数(它将一个元素——单词、句子、数字或二进制——转换成一个可以用作set/数组中的位置或指纹的数字)来计算项目的位置，并为每个数组增加计数器。每个关联的计数器都有一个等于或高于该项的实际值的值。当我们进行查询时，我们使用相同的哈希函数遍历所有数组，并获取与我们的项相关联的计数器。然后返回最低我们遇到的值，因为我们知道我们的值是膨胀的(或相等的)。

尽管我们知道许多项目对大多数计数器有影响，但由于自然碰撞（当不同项目接收到相同位置时），只要“噪音”保持在我们期望的错误率内，我们就接受它。

CM素描有什么好处？

现在我们了解了CM sketch的行为，我们可以用这个小野兽做什么？以下是一些常见的用例：

• 查询两个数字并比较它们的计数。
• 设定传入项目的百分比，比如说1%。每当一个项目最小计数大于总计数的1%，则返回true。例如，这可用于确定在线游戏的顶级玩家。
• 添加最小堆为CM绘制草图并创建Top-K数据结构。每当我们增加项目时，我们都会检查新项目最小计数高于堆中的最小值，并相应地更新它RedisBloom中的Top-K模块，随着时间的推移逐渐衰减，CM素描永远不会忘记，因此其行为与HeavyKeeper-基于Top-K。

在里面RedisBloom， CM草图的API是简单和容易的:

• 初始化CM草图数据结构:INITBYDIM {钥匙} {宽度} {深度}或CMS。INITBYPROB {钥匙} {错误} {可能性}
• 增加物品的计数器:CMS.INCRBY{钥匙} {项目} {定期的加薪}
• 要获取在项目计数器中找到的最小计数，请执行以下操作：CMS.QUERY{钥匙} {项目}

以下命令用于在本文顶部创建动画示例：

如你所见，Redis的值是4而不是3。这种行为是预期的，因为在CM草图中，项目的计数很可能被夸大。

如果你喜欢这篇文章或者想了解更多关于概率数据结构的信息，请随时与我联系。

[算盘图片作者]Crissy贾维斯在不鞭笞．]