表中的内容

• Introduction
• Frequency count
• What is CM Sketch
• Why is CM Sketch is important?
• Super Linear vs Linear vs Sub Linear
• Why not hash tables?
• Problems in CM Sketch ?
• Unveiling the Inner Workings
• From Theory to Action: Implementation Unleashed
• In Python
• Memory Comparison
• Summary of Key Points
• Takeaway
• Applications
• References

介绍

计数米草图是一种流行的概率数据结构，用于近似数据流中元素的频率估计。它提供了一种记忆效率（子线性）的方式，可以估算元素的频率而无需存储整个数据集。在此博客中，我们将探讨Count-Min Sketch的概念，并学习如何在Python中实施和使用它。

频率计数

• 频率计数或频率分析是数据分析中的一种技术，涉及确定数据集或数据流中不同元素的发生数量。
• 它为数据中元素的分布和普及提供了宝贵的见解。通过计算每个元素出现的频率，频率计数有助于发现模式，识别趋势并揭示数据集中最常见或最重要的元素。
• 该技术在各个领域中找到了应用程序，包括文本分析，数据挖掘，网络分析，市场研究，网络流量分析和社交媒体分析。它有助于识别流行单词，检测异常，了解客户偏好并做出数据驱动决策等任务。
• 从更简单的角度来看，此频率计数有助于获得更深入的了解和对我们拥有的数据的见解。

什么是CM草图？

• 如上所述，CM草图是一种概率数据结构，它将充当数据流的频率表。
• cm草图由多个哈希功能和一个二维数组组成。
• CM Sketch提供o（1）用于插入和检索，因此我们可以将其用于高速数据流，例如网络监控，股票市场分析，流量分析和数据挖掘。

CM草图的重要性

• 近似计数： cm草图旨在估计记忆有限的数据流中项目的频率。

• 内存效率：计数米草图（CM草图）演示了 sub-linear 记忆使用情况，因为它采用固定量的内存超级线性数据流的大小。

• 流数据分析： cm草图非常适合处理数据流，其中数据连续到达，并且无法完全归因于其音量。

• 可伸缩性：由于CM草图的内存需求是固定的并且与数据流的大小无关，因此为处理大型且不断增长的数据集提供了可扩展的解决方案，而不会随着数据量而变得不切实际增加。

超级线性与线性与子线性

在算法分析中，我们使用诸如超级线性，线性，子线性之类的术语，用于描述追索性消耗（时间或空间）。

超级线性：如果函数或算法的资源消耗速度快于输入的大小，则将其视为超级线性。就像我们确实递归或嵌套循环时一样，时间复杂性以更快的速度增加。我们可以考虑一种大于O（n）（n是输入大小）的算法将是超级线性

线性：函数或算法是线性的，如果其资源消耗与输入的大小相称地增长。我们可以考虑一种等于O（n）的算法。

sub-linear：如果其资源消耗以比输入尺寸慢的速率增长，则将函数或算法视为子线性。我们可以考虑算法的时间复杂性是O（log n）。即使我们加倍输入，也不会将资源分配加倍。

为什么不散布桌子？

在频率计数方面，我们的自然倾向是考虑哈希表，因为哈希表是存储频率计数最常用的数据结构。哈希表可以给出数据的确切计数，并提供有效的数据插入和检索。但是，由于以下原因，可以优于哈希表优先使用CM草图

1. 有效的内存： cm草图与哈希表相比需要足够少的内存（子线性内存）。我们可以使用固定的2-D阵列而不是将单个K-V对存储在表中。

2. 流数据： cm草图是专门设计用于处理流数据的，这意味着元素一一到达，并且可能不适合内存。我们可以在不存储整个数据集的情况下单个通过中处理数据。在流数据中，我们无法回顾旧数据，在CM草图中，我们可以实时执行所有操作。

3. 可扩展： cm草图可以轻松地分布在多个服务器上，每个草图都可以独立处理数据流。另外，我们可以合并结果以找到整体分析。 CM草图非常适合大规模分布式系统，因为其内存效率和可扩展性。

4. 简单，更快的更新：它具有有效的更新操作。它可以为每个元素进行处理（1）时间进行处理（插入或检索）。空间和时间复杂性的组合为数据流提供了很高的效率

CM草图中的问题

1. 近似错误：与哈希表不同，CM草图不会给出确切的计数。 CM草图是一种概率数据结构，在提供近似数据的同时，主要关注内存效率。这种权衡将适合在具有近似频率的地方，并且收敛的内存很有价值。

2. 假阳性：计数米草图可能会产生误报，其中估计频率高于实际频率。当两个不同的元素到同一计数器时，可能会发生这种情况。

3. 哈希功能选择：我们应该选择我们的哈希功能足以处理更多数据，选择不良的哈希功能将导致碰撞并降低准确性。

4. 一组元素： cm草图可以处理预定义的输入数据集，我们应该更多地了解我们在处理之前的数据集

揭示内部工作

让我们探索CM Sketch的真实后端实现。

为了获得更准确的数据，我们可以使用更多的哈希功能。

cm草图是一个额定空间，因为我们有一个预定义的草图/尺寸。

需要高级组件。

1. 计数器数组：这是一个2D阵列，具有固定数量的行和列。 CM草图中的草图不过是一个2D的计数器
2. 行：哈希函数数量
3. 列： 0到每个哈希函数给出的最大数字。
4. 哈希函数： cm草图使用多个哈希功能，这些函数独立地确定每个元素的计数器数组中的索引。
5. 递增计数器：当我们从数据流中获取元素时，每个哈希函数都会在计算计数器阵列中的各个行和列时进行处理。
6. 估计频率：为了估计元素的频率，草图检索了每个哈希函数为元素映射的行中计数器之间的最小值。最小值给出了元素频率的下限近似。

