Flajolet-Martin算法

先说说Flajolet-Martin(后面简称FM)算法能干什么吧。假设我们有1万个int型数字(可重复的),我们想找出这个数字集合中不重复的数字的个数。怎么办呢?很简单,将这1万个数字读进内存,存放到hashset中,那么hashset的size就是不重复数字的个数。接下来,问题变得更加的复杂,有100亿个数字,怎么办? 全部读取到内存中可能会有问题,如果这其中有1亿个不重复的数字,那么至少需要内存 100M * sizeof(int),内存也许不够。
FM算法就是为了解决这个问题。假设n个object,其中有m个唯一的,那么FM算法只需要log(m)的内存占用(实际操作中会是k*log(m)),以及O(n)的运算时间。当然,FM的问题是,它的结果只是一个估计值,不是精确结果。

原理

假设我们有一个非常好的hash函数,它能够将object哈希成一个二进制数0101…,并且非常均匀的打散到二进制空间。如果有8个唯一的object,将它们全部hash之后,结果按照概率应该有4个object的hash num是以0结尾。这4个hash num中又应该有两个结尾是00,两个中又有一个结尾应该是000。
OK,那么现在反过来理解一下。现在有十几个object,将它们全部hash之后,结果中有一个hash num的结尾是000,并且存在结尾是00和0的hash num,那么,我们就可以猜测,这些object中唯一的数量是8。
形式化定义:对于n个object,如果他们的hash结果中,结尾连续0的长度的最大值是m(当然,也存在连续0长度是m-1, m-2, … 1的结尾),那么,可以估计唯一的object的数量是 2^m。

在某种意义上,FM和Bloom Filter有着类似的地方,都是用hash函数来节约需要用到的内存量,并且结果都是不精确的。

理论上的证明可以看原始的paper:Probabilistic Counting Algorithms for Data Base Applications

具体实现

这里给出了非常具体的算法步骤和Java版的代码:

FM

Tips

具体实现中,并不会只使用一个hash函数,而是会使用很多组hash group,每一组hash group中又包括了多个不同的hash函数。这样做的目的,是提高最终结果的精度。每一个组的结果是由这个组中每个hash函数计算结果的平均值,然后所有组的结果做排序,取中位数作为最终的输出结果。
在我的观察中,多设置一些hash group对于结果的准确非常有用。

另外,hash函数的算法对于最终结果的影响也非常重要,不同的输入数据要选择不同的hash函数,选择的标准就是它能够将输入数据平均的映射到hash空间中,保证hash结果的随机性。原始paper和Java版代码中的hash函数的假设都是输入为string类型的数据,当我将它们应用到int型的输入中,效果非常不好。所以,选择合适的hash函数很重要。

—END—

Advertisements
相册 | 此条目发表在Large Scale分类目录。将固定链接加入收藏夹。

2 Responses to Flajolet-Martin算法

  1. Pingback引用通告: Large-scale Graph的closeness centrality计算 | Great Power Law

  2. Pingback引用通告: Flajolet-Martin算法及其应用 | Plus·中国

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s