基于布鲁姆过滤器的文本检索系统研究

赵扬名，程耕国，鲍考明

（武汉科技大学 信息学院，湖北 武汉 430081）

当今世界信息技术迅猛发展，人类社会正进入一个信息化的社会，社会经济的发展对信息资源、信息技术和信息产业的依赖程度越来越大。信息将成为决定企业生存与发展的关键因素之一[1]。搜索引擎作为一个网络应用，已经成为人们查询信息的重要工具之一。它可以使人们从Internet大量纷杂的信息中，找到与主题相关的信息，为人们查询信息提供了方便。但是由于中文自身的特点，目前的搜索引擎往往返回给用户成千上万个检索到的页面，且其中很大一部分是重复的或与用户检索要求不相关的内容。这些内容被认为是无效信息。同时与西文相比，中文信息检索和文本检索存在着很多的问题：在词语切分时存在大量切分歧义，大量专业术语的错误划分，专有名词的识别困难以及汉语的自然语言处理准确性低。由于智能文本检索和文本挖掘的基础是自然语言处理，汉语自然语言处理的自身的难点成为文本检索和文本挖掘处理的关键问题，因此要进一步提高汉语信息检索和文本挖掘处理的准确性。

1 Bloom Filter的基本原理

Bloom Filter[2]由Bloom于1970年提出。Bloom Filter对数据集合采用一个位串表示，能有效支持集合元素的hash查找，是一种能够表示集合、支持集合查询的简洁数据结构，能够有效地过滤掉不属于该集合的元素。

标准布鲁姆过滤器算法具体描述如下，数据集合X={x1，x2，…，xn}共有 n 个元素通过 k 个哈希函数 h1，h2，…，hk映射到长度为m的位串向量BitSet中。通常，布鲁姆过滤器表示的汇总信息就是向量BitSet，第i个哈希函数对数据集合内的元素xn哈希的结果记为 h（i，xn），每一个哈希函数相互独立且函数的取值范围为{0，1，…，m-1}.

算法基本操作包括元素查询操作和插入操作。元素查询操作就是利用布鲁姆过滤器判断元素是否在集合中。布鲁姆过滤器在使用前必须初始化，即将BitSet向量的各位初始化为0。

图1 BitSet向量的初始状态Fig.1 Initial state of the BitSet vector

1）元素插入操作，如图2所示：

①计算元素 X 相应的 k 个哈希地址，即 h（1，x），h（2，x），…，h（k，x）；

②把向量 BitSet中对应的第 h（1，x），h（2，x），…，h（k，x）位设为1。

注意：当一个位置或多个位置被置为1时，那么只有第一次会执行，后面几次将不会对其做任何操作。

图2 标准布鲁姆过滤器的元素插入Fig.2 Element insertion of the standard Bloom Filter

2）元素查询操作，也有两个步骤：

①计算 x 的 k 个哈希地址，即 h1（x），h2（x），…，hk（x）；

②检查布鲁姆过滤器表示汇总信息的向量BitSet中这k个相对应的位置是否都为1，它们只要有一个是0，x必不在集合中，如果全为1，则可以“认为”x在集合中。

事实上若一个元素对应的位置全为1，实际上是不能100%的肯定该元素被Bloom Filter记录过的。因为有可能该元素的所有位都刚好是被其他元素所对应，这种将元素划分错的情况，称为假阳性误判。如图3所示，元素x不属于集合，但属于集合的元素a，b，c将x的映射地址置位，导致误判x在集合中[3]。

图3 布鲁姆过滤器假阳性Fig.3 False positive of the Bloom Filter

2 MD5算法

MD5（中文名为消息摘要算法第五版）为计算机安全领域广泛使用的一种散列函数，用以提供消息的完整性保护。它是为了解决MD4的碰撞而生的。可以说是MD4的加强版，面向32位机器。对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由4个32位分组组成，将这4个32位分组级联后将生成一个128位散列值。由此可知，任意明文的输入，经过MD5算法后都可以生成128位的消息输出，并且不同的明文输入使它们的输出相同在计算上是不可行的[4]。

3 在文本检索系统中新算法的设计

在文本检索系统中的用户一般具有两种角色，具有查询权限的角色和添加权限的角色，其中查询权限算法的具体流程图如图4所示。

图4 查询权限算法流程图Fig.4 Algorithm flow chart of the query

添加权限算法的具体流程图如图5所示。

4 性能分析

图5 添加权限算法流程图Fig.5 Algorithm flow chart of the add

不论是查询算法还是添加算法的错误率都来自于Bloom Filter的假阳性错判fp，因此，在实际应用中必须对fp进行评估，设计合适的布鲁姆过滤器，降低fp的影响[5]。n为集合X的元素个数，m为向量BitSet的长度，k为哈希函数的个数。

假设向量BitSet中任一bit位为0的概率是p，那么任一bit位为1的概率是p-1，假设哈希函数值服从均匀分布，则当集合中所有的元素都映射完毕后，BitSet中任意一位为0的概率是：

当不属于集合的元素误判断属于集合时，元素在BitSet向量的对应位置都必须为1。即元素的误判率为

即

由公式可知，当集合元素个数n和向量空间的长度m一定时，当且仅当k=ln 2·m/n时，布鲁姆过滤器fp最小。

使用标准布鲁姆过滤器，增加一个元素到集合，需要进行k次哈希运算，其一次元素插入操作的时间复杂度为O（k）。当判断元素是否在集合中时，同样需要进行k次哈希计算，完成一次元素查询的时间复杂度为O（k），因此布鲁姆过滤器最大的特征是空间简洁和查询方便。

而布鲁姆过滤器的狭隘性同样明显。多样性的网络应用带来了多样性的操作集合，布鲁姆过滤器作为一种表示集合的数据结构，集合是布鲁姆过滤器算法实施的对象和前提。但是，现有的布鲁姆过滤器对集合的表示大多限制为数字或者类似数字组成的集合，即将非数值集合的元素转换成一定范围的数值数据。这种对数据集合形式的限制，成为布鲁姆过滤器在持续发展的网络中广泛应用的绊脚石。本文利用MD5的可以把任何明文输入转换为128位散列值和可靠性高的特性，将Bloom Filter应用于文本检索系统[6]。

5 结束语

总之，Bloom Filter空间简洁的特性使其在搜索系统上大有可为，而MD5生成的128位散列值的唯一性，又满足了Bloom Filter对数据集合的要求。合理的设计哈希函数的个数可以将假阳性误判降至最低，因此本文设计的算法必然可以充分应用于搜索系统，网页去重，垃圾邮件过滤等方面，为实现更多互联网的应用发展提供帮助和支持。

[1]James KM.A second look at Bloom filters[J].Communiations of the ACM，1983，26（8）：570-571.

[2]Burton HB．Space/Time trade—offs in hash coding with allowable errors[J]．Communications of the ACM，1970（13）：422-426．

[3]Mitzenmacher M．Compressed Bloom filters[J]．IEEE—ACM Trans．on Networking，2002（10）：604-612．

[4]RivestR.TheMD5 Message-DigestAlgorithm[R].1 RFC1321，1992.

[5]Broder A，Mitzenmacher M.Network applications of bloom filters a survey[J].Internet Mathematics，2004（1）：485-509.

[6]谢鲲，文吉刚，张大方，等．布鲁姆过滤器查询算法[J]．软件学报，2009（20）：96-108.XIE Kun，WEN Ji-gang，ZHANG Da-fang，et al．Bloom filter query algorithm[J]．Journal of Software，2009（20）：96-108.