Skip to content

Misra-Gries

目标

找出所有的 \(\epsilon\)-Heavy Hitters, 并最小化时间、空间复杂度

算法

从 \(\epsilon = 0.5\) 开始

此时找出的数出现了一半以上，我们叫他 Majority element

我们知道，如果一个数出现了一半以上，那么如果他和其他数两两抵消，最后还是他剩余

所以我们想到了这样一个算法：

function majority_element():
    memory = empty and counter = 0
    when a arrives:
        if counter == 0:
            memory = a and counter = 1
        else if memory == a:
            counter++;
        else 
            counter--;

memory 用来存数据，counter 用来存出现次数

如果 majority element 存在，即有数出现了一半次数以上，最后剩下的就会是这个数

这是因为不同的数会两两抵消，而 majority element 一定会剩余

这个算法也叫 Moore's Vote Algorithm

扩展到一般情况

我们创建一个大小为 \(k=\lceil\frac1\epsilon\rceil-1\) 的 memory 数组 和 counter 数组，于是我们有：

function Misra_Gries():
    memory = empty and counter = 0
    when a arrives:
        if there is j that memory[j] == a:
            counter[j]++;
        else if there is empty memory cell:
            memory[j] = a and counter[j] = 1
        else 
            for every j: 
                counter[j]--;
                if counter[j] == 0:
                    discard(memory[j])

这样，我们把出现次数多的数和出现次数少的数相互抵消，最后剩下的是次数多的数

最后剩下的数组为估计数组

一些证明

\(0 \leq f(i) - \hat f(i) \leq \frac{n}{k+1} \leq \epsilon \cdot n\)

这里 \(f(i)=count(i)\), \(\hat f(i)=est(i)\), 表示 \(i\) 这个数的实际数量和估计数量

由于我们每次只会丢弃，不会凭空新增，所以 \(f(i) \geq \hat f(i)\), 所以左式成立

同时，每次丢弃相当于长度为 \(k\) 的数组满了，那么我们将当前这一条数据和数组中的 \(k\) 条数据都丢弃，而一共有 \(n\) 条数据，所以最多丢弃 \(\frac{n}{k+1} \leq \epsilon \cdot n\) 次， 故右式成立

每条满足 \(f(i)>\epsilon \cdot n\) 的数据都会被留在最终结果中

由上面的引理，我们有 \(\hat f(i)\geq f(i) - \epsilon \cdot n > 0\), 因为只有 \(\hat f(i) >0\) 的数留在了最终数组里

所以 \(f(i)>\epsilon \cdot n\) 的数据 \(i\) 都会被筛出来，不过数组中也会存在一些频率小的数据，这些数很少，只要遍历数组判断即可

时间，空间复杂度

假设值域为 \(D\), 流为 \(S\)

那么空间复杂度为 \(O(k(\log D + \log S))\)

时间复杂度为 \(O(n\cdot \phi(n))\), 这里 \(\phi(n)\) 是指搜索的时间复杂度，可以用 hash 做到 \(O(1)\)

原因是每次搜索后操作都是 \(O(1)\) 的，而删除最多删除 \(n\) 次，每次删除也是 \(O(\phi(n))\) 的

所以单次最坏 \(O(k\cdot \phi(n))\), 总复杂度是 \(O(n\cdot \phi(n))\) 的

弊端

不能处理 deletion。考虑前 \(k-1\) 个数是 \(1\), 最后一个数是 \(m\), 我们再加一个 \(1\) 进来，此时前 \(k-1\) 个数变为 \(0\), 最后一个数变为 \(m-1\)

但是，如果我们又要删除第 \(1\) 个数，他此时已经不存在于当前搜索树中，所以不能够处理；同时，由于第 \(2\) 到 \(k-1\) 个数也都被删除，我们不知道那些数被删除，所以我们没法把当前状态还原为之前加操作前的状态

解决 deletion

构造一个概率

所以我们有另一种处理这个问题的数据结构：哈希

现在我们的最终目的是要找到一种 hash 函数使得查询 \(count(i)\) 时，返回的 \(est(i)\) 满足：

\(\displaystyle Pr[|est(i)-count(i)|\leq \epsilon\cdot n] \geq 1-\delta\)

那么我们将 每个数 \(i\) 用 hash 映射到 \([0,k-1]\) 上，如果是 add 操作就 \(A[h(i)]++\), del 操作就 \(A[h(i)]--\)

最后我们有 \(est(i)=A[h(i)]\)

