3.3 寻找频繁元素的非随机算法
上面讲的是一个简单的例子，接下来讲一个复杂的例子——频繁元素。
频繁元素指的是在数据流当中同一个元素出现多次，希望找到出现最频繁的元素。我们看一个例子：在数据流状态<32,12,14,32,7,12,32,7,6,12,4>中，当前最频繁的元素是32和12。这两个都是最频繁元素。
频繁元素问题
输入：流
,隐式地定义了一个频率向量f=(f1,…,fn)。注意f1+…+fn=m。
输出：对于一个参数k，输出集合
频繁元素问题有广泛的应用。在网络当中找到“elephant flow”、ip地址等，在搜索引擎中找到频繁查询，可以给这些最频繁的查询做一些优化。在应用当中求频繁元素时有一个假设，即Zipf原则:典型的频率分布是高度偏斜的，只有少数频繁元素，大多数元素是非常不频繁的。这个假设是合法的，根据统计一般最多10%的元素占元素总个数的90%。
3.3.1 频繁元素的精确解
求精确解的方法很简单，可以对每一个单独元素设置一个计数器。当处理一个元素时，增加相应计数器。
例如求上述数据流中的频繁元素。
1） 首先，32到来，给32设一个计数器，并加1，得到<32,1>。
2） 接着12到来，给12设一个计数器，并加1，得到<32,1>，<12,1>。
3） 接下来给14设一个计数器，得到<32,1>，<12,1>，<14，1>。
4） 32又来了，给32的计数器加1,得到<32,2>，<12,1>，<14，1>。
5） 依此类推，最终结果为<32,3>，<12,3>，<14，1>,<7,2>,<6,1>,<4,1>。
这样做确实能得到精确解。但缺点是很明显的，只要数据流里面有一个新元素，在内存当中就要保存这个元素和它的计数器。如果在整个数据流中不同数据的数量非常大，则它所需要的内存量也是非常大的。这意味着没有一个很具体的界限。最坏情况是需要维护n个计数器，数据的个数就是计数器的个数。但在现实当中可以提供的计数器个数k是远小于n的，因此，可以退而求其次，求近似解。
3.3.2 频繁元素的Misra-Gries算法
Misra-Gries算法是一个计算频繁元素的非随机化近似算法。求解思想为：对于接收到的元素x，如果已经为其分配计数器，则把相应计数器加1；如果没有相应计数器，但计数器个数少于k,就为其分配计数器，并设为1，意味着内存中还有空间；如果当前计数器的个数为k，说明内存已经满了，则把所有计数器减1，然后删除取值为0的计数器，这样内存就又有空间了，再依次处理下一个x。
考虑上面的例子，其中n=6，k=3，m=11。
1) 接收32，内存有空间，为其分配计数器，内存状态<32,1>。
2) 接收12，内存有空间，为其分配计数器，内存状态<32,1>，<12,1>。
3) 接收14，内存有空间，为其分配计数器，内存状态<32,1>，<12,1>,<14,1>。
4) 接收32，32对应计数器加1，内存状态<32,2>，<12,1>,<14,1>。
5) 接收7，7不在内存当中，需要为其分配新的计数器，但是内存没有空间了。这时将所有计数器减1，然后把值为0的计数器删除，这时候，12和14的计数器就没有了。注意此时不将7的计数器加1,内存状态<32,1>。
6) 接收12，内存又有空间，为其重新分配计数器，内存状态<32,1>，<12,1>。
7) 接收32，32对应计数器加1，内存状态<32,2>，<12,1>。
8) 接收7，为其分配计数器，内存状态<32,2>，<12,1>,<7,1>。
9) 接收6，这时候内存满了，把所有计数器减1，然后把值为0的计数器删除,内存状态<32,1>。
10) 接收12，内存又有空间，为其再重新分配计数器，内存状态<32,1>，<12,1>。
11) 接收4，为其分配计数器，内存状态<32,1>，<12,1>,<4,1>。
这时候，如何根据计数器估计x出现的次数？最直接的办法是将内存里最后的数据定为x出现的次数，计数器在内存中将x返回，没有则返回0。很显然这种方法低估了计数问题，32出现了3次，但是最后只返回1次。
该算法的伪代码如算法3-2所示。算法3-2 求元素频率
初始化:A←;
处理j:
if j ∈ keys(A) then
A\[j\]←A\[j\]+1
else if keys(A)<k-1 then
A\[j\]←1
else
foreach ∈keys(A) do
A\[\]←A\[\]-1
if A\[\]=0 then从A中移除;
输出:对于查询a, if a∈ keys(A),then输出fa=Aa,else输出fa=0。
算法精确性分析
定理3-2 算法3-2求得的元素a、频率估计fa和真实值fa之间的关系满足，其中m是数据流中所有元素出现的次数，m′是当前所有计数器之和。
证明 由于在计算过程中每个元素对应的计数器都可能减掉一些值，故显然
下面通过分析删除最多的元素数分析fa与fa之差的上界。这二者的差距是由a所对应计数器的减少所引起的，出现一个减少计数器的步骤，相应计数器就要减少一次。因而问题转化为整个计算过程中a对应计数器减少的次数。
注意到在计算过程中，只有内存已经满了的时候，即已经有k个计数器的时候，才执行计数器减少步骤，而此时每个计数器减少了1，意味着共减少了k。而在出现减少的时候，应该往内存里放的元素并没有放到内存中，也就是说未计入输入元素的此次出现，因此，每次计数器减少的步骤相当于减少了k+1。整个数据流的元素总数是m，内存中保存的计数总数是m′，每一轮计数器减少步骤减少了k+1，那么应该有（m-m′）/（k+1）个计数器减少步骤，这也就意味着fa和fa最多相差（m-m′）/（k+1），即。■
由上述分析可见，当数据流中元素的总数远大于（m-m′）/（k+1）时，可得到频繁项的一个好的估计。而且错误的界限和k成反比，因为k越大估计值和真实值相差越小，即内存越大误差越小。
可以利用略图计算错误的界限，在内存中记录m、m′和k，然后，把内存里最后一个频繁元素再加上相差的值，就可以得到频繁元素真实值的一个上界，而内存中保存的估计值是频繁元素的一个下界。在频繁元素的真实值范围之内，估计就准确得多。该算法有效的原因源于Zipf原则，就是说极少数元素出现的次数非常多，而大多数元素出现的次数非常少。