Haskell中使用 BloomFilter 的经历

[Albert Lee]

今天一个统计任务，需要从一个巨大的列表（几亿条）中找出属于另一个小点的列表的记录，小表有3千多条。

使用bloomfilter 算法简化，bloomfilter 的介绍在谷歌中文blog上有一篇。 简单的说就是用一个位串做筛子，用一组hash
函数作映射。 先用小表创建这个位串过滤器，形象的说就是在纸带上打孔。 全都打好后，用这个筛子来过滤大表，大表中的元素经过hash函数，如果能全
部通过纸带上的孔，就算通过，否则就过滤掉。

bloomfilter 的一个特点是：过滤有误差，误差通过过滤函数以及位串的长度两个变量可以计算出来。

Haskell hackage 上有一个 bloomfilter 的库，很易用。

安装： cabal install bloomfilter

http://hackage.haskell.org/package/bloomfilter

Data.BloomFilter
* Data.BloomFilter.Easy
* Data.BloomFilter.Hash

使用的时候， 先通过 suggestSizing 函数获得推荐的 hash函数个数以及位串长度：

suggestSizing Source
:: Int expected maximum capacity
-> Double desired false positive rate (0 < e < 1)
-> (Int, Int)

然后创建一个过滤器：

fromListB Source
::
=> a -> [Hash] family of hash functions to use
-> Int number of bits in filter
-> [a] values to populate with
-> Bloom a

例如： filt = fromListB (cheapHashes 3) 1024 ["foo", "bar", "quux"]

使用过滤器过滤值：

elemB :: a -> Bloom a -> Bool

[刘鑫]

喵的为毛我想到的都有人做过了……

--
您收到此邮件是因为您订阅了 Google 网上论坛的“haskell.cn”论坛。
要向此网上论坛发帖，请发送电子邮件至 hask...@googlegroups.com。
要取消订阅此网上论坛，请发送电子邮件至 haskellcn+...@googlegroups.com。
若有更多问题，请通过 http://groups.google.com/group/haskellcn?hl=zh-CN 访问此网上论坛。

--
“那么告诉我，路西法·晨星，问问你们自己，你们所有人……若是十万天使军不再梦想天堂，地狱又有什么伟力？”——尼尔·盖曼《睡魔》
……

劉鑫
March.Liu