大数据基础-亚线性空间算法总结-近似计数+不重复元素

近似计数1近似计数解决什么问题

当数据特别大的时候，在二进制的条件下，存储一个数字N，需要log（N）的空间，如果N特别大而且这样的N又特别的多，该怎么办呢？我们的解决办法是行省一些准确性，从而节省更多的空间。使用近似计数算法，每一个数字的存储只需要loglog（N）的空间复杂度就行了。

流模型的计数问题

流模型

定义一个数据流,

,频率向量$

i \in [1,n] , f_{i} \in [1,m]

。

数

据

流

是

无

限

的

，

当

数

据

流

流

过

个

时

，

出

现

了

个a_{i}$。请设计一个算法记录N的大小，要求空间复杂度为loglog（N）。

morris算法

算法

将X初始化为0

循环

如果

出现一次 就以

的概率将X增加1

返回

证明的目标

我们期望返回的值与N的差别尽量小，换句话说就是如果

与N的差的绝对值大于某一个很小的值的概率很小，那么我们就可以用这种方法进行计数。说得更通俗一点就是使这个算法计算出的结果偏离N不多，或者偏离太多的概率特别小。

利用切比雪夫不等式证明这一点

。

证明

计算期望

。（公式推导请见附录1）

计算方差

=

。（公式推导请见附录2）

令切比雪夫不等式中的

。

其中，

指的是

最终的值，下标指的是在这个计数器在流模型中经历了

个数字。则最终得到公式

。

设定