基于布魯姆過濾器的文本檢索系統(tǒng)研究

趙揚(yáng)名，程耕國，鮑考明

（武漢科技大學(xué) 信息學(xué)院，湖北 武漢 430081）

當(dāng)今世界信息技術(shù)迅猛發(fā)展，人類社會正進(jìn)入一個(gè)信息化的社會，社會經(jīng)濟(jì)的發(fā)展對信息資源、信息技術(shù)和信息產(chǎn)業(yè)的依賴程度越來越大。信息將成為決定企業(yè)生存與發(fā)展的關(guān)鍵因素之一[1]。搜索引擎作為一個(gè)網(wǎng)絡(luò)應(yīng)用，已經(jīng)成為人們查詢信息的重要工具之一。它可以使人們從Internet大量紛雜的信息中，找到與主題相關(guān)的信息，為人們查詢信息提供了方便。但是由于中文自身的特點(diǎn)，目前的搜索引擎往往返回給用戶成千上萬個(gè)檢索到的頁面，且其中很大一部分是重復(fù)的或與用戶檢索要求不相關(guān)的內(nèi)容。這些內(nèi)容被認(rèn)為是無效信息。同時(shí)與西文相比，中文信息檢索和文本檢索存在著很多的問題：在詞語切分時(shí)存在大量切分歧義，大量專業(yè)術(shù)語的錯(cuò)誤劃分，專有名詞的識別困難以及漢語的自然語言處理準(zhǔn)確性低。由于智能文本檢索和文本挖掘的基礎(chǔ)是自然語言處理，漢語自然語言處理的自身的難點(diǎn)成為文本檢索和文本挖掘處理的關(guān)鍵問題，因此要進(jìn)一步提高漢語信息檢索和文本挖掘處理的準(zhǔn)確性。

1 Bloom Filter的基本原理

Bloom Filter[2]由Bloom于1970年提出。Bloom Filter對數(shù)據(jù)集合采用一個(gè)位串表示，能有效支持集合元素的hash查找，是一種能夠表示集合、支持集合查詢的簡潔數(shù)據(jù)結(jié)構(gòu)，能夠有效地過濾掉不屬于該集合的元素。

標(biāo)準(zhǔn)布魯姆過濾器算法具體描述如下，數(shù)據(jù)集合X={x1，x2，…，xn}共有 n 個(gè)元素通過 k 個(gè)哈希函數(shù) h1，h2，…，hk映射到長度為m的位串向量BitSet中。通常，布魯姆過濾器表示的匯總信息就是向量BitSet，第i個(gè)哈希函數(shù)對數(shù)據(jù)集合內(nèi)的元素xn哈希的結(jié)果記為 h（i，xn），每一個(gè)哈希函數(shù)相互獨(dú)立且函數(shù)的取值范圍為{0，1，…，m-1}.

算法基本操作包括元素查詢操作和插入操作。元素查詢操作就是利用布魯姆過濾器判斷元素是否在集合中。布魯姆過濾器在使用前必須初始化，即將BitSet向量的各位初始化為0。

圖1 BitSet向量的初始狀態(tài)Fig.1 Initial state of the BitSet vector

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

①計(jì)算元素 X 相應(yīng)的 k 個(gè)哈希地址，即 h（1，x），h（2，x），…，h（k，x）；

②把向量 BitSet中對應(yīng)的第 h（1，x），h（2，x），…，h（k，x）位設(shè)為1。

注意：當(dāng)一個(gè)位置或多個(gè)位置被置為1時(shí)，那么只有第一次會執(zhí)行，后面幾次將不會對其做任何操作。

圖2 標(biāo)準(zhǔn)布魯姆過濾器的元素插入Fig.2 Element insertion of the standard Bloom Filter

2）元素查詢操作，也有兩個(gè)步驟：

①計(jì)算 x 的 k 個(gè)哈希地址，即 h1（x），h2（x），…，hk（x）；

②檢查布魯姆過濾器表示匯總信息的向量BitSet中這k個(gè)相對應(yīng)的位置是否都為1，它們只要有一個(gè)是0，x必不在集合中，如果全為1，則可以“認(rèn)為”x在集合中。

事實(shí)上若一個(gè)元素對應(yīng)的位置全為1，實(shí)際上是不能100%的肯定該元素被Bloom Filter記錄過的。因?yàn)橛锌赡茉撛氐乃形欢紕偤檬潜黄渌厮鶎?yīng)，這種將元素劃分錯(cuò)的情況，稱為假陽性誤判。如圖3所示，元素x不屬于集合，但屬于集合的元素a，b，c將x的映射地址置位，導(dǎo)致誤判x在集合中[3]。

圖3 布魯姆過濾器假陽性Fig.3 False positive of the Bloom Filter

2 MD5算法