这种特殊的数据结构称为计数最小草图，因为我们正在计算草图内计数器的最小值。

揭示内部工作

高级工作组件

考虑具有定义元素集的以下数据流。

stream_data → [A, B, K, A, A, K, S, ....∞]

首先，我们必须为所拥有的元素构建预测的哈希功能输出。我们可以使用尽可能多的哈希功能来避免碰撞。

现在启动以行数为哈希函数的长度和列的数量作为哈希返回的最大数字，将CM草图作为哈希函数的长度和列数。矩阵/网格中的值将为0

在我们的情况下，我们使用这些哈希函数的最大哈希值的4个哈希函数为6

• 行 - 4
• 列7（0-6）

cm草图

使用4行和7列，我们创建了一个计数器数组，该数组将存储计数/频率。

步骤
1）首先开始处理数据流时，我们将把a传递给CM草图，对于A，
我们需要在哈希函数返回值的索引中增加计数器。
在我们的示例中 因此，通过各自的哈希函数行及其返回值更新了这些值。

2）类似于B，
我们需要在哈希函数返回值的索引中增加计数器。
现在，B通过Hash函数H1，H2，H3和H4，并获得值1、2、4、6。
因此，通过各自的哈希函数行及其返回值更新了这些值。
在H1中，对于A和B返回1，因此我们需要在索引中添加1个。

3）类似于K，
我们需要在哈希函数返回值的索引中增加计数器。
现在，k通过Hash函数H1，H2，H3和H4，并获得值3、4、1、6。
因此，通过各自的哈希函数行及其返回值更新了这些值。

4）现在我们再次获得了A，
现在，我们需要添加哈希的值。
对于哈希功能，H1，H2，H3和H4将返回1、6、3、1。
现在，我们需要在已经存在的那些索引值中添加1个。

5）我们再次得到一个，
重复步骤4。
对于哈希功能，H1，H2，H3和H4将返回1、6、3、1。
现在，我们需要在已经存在的那些索引值中添加1个。

6）现在元素将是k，
与K的哈希值重复相同的步骤
对于K Hash功能H1，H2，H3和H4将返回3、4、1、6。
现在，我们需要在已经存在的那些索引值中添加1个。

7）现在我们得到了一个新元素，
与S的哈希值重复相同的步骤
对于S Hash功能，H1，H2，H3和H4将返回6、2、4、1。
现在，我们需要在已经存在的那些索引值中添加1个。

因此，我们为数据流生成了CM草图。我们可以随时检索我们需要的计数。

如何获得频率

• 认为我们需要检索A。
的频率
• 我们知道A的哈希功能将返回索引1、6、3、1。
• 从CM草图矩阵中获取哈希频率。
• 哈希频率a is，

  
  A  → [4, 3, 3, 4]
  

• 因此，从哈希频率中，我们将将最小值作为计数/频率，在我们的情况下为3
• 我们的数据流中有3个A。
• 同样，对于K，我们有哈希频率。

• 
  K  → [2, 2, 2, 3]
  

• 频率列表的最小值为2，我们在流中有2 k。

- 不准确！

• 当我们计算 b 的最低频率时
• bâ[4，2，2，3]
• min_count = 2中B计数

注意事项

• 我们需要考虑最小值，因为另一个哈希更新可能会达到准确性。
• 当我们增加哈希数时，我们将获得更准确的频率。

python

在Python中，我们可以使用软件包/库， pyprobables

先决条件：

• Python版本> 3.6

• pyprobables软件包，我们可以通过pip

  安装它

  
  pip install pyprobables
  

• 我们可以从 pyprobables 中导入 countminsketch 类，并可以实现此数据结构。

代码突破

• cms = countminsketch（4，1000）。
• 这将在内部创建4个哈希函数，每个哈希函数将在0-999的范围内返回值。
• 我们将datastream添加到CMS （CMS.ADD），并且CMS内部对数据流的哈希函数和元素进行增量。
• cms.check（{element}）将返回元素的计数/频率/
• 对于此输入，我们将获得以下输出。

这就是我们可以在Python中使用CM草图进行流数据的方式。

记忆比较

现在，让我们尝试比较哈希表的内存利用率与CM草图。

认为我们有一个大输入，该输入将创建一个10 ³ 的随机单词。

这就是我们可以看到的结果，我们几乎通过CM草图保存了大约97％的内存。

摘要

1. CM草图是一种概率数据结构，用于近似数据流中元素的频率估计。
2. CM草图提供了一种有效的方法来通过使用有限的内存与精确计数方法进行估计频率。
。
3. cm草图是一个2D矩阵/网格，将相对于哈希函数增加计数。
4. CM草图中的每个单元格都会存储元素的频率。

收获

1. cm草图是一个近似频率估计。
2. cm草图是高度记忆力的。
3. cm草图是高度可扩展的，我们可以将最终输出与多个服务器输出合并。
4. 考虑多个哈希以提高准确性并降低碰撞。
5. 也要考虑时间与空间。因此，最好在我们在特定用例中使用它之前进行一些研究。

应用

• 网络流量分析。
• 监视。
• 数据流算法。
• 压缩传感。
• NLP/ML

参考

• https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
• Graham Cormode的CM草图：https://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf

代码回购：

• https://git.epam.com/ajay_thangavelu/cm-sketch/-/blob/main/src/cm_sketch.py
• https://git.epam.com/ajay_thangavelu/cm-sketch/-/blob/main/src/cm_sketch_comp.py

免责声明：

这是一个个人博客。此处表达的观点和观点仅是作者的观点，并且不代表任何组织或任何人都可以与之相关的任何组织的观点和观点。