beta's blog

前言

寻找数据流中出现最频繁的k个元素，这个问题和自己目前的研究兴趣有很大的相关性，只不过在具体的场景中可能有其他的限制条件，但抽象的问题并没有实质的区别。

两个问题存在本质的区别:

查找频率超过p*M 的元素

查找 Top-K的元素

问题1. 查找频率超过p*M的元素

数据流大小为M, 令寄存器数量为1/p, 那么一定可以保证频率超过p的元素都找到, 假设数量为a. 对于此问题, 不会存在假阳性的问题.

问题2. 查找Top-k元素

如果将k作为寄存器的数量, 那么可以保证频率大于1/k的元素都会被找到,假设数量为a. 但是我们无法保证a=k, 实际上,当数据倾斜较大时, a«k. 因此会有(k-a)个元素类别因为顺序等原因无规则的出现在k个寄存器中, 这就是误差,或者假阳性, 也会有假阴性.

问题1 和问题2的联系

为了使Top- k的误差变小, 那么会设寄存器数量为n, n >k, 那么此时可以保证频率超过1/n的元素都入选,记为a1;频率超过1/k的元素数量记为a2.

显然有a1>a2. 我们希望a1尽可能地接近k,即 k>a1>a2. 所以花费内存的开销可以提高Top-K解决方法的accuracy.

1.Hashmap + 最小堆

这是最直观的想法，使用hashmap存储所有的<string,int>存放所有元素出现的次数；用容量为k的min-heap存放目前出现过的最频繁的k个元素。

具体插入流程：

每次从数据流中提取数据，如果在Hashmap中存在，则把相应的计数器加1；如果不存在，则将该元素插入到hashmap中，初始为1；
在min-heap中遍历查找该元素，

2.1 如果找到，则把堆里的计数器加1，并向下调整堆；

2.2 如果没找到，并且堆未满，则在堆尾插入该元素，向上调整，

2.3 如果没找到，并且堆已满，则将该元素的次数与堆顶比较，若大于堆顶元素的次数，则将堆顶替换为该元素，并向下调整

2.frequent algorithm

首次由Misra和Gries提出，思路很简单，保存k个<item,count>组成的条目，核心的想法是，每次到达的元素若在条目中，则元素对应的条目计数加一，否则所有的条目计数减一。因为如果一个元素的频率大于N/K, 那么每次减少都可以被抵消。伪代码如下：

输入：N为数据流项集合，T为存储条目集合
T <- Φ
for each i in N:
	if i ∈ T
		count[i] <- count[i]+1;
	else if |T|<k
		T <- T ∪ {i};
		count[i] <- 1;
	else
		all counter decrease 1;
		if count[j] ==0 T <- T\{j}

可以很明显的看出，对于top-k寻找而言，若该元素的频率大于N/k，则一定会被找出，但是频数估计会存在较大误差；并且top-k不一定能保证前k项都大于N/k，所以也会出现精度的误差

3.space saving

基于计数的方法

1.Majority算法

思路

遍历数组,如果前后两个元素不相同,则将两个元素都消除,最终剩下的元素一定是出现次数超过一半的元素.

具体操作,存储一个<key,count>,在遍历的过程中,如果遇到的元素与key相同,则count+1;如果不相同,则count-1;弱count为0,则是key为新元素,count为1.

2.Misra-Gries算法

问题: 找出长度为m的数据流S中, 出现频率超过 m/k的元素

Majority问题可以看作是此问题k=2时的特例.

基于Majority的计数器思路, 维护k-1个<key,count>数组:

如果元素在数组中,则将对应的计数器加1
如果元素不在数组中,并且数组未满;则将元素加入数组,count记为1
如果元素不再数组中,并且数组已满; 则将数组内所有的计数器自减, count为0的元素移除

每次自减操作都会减去k个项,所以不会有频率大于m/k的元素丢失.

反证法: 如果频率大于m/k 的元素也被删除,那么自减操作至少执行了m/k + 1次,而每次自减操作都会删除k个项.因此会删除m+k 个项,这是不可能的.

实际上,自减操作最多为(m-1)/k向下求整次数

算法结果有如下性质:

对元素频率的估计偏低
K越大,频率估计的误差越小
最终结果可以保证没有假阴性,即不会漏掉大于m/k的元素.但会出现假阳性,即混入实际频率低于m/k的元素

3. Lossy Counting算法

问题: 找出长度为m的数据流中,出现频率超过s的元素

Lossy Counting定义两个参数,一个是阈值s,另一个是误差 p(p«s).

过程:

将数据流划分为固定大小的多个窗口,

从第一个窗口开始,计算每个元素的频率. 在统计结束之后,将每个元素减1, 计数为0的元素从内存中删除.

接着,处理下一个窗口的元素, 同样在窗口结束的时候, 将每个元素的计数减1,同时清除计数为0的元素.

显然, lossy counting也是近似算法. 在误差为p时, 窗口大小设定为1/p, 窗口数量为m*p, 由于每个窗口结束计数器都会减1,所以一个元素的最大误差为p *m. 所以最后的元素频率一定超过(s-p) * m

通过比MG算法更多的空间,换取更小的误差.

4.Space Saving算法