爱.港湾

这是前两天看到Bloom Filter算法想到的一个问题。加上我自己的一些想法，写了这篇文章。

首先介绍一下Bloom Filter算法，中文叫做布隆过滤器，通常用于集合的判断存在问题。比如要判断一个元素是否在已有的集合中时用该算法就比较快捷而且比较节省空间，但是其最大的特点就是不准确，容易出现判断错误，导致将不该过滤掉的元素过滤掉。（关于Bloom Filter算法，详细参见http://blog.csdn.net/godfrey90/archive/2011/06/20/6557113.aspx）

对于一个算法而言，我们考虑的无非是首先准确性，然后在准确的基础上再考虑时间和空间复杂度的问题。我们通常会权衡时间和空间，有时需要牺牲时间换取空间，有时需要牺牲空间换取时间，而对于时间和空间复杂度都很低的算法是很少的。

但是，从Bloom Filter算法中我看到了一个理念，就是根据需求制定解决方案。在对于算法的研究时我们通常希望得到绝对准确的算法来解决问题。但是在实际应用当中，我们往往不需要绝对准确的结果，一个时间复杂度和空间复杂度都很低而且准确率达到一个可以接受的范围的时候，这个算法往往能得到青睐。

Bloom Filter算法有一个应用就是在搜索引擎方面，在搜索引擎爬取网页时需要从网页中提取出链接以备继续爬取。在提取链接的时候要进行一项判断，即这个链接是否在已经爬取过的链接的集合中，如果在集合中的话，就跳过以防止重复爬取；如果不在集合中的话就进行爬取，并且把链接放到集合中。

其实搜索引擎爬取网页的这个思路很像宽度优先搜索，在宽度优先搜索中也有这样的一个判断重复的步骤，但是通常情况下的宽搜要求严格的没有遗漏。但是对于网页爬取这样的程序而言是可以容忍一定概率的遗漏的。这样的程序更看重的是时间复杂度和空间复杂度，也就行性能标准。这样的话就将算法的准确性，时间复杂度和空间复杂度放在一起进行权衡了。

在概率统计学上来讲，在可以容忍的错误范围里，达到一定概率的准确性可以认为是足够准确的了。而在实践中我们需要的往往就是一个准确的概率，而非绝对的准确。

回到宿舍和舍友讨论准确性的问题，又想到了对于软件测试。他说，用写的测试程序去测试一个程序，是不能保证准确性的，因为测试程序也可能出错，那么就需要在写测试程序的测试程序，这样的话就不可能有绝对准确的时候。我说，确实是这样的，但是，用测试程序去测试一个程序，这样可以大大的提高了被测程序的准确性，当它的准确性达到了我们期望的概率值以上的时候我们就可以认为它是准确的了，而不需要绝对的准确。

对于准确的概念，其实世人还有其他的理解。搞物理的人都知道，一个理论在没有被证明是错误的时候我们就认为它就是正确的，爱因斯坦就是这样将他的相对论推广出来的，他没有办法证明相对论的正确性，但是没有人可以推翻它，所以世人就认为它是正确的了。

所以说或许这个世界上没有绝对的准确，如果我们都认为它是准确的，那么就可以说它就是准确的了。

Tags: Bloom Filter, 准确性, 搜索引擎, 相对论, 算法