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
