Misra-Gries 算法

Misra-Gries 算法

 

Misra-Gries算法是频繁项挖掘中一个著名的算法。频繁项就是在数据流中出现频率最高的数据项。频繁项挖掘，这个看似简单的任务却是很多复杂算法的基础，同时也有着广泛的应用。

Misra-Gries算法的思路很简单，就是类似“俄罗斯方块”，即不满就放入，如果满了就消掉一行，每个记录中的项都减一；

但是，在搜寻资料中，我发现了很大的出入：

 

公认无误的逻辑是，

① 运算逻辑是：不满就放入，如果满了就消掉一行，每个记录中的项都减一；

② Misra-Gries算法输出的数据项并不一定是频繁项，但是频繁项一定在输出结果之中。

③ 频繁项（频数>=n/k）要出现在最终的结果里

 

但是我在网上找的很多资料都是如出一辙，都是逻辑上“一旦满了k个，立即同时消去一个”，我认为这个逻辑不太对。

（我认为逻辑有瑕疵的代码）代码一：

def misra_gries(S,k):
    c = {}
    for i in S:
        if i in c:
            c[i]+=1
        elif len(c) < k-1: ### 我认为此处有瑕疵
            c[i]=1
        else:
            for j in list(c):
                c[j]-=1
                if c[j]==0:
                    c.pop(j)
        print (c)
    return list(c)

我认为，当占位达到k个时，不应当马上消去，而是直到有新的加入，在想办法消除一位。

修正版代码，代码二：

def misra_gries(S,k):
    c = {}
    for i in S:
        if i in c:
            c[i] += 1
        elif len(c) < k: 
            c[i] = 1
        else:
            sig = 0
            while(sig == 0): #需要直到空出一位才可以
                for j in list(c):
                    c[j] -= 1
                    if c[j]==0:
                        c.pop(j)
                        sig = 1
                        c[i] = 1
        print (c)
    return list(c)

最简单的拿 k=3，S={a,b,c,a,b,d,a,b,e}这个序列来说，正常结果应当包括a,b这两个频繁项，但是如果按照代码一，一旦满三个立即消去，那结果一个不剩，显然违背 “Misra-Gries算法输出的数据项并不一定是频繁项，但是频繁项一定在输出结果之中”这一条效果！！！

 

 

相关资料：

Misra-Gries 算法

Misra-Gries算法---简书