但是 \(k\) 小于 \(n\), 所以一定会有冲突

为什么我们不使用大小为 \(n\) 或更大的表，其实也是为了和之前算法的 \(O(k\log t)\) 空间复杂度对齐

具体地，我们要找到一种 universal 的 hash 函数，这种函数满足:

\(Pr[h(x)=h(y)]\leq \frac1k\)

至于这个 hash 函数具体是什么，就不具体说了，~~因为我不知道~~

你可以假设我们总能找到这样一族 hash 函数 \(H\)

我们写出 \(est(i)\) 的表达式：

\(est(i)=\sum_{j\in D}count(j)\cdot[h(i)==h(j)]\)

\(=count(i)+\sum_{j\not= i}count(j)\cdot[h(i)==h(j)]\)

注意到这里的 \(est(i)>count(i)\), 即每个 \(A[h(i)]\) 都是 \(count(i)\) 的一个过度估计，与之前不同

\(\therefore est(i)-count(i)=\sum_{j\not= i}count(j)\cdot[h(i)==h(j)]\)

\(\therefore E[est(i)-count(i)]=E[\sum_{j\not= i}count(j)\cdot[h(i)==h(j)]]\)

\(=\sum_{j\not= i}count(j)\cdot E[[h(i)==h(j)]]\)

\(=\sum_{j\not= i}count(j)\cdot Pr[h(i)==h(j)]\)

\(\leq \sum_{j\not= i}count(j)\cdot \frac1k\)

\(=\frac{|S|-count(i)}k \leq \frac {|S|}k = \epsilon \cdot n\)

所以期望来说，我们有 \(0\leq est(i)-count(i)\leq \frac {|S|}k\)

同时我们说在 \(\frac12\) 的概率下 \(est(i)-count(i)\leq \frac {2|S|}k\)

感性理解一下，这是因为如果在 \(\frac12\) 的概率下 \(est(i)-count(i)> \frac {2|S|}k\), 这部分期望和另外 \(1/2\) 期望加和，期望还要满足 \(\leq \frac {|S|}k\)， 就说明另一部分期望一定 \(<0\), 而 \(est(i) \geq count(i)\), 矛盾

所以，我们从函数族 \(H\) 中取 \(m\) 个 hash 函数 \(h_1,\cdots,h_m\)

每次 add 操作为 \(A[h_t(e)]++\), del 操作为 \(A[h_t(e)]--\)

最后取出 \(best(e)=\min est(i)=\min_{t=1}^mA[h_t(e)]\)

这样我们失败的概率为 \(\delta = \frac1{2^m}\)

我们令 \(k=\frac2{\epsilon}, m=\log_2(\frac1{\delta})\), 那么我们就得到了上面的式子：

\(\displaystyle Pr[|est(i)-count(i)|\leq \epsilon\cdot n] \geq 1-\delta\)

意义

按照之前算法的分析方式，我们有了 \(|est(i)-count(i)| \leq \epsilon \cdot n\) 后，那么如果 \(count(i)>\epsilon \cdot n\), 那么 \(est(i)>0\), 所有重要元一定被包含

但是，这是废话，所有 \(est(i)>0\) 都满足

那么我们可以反过来筛选

我们根据 \(est(i)-count(i)\leq \epsilon \cdot n\), 所有 \(count(i)\leq \epsilon \cdot n\) 的元素满足 \(est(i) \leq 2 \epsilon \cdot n\)

所以满足 \(est(i) > 2\epsilon \cdot n\) 的一定是最大元

剩下的元素里面，所有 \(est(i)\leq \epsilon \cdot n\) 的一定不是最大元，因为\(est(i)\geq count(i) > \epsilon \cdot n\)

所以筛选掉这一部分，我们只需要检查 \(\epsilon \cdot n < est(i) \leq 2\epsilon \cdot n\) 这一部分的元素，加上 \(est(i) > 2\epsilon \cdot n\) 的元素，就得到了所有重要元

复杂度

空间复杂度：一共 \(O(m\cdot k)\) 个 counter, 每个 \(O(\log S)\) 位

同时有 \(O(m\cdot \log D)\) 空间用来存储 hash 函数

最终复杂度为 \(O(\frac{\log{\frac1{\delta}}\log S}{\epsilon} + \log{\frac1{\delta}}\log D)\)

时间是 \(O(mn\cdot f(n))\), \(f(n)\) 是 hash 函数的复杂度，可视为 \(O(1)\)

\(m\) 取成常数，就是 \(O(n)\) 的复杂度