基于布魯姆過濾器的文本檢索系統研究

趙揚名，程耕國，鮑考明

（武漢科技大學 信息學院，湖北 武漢 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.