MD5（中文名為消息摘要算法第五版）為計(jì)算機(jī)安全領(lǐng)域廣泛使用的一種散列函數(shù)，用以提供消息的完整性保護(hù)。它是為了解決MD4的碰撞而生的。可以說是MD4的加強(qiáng)版，面向32位機(jī)器。對MD5算法簡要的敘述可以為：MD5以512位分組來處理輸入的信息，且每一分組又被劃分為16個(gè)32位子分組，經(jīng)過了一系列的處理后，算法的輸出由4個(gè)32位分組組成，將這4個(gè)32位分組級聯(lián)后將生成一個(gè)128位散列值。由此可知，任意明文的輸入，經(jīng)過MD5算法后都可以生成128位的消息輸出，并且不同的明文輸入使它們的輸出相同在計(jì)算上是不可行的[4]。

3 在文本檢索系統(tǒng)中新算法的設(shè)計(jì)

在文本檢索系統(tǒng)中的用戶一般具有兩種角色，具有查詢權(quán)限的角色和添加權(quán)限的角色，其中查詢權(quán)限算法的具體流程圖如圖4所示。

圖4 查詢權(quán)限算法流程圖Fig.4 Algorithm flow chart of the query

添加權(quán)限算法的具體流程圖如圖5所示。

4 性能分析

圖5 添加權(quán)限算法流程圖Fig.5 Algorithm flow chart of the add

不論是查詢算法還是添加算法的錯(cuò)誤率都來自于Bloom Filter的假陽性錯(cuò)判fp，因此，在實(shí)際應(yīng)用中必須對fp進(jìn)行評估，設(shè)計(jì)合適的布魯姆過濾器，降低fp的影響[5]。n為集合X的元素個(gè)數(shù)，m為向量BitSet的長度，k為哈希函數(shù)的個(gè)數(shù)。

假設(shè)向量BitSet中任一bit位為0的概率是p，那么任一bit位為1的概率是p-1，假設(shè)哈希函數(shù)值服從均勻分布，則當(dāng)集合中所有的元素都映射完畢后，BitSet中任意一位為0的概率是：

當(dāng)不屬于集合的元素誤判斷屬于集合時(shí)，元素在BitSet向量的對應(yīng)位置都必須為1。即元素的誤判率為

即

由公式可知，當(dāng)集合元素個(gè)數(shù)n和向量空間的長度m一定時(shí)，當(dāng)且僅當(dāng)k=ln 2·m/n時(shí)，布魯姆過濾器fp最小。

使用標(biāo)準(zhǔn)布魯姆過濾器，增加一個(gè)元素到集合，需要進(jìn)行k次哈希運(yùn)算，其一次元素插入操作的時(shí)間復(fù)雜度為O（k）。當(dāng)判斷元素是否在集合中時(shí)，同樣需要進(jìn)行k次哈希計(jì)算，完成一次元素查詢的時(shí)間復(fù)雜度為O（k），因此布魯姆過濾器最大的特征是空間簡潔和查詢方便。

而布魯姆過濾器的狹隘性同樣明顯。多樣性的網(wǎng)絡(luò)應(yīng)用帶來了多樣性的操作集合，布魯姆過濾器作為一種表示集合的數(shù)據(jù)結(jié)構(gòu)，集合是布魯姆過濾器算法實(shí)施的對象和前提。但是，現(xiàn)有的布魯姆過濾器對集合的表示大多限制為數(shù)字或者類似數(shù)字組成的集合，即將非數(shù)值集合的元素轉(zhuǎn)換成一定范圍的數(shù)值數(shù)據(jù)。這種對數(shù)據(jù)集合形式的限制，成為布魯姆過濾器在持續(xù)發(fā)展的網(wǎng)絡(luò)中廣泛應(yīng)用的絆腳石。本文利用MD5的可以把任何明文輸入轉(zhuǎn)換為128位散列值和可靠性高的特性，將Bloom Filter應(yīng)用于文本檢索系統(tǒng)[6]。

5 結(jié)束語

總之，Bloom Filter空間簡潔的特性使其在搜索系統(tǒng)上大有可為，而MD5生成的128位散列值的唯一性，又滿足了Bloom Filter對數(shù)據(jù)集合的要求。合理的設(shè)計(jì)哈希函數(shù)的個(gè)數(shù)可以將假陽性誤判降至最低，因此本文設(shè)計(jì)的算法必然可以充分應(yīng)用于搜索系統(tǒng)，網(wǎng)頁去重，垃圾郵件過濾等方面，為實(shí)現(xiàn)更多互聯(lián)網(wǎng)的應(yīng)用發(fā)展提供幫助和支持。

[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]謝鯤，文吉?jiǎng)?，張大方，等．布魯姆過濾器查詢算法[J]．軟件學(xué)報(bào)，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.