url排重和bloom filter(转载)

from http://blog.csdn.net/accesine960/archive/2007/01/23/1491483.aspx.

误差换效率

google黑板报上一片文章,讲Url排重用到的一个技巧:把平均长度较长的Url转换成平均长度较短的GUID来节省空间。在Url排重方面还有一个常用的算法:Bloom Filter 算法。Bloom Filter 算法是查看元素E是否在集合S中存在的快速算法,典型的应用就是拼写检查spellcheck时,查看某个单词是否在字典中存在。关于查询的算法有很多种了,排序折半、B-Tree、Hash-Code 等等。Bloom Filter 的优点是什么呢?

1、Bloom Filter不存储key-value值,Bloom Filter 用一组Hash算法把集合S中的元素E换算成位表示;

2、查询速度快。

我们知道Hash算法一般都有冲突,在Bloom Filter中的冲突就表现为误差了。

Bloom Filter 是一种常见的算法,现在已经有了 Java , C++ , C# , ruby 等各个版本的算法。当然也有很多变种出现以适应更多的需求。

Bloom Filter 是有误差的,但误差在可控制的程度内。换句话说,大多数的误差的恼人之处在于我们无法衡量它。

参考阅读:

http://blog.likeshow.net/article.asp?id=34

http://blogs.msdn.com/devdev/archive/2006/01/23/516431.aspx

http://en.wikipedia.org/wiki/Type_I_and_type_II_errors

http://en.wikipedia.org/wiki/Bloom_filter

http://jaspell.sourceforge.net/javadocs/index-files/index-2.html

http://blogs.msdn.com/devdev/archive/2005/08/17/452827.aspx

http://www.cc.gatech.edu/fac/Pete.Manolios/research/bloom-filters-verification.html

http://homepages.inf.ed.ac.uk/s9902505/specksim/doc/index-files/index-2.html

http://weblogs.asp.net/dfindley/archive/2004/08/19/217485.aspx

http://www.darkridge.com/~jpr5/archive/dads/HTML/bloomFilter.html

http://loaf.cantbedone.org/

Advertisements
url排重和bloom filter(转载)

Leave a Reply

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 / Change )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s