数据流中的频繁元素

数据流意味着数据在流动，在源源不断的到达计算系统进行处理，意味着数据只能被扫描一次，而后就被放弃，不再访问了。

数据流中的频繁元素：在流动的数据中出现最频繁的几个元素

现要获取n个元素中的k个频繁元素。

如果为每个同种元素设置单独的计数器，每处理一个元素时增加相应计数器。这样如果有很多种元素就需要很多个计数器。这样没有满足O(n)的要求，并且对于数据流来说是不能实现的。

所以使用Misra Gries(MG)算法。

1.处理一个新到来的元素x时

2.if已经为其分配了计数器，则计数器加一

3.else if没有相应的计数器，但计数器少于k，为x分配计数器，并设为1

4.else 所有计数器值减1,删除值为0的计数器。

栗子：

数组 32, 12, 14, 32, 7, 12, 32, 7, 6, 5, 12, 32

假设内存中有3个存放计数器的空间。

32    [32:1]

12    [32:1, 12:1]

14    [32:1, 12:1, 14:1]

32    [32:2, 12:1, 14:1]

7      [32:1]

12    [32:1, 12:1]

32    [32:2, 12:1]

7      [32:2, 12:1, 7:1]

6      [32:1]

5       [32:1, 5:1]

12     [32:1, 5:1, 12:1]

32    [32:2, 5:1, 12:1]

使用该算法求出的几个频繁元素是32,5和12。对应数据来说，最频繁的元素是32,7和12。成功的找出了32和12，虽然没有找出全部的频繁元素，但整体来说已经是不错的结果了。如果只需要最频繁的元素，那么该算法找到了最频繁元素32。因此该算法求出的是近似解

不过频繁元素的计数值是不准确的，因此需要分析数值误差。

当我们使用近似手段处理问题时，一定要对近似解进行误差分析，研究近似解是否在我们可接受的范围之内，误差太大近似解就没有意义了。

近似解误差分析：

设：

总元素个数为：n

最后计数器和为:m

计数器容量为:k

元素最后的计数器值f

元素实际计数值F

则总共减去了n-m个计数

每次都将所有计数器减一，并且抛弃当前元素，则每次减去的计数为k+1

减少的次数为：(n-m)/(k+1)

那么得到真实计数范围为：