張 華,顧紅飛,劉 濤

（阜陽(yáng)職業(yè)技術(shù)學(xué)院工程科技學(xué)院,安徽阜陽(yáng) 236031）

基于B+樹(shù)的文本信息檢索技術(shù)

張 華,顧紅飛,劉 濤

（阜陽(yáng)職業(yè)技術(shù)學(xué)院工程科技學(xué)院,安徽阜陽(yáng) 236031）

隨著人類(lèi)步入信息時(shí)代,網(wǎng)上龐大的數(shù)字化信息與人們獲取所需信息能力之間的矛盾日益突出,怎樣快速地檢索相關(guān)信息已經(jīng)成為研究熱點(diǎn)。闡述了全文檢索系統(tǒng)的原理,分析了基于字表結(jié)構(gòu)的索引組織方法和索引庫(kù)的建立。通過(guò)和B-樹(shù)的對(duì)比,提出了基于B+樹(shù)的索引存儲(chǔ)方法及其算法思想,對(duì)提高索引的存儲(chǔ)效率和查找速度具有一定意義。

B+樹(shù);全文索引;B-樹(shù);倒排索引

隨著互聯(lián)網(wǎng)的發(fā)展,如何充分利用網(wǎng)上的信息資源正在成為信息科學(xué)研究者所關(guān)注的熱點(diǎn)。信息檢索技術(shù)是根據(jù)互聯(lián)網(wǎng)信息的特點(diǎn)而發(fā)展起來(lái)的一種檢索方式。信息檢索技術(shù)主要研究信息的表示、存儲(chǔ)、組織和訪問(wèn),即根據(jù)用戶(hù)的查詢(xún)要求,從信息數(shù)據(jù)庫(kù)中檢索出相關(guān)信息資料,其核心為文本信息的索引和檢索,即全文檢索技術(shù)。

1 全文檢索系統(tǒng)

全文檢索是指計(jì)算機(jī)索引程序通過(guò)掃描文章中的每一個(gè)詞,對(duì)全文建立一個(gè)能精確定位每個(gè)字詞的索引,當(dāng)用戶(hù)查詢(xún)時(shí),檢索程序根據(jù)事先建立好的索引進(jìn)行查找,并將查找的結(jié)果反饋給用戶(hù)的檢索方式。全文檢索的核心技術(shù)是將源文檔中所有的基本元素的出現(xiàn)信息記錄到索引庫(kù)中,在中文系統(tǒng)中,基本元素可以是單個(gè)漢字字符,也可以是詞。因此存在兩種基本的索引庫(kù)結(jié)構(gòu),即基于字表的索引庫(kù)和基于詞表的索引庫(kù)。字表法和詞表法各有優(yōu)缺點(diǎn),文章主要討論基于字表的檢索方式。

全文檢索系統(tǒng)是指按照全文檢索技術(shù)理論建立起來(lái)的用于提供全文檢索服務(wù)的軟件系統(tǒng)。一般來(lái)說(shuō),全文檢索系統(tǒng)需要具備建立索引和提供查詢(xún)這兩項(xiàng)基本功能。功能上,全文檢索系統(tǒng)核心具有建立索引、增加索引、優(yōu)化索引、處理查詢(xún)返回結(jié)果集等功能。結(jié)構(gòu)上,全文檢索系統(tǒng)核心具有索引引擎、查詢(xún)引擎、文本分析引擎、對(duì)外接口,加上各種外圍應(yīng)用系統(tǒng)等共同構(gòu)成了全文檢索系統(tǒng)。

圖1 全文檢索系統(tǒng)結(jié)構(gòu)圖

圖1展示了全文檢索系統(tǒng)的結(jié)構(gòu)與功能。全文檢索系統(tǒng)中最核心、最關(guān)鍵的部分是全文檢索引擎部分,從功能模塊上可以劃分為文本分析模塊、創(chuàng)建索引模塊、查詢(xún)索引模塊。索引的準(zhǔn)備工作和搜索的應(yīng)用都是建立在這個(gè)引擎之上,因此提升全文檢索引擎的效率即是我們提升全文檢索應(yīng)用效率的關(guān)鍵。

2 索引的數(shù)據(jù)結(jié)構(gòu)

2.1 索引組織

中文索引策略中索引的組織方法有兩種,即正向索引和倒排索引[1]（P24-26）。在信息檢索系統(tǒng)中,會(huì)為每個(gè)文檔分配一個(gè)唯一的ID號(hào)作為其標(biāo)志,在索引數(shù)據(jù)庫(kù)中以這個(gè)文檔ID號(hào)表示該文檔。索引建立的方法有正向索引和倒排索引（如圖2所示）,正向索引是以文檔的ID為關(guān)鍵字,表中記錄文檔中每個(gè)詞出現(xiàn)的位置信息,進(jìn)行檢索時(shí)掃描表中每個(gè)文檔中詞的信息直到找出所有包含查詢(xún)關(guān)鍵字的文檔。這種方法的索引結(jié)構(gòu)比較簡(jiǎn)單、維護(hù)方便,但是在查詢(xún)的時(shí)候?qū)?huì)對(duì)所有的文檔進(jìn)行順序掃描,因此使得檢索時(shí)間大大延長(zhǎng),檢索效率較低。所以這里采用倒排表（如圖2所示）作為文檔數(shù)據(jù)索引方式,倒排索引以索引單元作為關(guān)鍵字,每個(gè)關(guān)鍵字對(duì)應(yīng)著該索引單元在所有文檔中出現(xiàn)的位置信息、頻率等。進(jìn)行檢索時(shí)可以一次得到該關(guān)鍵字對(duì)應(yīng)的所有文檔,因此檢索時(shí)間短,檢索效率較高。由于每個(gè)詞對(duì)應(yīng)的文檔數(shù)量在動(dòng)態(tài)變化,所以倒排表的建立和維護(hù)較為復(fù)雜,但是在檢索的時(shí)候由于可以一次得到查詢(xún)關(guān)鍵詞對(duì)應(yīng)的所有文檔,所以效率遠(yuǎn)遠(yuǎn)高于正排表。

圖2 正向索引和倒排索引

圖3 字表圖

圖4 字表及字表段結(jié)構(gòu)

2.2 建立索引庫(kù)

建立一個(gè)全文檢索系統(tǒng),首先將源文檔轉(zhuǎn)換為能夠進(jìn)行文本查找的全文索引庫(kù),包括全文的分割處理以及規(guī)范格式等,這稱(chēng)為前處理工作,前處理完成后,即可開(kāi)始建立索引,先過(guò)濾掉源文檔中的排版符號(hào)、格式控制符等,再把源文檔中每一個(gè)字的出現(xiàn)位置信息記錄到索引庫(kù)中。

前期處理工作主要將文檔的內(nèi)容全部提取出來(lái),去除無(wú)用的信息,再轉(zhuǎn)換成統(tǒng)一的格式類(lèi)型。在文章檢索系統(tǒng)的處理中,靜態(tài)文件要去除文件內(nèi)容中的大量標(biāo)記,如htm l標(biāo)記,動(dòng)態(tài)文檔則可直接抽取出數(shù)據(jù)庫(kù)中的相應(yīng)字段內(nèi)容。處理完成后將所有內(nèi)容轉(zhuǎn)換成字符串類(lèi)型的對(duì)象,最后根據(jù)一個(gè)詞典,用一個(gè)“切詞軟件”,從處理完的字符串中切出所含的詞,去掉諸如“的”,“在”等沒(méi)有內(nèi)容指示意義的詞,這樣文檔就主要由一組詞來(lái)近似代表了,如p={t1,t2,…tn…}。

索引庫(kù)對(duì)每個(gè)不同的字符都保存一個(gè)字表,字表法索引庫(kù)的主要部分是每個(gè)字的字表信息,字表結(jié)構(gòu)如圖3所示,其中字符i對(duì)應(yīng)的字表值記錄了該字符在源文檔中所出現(xiàn)的位置 Pix。在這里,位置采用字符相對(duì)于文檔頭的偏移字符數(shù)表示,而不按通常情況采用相對(duì)于文檔頭的偏移字節(jié)數(shù),這樣可減小位置的數(shù)值大小,有利于進(jìn)一步采用壓縮技術(shù)。建立字表時(shí),需要掃描整個(gè)源文檔,對(duì)出現(xiàn)的每一個(gè)有效字符,計(jì)算其在文檔中出現(xiàn)的位置,并將該位置的值加入到對(duì)應(yīng)的字表中。字表是索引庫(kù)中最主要的部分,在每個(gè)漢字字符對(duì)應(yīng)的字表中包含該字符出現(xiàn)在所有文檔中的全部位置。為了區(qū)分每個(gè)位置值屬于哪個(gè)文檔,每個(gè)字符的字表被分為多個(gè)字表段（圖4）,每段對(duì)應(yīng)一個(gè)文檔,記錄該字符在此文檔中出現(xiàn)的位置。

2.3 索引的存儲(chǔ)結(jié)構(gòu)及查找方式

全文索引[2]（P9-10）把正文看作一個(gè)長(zhǎng)的字符串,可以對(duì)每一個(gè)字符建立索引,從而使查詢(xún)不再限于關(guān)鍵詞,但也需要更大的空間,因此索引庫(kù)[3]（P7-10）所需的空間很大。因此選擇合理的存儲(chǔ)結(jié)構(gòu),使其能夠快速地得到關(guān)鍵字對(duì)應(yīng)的文檔id集,倒排存儲(chǔ)結(jié)構(gòu)有指針鏈表、Hash表、B樹(shù)、二級(jí)索引等多種方法,這里我們采用B+[4]樹(shù)存儲(chǔ)結(jié)構(gòu)。

2.3.1 B-樹(shù)[5]的結(jié)構(gòu)與特點(diǎn)

B-樹(shù)的結(jié)構(gòu)如下:

1、每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn);2、除根結(jié)點(diǎn)和葉結(jié)點(diǎn)外,其他每個(gè)結(jié)點(diǎn)至少有個(gè)子結(jié)點(diǎn);3、根節(jié)點(diǎn)至少有兩個(gè)子結(jié)點(diǎn),唯一例外的是根結(jié)點(diǎn)是葉結(jié)點(diǎn)時(shí)沒(méi)有子結(jié)點(diǎn),此時(shí)B-樹(shù)只包含一個(gè)結(jié)點(diǎn);4、有λ+1個(gè)子結(jié)點(diǎn)的非根結(jié)點(diǎn)必有λ個(gè)關(guān)鍵碼,它包含如下信息:（P0,K1,P1,K2,P2,K3,…,Pλ-1,Kλ,Pλ）;5、所有葉結(jié)點(diǎn)在同一層。

B樹(shù)上進(jìn)行查找包含兩種基本操作:（1）在B樹(shù)中找結(jié)點(diǎn);（2）在結(jié)點(diǎn)中找關(guān)鍵字。由于B樹(shù)通常存儲(chǔ)在磁盤(pán)上,則前一查找操作是在磁盤(pán)上進(jìn)行的,而后一查找操作是在內(nèi)存中進(jìn)行的,即在磁盤(pán)上找到指針P所指結(jié)點(diǎn)后,先將結(jié)點(diǎn)中的信息讀入內(nèi)存,然后再利用順序查找或折半查找查詢(xún)等于K的關(guān)鍵字。顯然,在磁盤(pán)上進(jìn)行一次查找比在內(nèi)存中進(jìn)行一次查找耗費(fèi)時(shí)間多得多,因此,在磁盤(pán)上進(jìn)行查找的次數(shù)即待查找的次數(shù),也就等于待查關(guān)鍵字所在結(jié)點(diǎn)在B樹(shù)上的層次數(shù),是決定B樹(shù)查找效率的首要因素。

假設(shè)m階B-樹(shù)包含N個(gè)關(guān)鍵字,由分析可知第k層至少有2×k-1個(gè)結(jié)點(diǎn),

對(duì)B-樹(shù)進(jìn)行插入,會(huì)產(chǎn)生分裂。設(shè)L是內(nèi)部結(jié)點(diǎn)的個(gè)數(shù),除根外的所有內(nèi)部結(jié)點(diǎn)都包括-1個(gè)關(guān)鍵字時(shí),B-樹(shù)所包括的總關(guān)鍵字個(gè)數(shù)最少,故

2.3.2 B+樹(shù)的性能

2.3.2.1 B+樹(shù)的結(jié)構(gòu)

B+樹(shù)是B樹(shù)的變型,M階B+樹(shù)的結(jié)構(gòu)定義如下:1、每個(gè)節(jié)點(diǎn)至多有m個(gè)子女;2、每個(gè)節(jié)點(diǎn)（除根外）至少有個(gè)子女;3、根節(jié)點(diǎn)至少有兩個(gè)子女; 4、有λ個(gè)子女的節(jié)點(diǎn)必有λ個(gè)關(guān)鍵碼,它包含如下信息:（P0,K1,P1,K2,P2,K3,…,Pλ-1,Kλ）。

在基本B樹(shù)中,關(guān)鍵字分布在整個(gè)B樹(shù)中,并且在內(nèi)部結(jié)點(diǎn)中出現(xiàn)的關(guān)鍵字不再出現(xiàn)在葉結(jié)點(diǎn)中,這樣順序鏈就不能將樹(shù)中所有關(guān)鍵字接在一起。B+樹(shù)在這一點(diǎn)上做了改動(dòng),即把樹(shù)中所有關(guān)鍵字都按遞增次序從左到右插在葉結(jié)點(diǎn)上,并用指針鏈接起來(lái),在B+樹(shù)中數(shù)據(jù)指針只存儲(chǔ)在樹(shù)的葉結(jié)點(diǎn)中,因此,葉結(jié)點(diǎn)的結(jié)構(gòu)與內(nèi)部結(jié)點(diǎn)的結(jié)構(gòu)是不同的。如果搜索字段是關(guān)鍵字,葉結(jié)點(diǎn)對(duì)每個(gè)搜索字段的值有一個(gè)入口和一個(gè)指向記錄的指針,對(duì)于非關(guān)鍵搜索字段,指針指向附加級(jí)中的一個(gè)塊,這個(gè)塊中存放指向數(shù)據(jù)文件的記錄指針。B+樹(shù)的所有關(guān)鍵碼都出現(xiàn)在葉子節(jié)點(diǎn)上,上面各層節(jié)點(diǎn)中的關(guān)鍵碼是下一層相應(yīng)節(jié)點(diǎn)中最大關(guān)鍵碼的復(fù)寫(xiě)。B+樹(shù)的構(gòu)造是由下而上的,m限定了節(jié)點(diǎn)的大小,自下而上地把每個(gè)節(jié)點(diǎn)的最大關(guān)鍵碼復(fù)寫(xiě)到上一層節(jié)點(diǎn)中。（如圖5）

2.3.2.2B+樹(shù)的檢索效率

假設(shè)m階B+樹(shù)中包含N個(gè)關(guān)鍵字,由B+樹(shù)結(jié)構(gòu)可知每層上最少關(guān)鍵字個(gè)數(shù)和結(jié)點(diǎn)數(shù)如下:

第0層結(jié)點(diǎn)數(shù)1個(gè),關(guān)鍵字?jǐn)?shù)1個(gè);

2.3.2.3B+樹(shù)的結(jié)點(diǎn)分裂次數(shù)

圖5 B+樹(shù)

2.3.3B+樹(shù)和B-樹(shù)的性能比較

由公式（1）知含N個(gè)關(guān)鍵字的B-樹(shù)的檢索層次KB-≤1+log（N+1）/2,大于1。由公式（5）知含N個(gè)關(guān)鍵字的B+樹(shù)的檢索層次kB+≤logN/2,小于1,kB+小于KB-,因此相同關(guān)鍵字?jǐn)?shù)中B+數(shù)的檢索層次小,檢索效率更高。由圖5可知B+樹(shù)上有兩個(gè)指針,一個(gè)指向根結(jié)點(diǎn),另一個(gè)指向關(guān)鍵字最小的葉子結(jié)點(diǎn)。B +樹(shù)的關(guān)鍵字存儲(chǔ)在葉子結(jié)點(diǎn),同組關(guān)鍵字是順序排列,進(jìn)行順序查找比B-樹(shù)容易實(shí)現(xiàn),優(yōu)點(diǎn)是加快了順序訪問(wèn)的速度,刪除過(guò)程簡(jiǎn)化,被刪除的關(guān)鍵字只需要從葉子結(jié)點(diǎn)移出,相關(guān)指針進(jìn)行移動(dòng),其他內(nèi)部結(jié)點(diǎn)保持不變。B+樹(shù)的第二種查找方式是從根結(jié)點(diǎn)開(kāi)始進(jìn)行隨機(jī)查找,由于B+樹(shù)的檢索層次比B-樹(shù)小,對(duì)磁盤(pán)的存取次數(shù)少,速度更快。

由公式（3）知道B-樹(shù)每插入一個(gè)關(guān)鍵碼的平均分裂次數(shù)為小于等于1/（-1）,隨著m的增大,分裂次數(shù)逐漸減少。由公式（8）知道B+樹(shù)的最大分裂次數(shù)為p=1-1/（-1）比B-樹(shù)的略大,但是隨著m的增長(zhǎng)分裂次數(shù)p的值總小于1,因此B+樹(shù)需要進(jìn)行“分裂”處理的概率不大,因?yàn)锽+樹(shù)具有良好的查找速度,插入操作比較簡(jiǎn)單等優(yōu)勢(shì),因此采用B+樹(shù)存儲(chǔ)結(jié)構(gòu)。

2.4 B+樹(shù)的算法

2.4.1 結(jié)點(diǎn)結(jié)構(gòu)

對(duì)于m階B+樹(shù),設(shè)計(jì)的結(jié)點(diǎn)結(jié)構(gòu)對(duì)應(yīng)數(shù)據(jù)模型如下:

所有內(nèi)部結(jié)點(diǎn)僅含有其子樹(shù)中的最大關(guān)鍵字,則所有小于等于某一給定關(guān)鍵字值的關(guān)鍵字值將被存儲(chǔ)在該給定關(guān)鍵字的子樹(shù)中。B+樹(shù)的葉子結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù),具體關(guān)鍵字及每個(gè)關(guān)鍵字的地址,關(guān)鍵字值按從小到大順序排列。此算法的優(yōu)勢(shì)在于,設(shè)置每個(gè)結(jié)點(diǎn)的雙親指針、左孩子和右孩子指針,雙親指針使隨機(jī)查找容易實(shí)現(xiàn),左孩子和右孩子指針使順序查找得以實(shí)現(xiàn),提高B+樹(shù)整體的檢索效率。

2.4.2 B+樹(shù)的檢索

B+樹(shù)的檢索有兩種途徑,一種從根開(kāi)始進(jìn)行隨機(jī)查找,第二種是從最小關(guān)鍵字的left指針開(kāi)始進(jìn)行線性查找。這里我們采用第一種方式,檢索分兩個(gè)步驟:一、查找目標(biāo)結(jié)點(diǎn);二、在目標(biāo)結(jié)點(diǎn)中查找關(guān)鍵字。B+樹(shù)查找若在上層已找到待查關(guān)鍵碼并不停止,而是繼續(xù)沿著相應(yīng)子樹(shù)查到葉結(jié)點(diǎn)層為止。如果在葉結(jié)點(diǎn)的q找到k,則說(shuō)明找到關(guān)鍵字,否則,沒(méi)有找到。為此我們定義了如下數(shù)據(jù)結(jié)構(gòu):

表示查找結(jié)果的類(lèi)型Result:

2.4.3B+樹(shù)的插入

B+樹(shù)的生成是從空樹(shù)開(kāi)始逐個(gè)插入關(guān)鍵字,由下而上生成。由B+樹(shù)定義知道關(guān)鍵字必然插在葉結(jié)點(diǎn),因此插入分兩個(gè)步驟:一、從根向下查找,找到目標(biāo)結(jié)點(diǎn)q;二、在目標(biāo)結(jié)點(diǎn)中插入關(guān)鍵字k。在樹(shù)T中結(jié)點(diǎn)q中i位置中插入關(guān)鍵字k會(huì)產(chǎn)生如下幾種情況:

（1）當(dāng)樹(shù)為空時(shí)生成根結(jié)點(diǎn)

（2）當(dāng)q-＞keynum＜m,則直接插入關(guān)鍵字k,如果k是q中的最大關(guān)鍵字,則調(diào)整父結(jié)點(diǎn)中的相應(yīng)關(guān)鍵字,繼續(xù)查看k是否為父結(jié)點(diǎn)中的最大關(guān)鍵字,如果是繼續(xù)向上調(diào)整父結(jié)點(diǎn)中的關(guān)鍵字,如此循環(huán)直至不需調(diào)整為止。

（3）當(dāng)q-＞keynum==m,首先插入關(guān)鍵字k,再分裂為q和q1兩個(gè)結(jié)點(diǎn),再將兩個(gè)結(jié)點(diǎn)中的最大關(guān)鍵字及q和q1插入父結(jié)點(diǎn)中的相應(yīng)位置。如果父結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于等于m則重復(fù)分裂,向上生長(zhǎng),直至滿(mǎn)足條件為止。

3 結(jié)束語(yǔ)

全文檢索系統(tǒng)對(duì)人們從互聯(lián)網(wǎng)中快速獲得有用信息具有積極的意義。隨著互聯(lián)網(wǎng)信息的高速增長(zhǎng),搜索效率降低,耗費(fèi)時(shí)間長(zhǎng)的問(wèn)題越來(lái)越嚴(yán)重。文中闡述了全文檢索系統(tǒng)的原理,分析了基于字表結(jié)構(gòu)的索引組織方法和索引庫(kù)的建立。通過(guò)和B-樹(shù)的對(duì)比,提出B+樹(shù)的索引存儲(chǔ)方法及其算法思想,對(duì)提高索引的存儲(chǔ)效率和查找速度具有一定意義。

[1]韓中元.中文索引策略的研究[D].哈爾濱:哈爾濱工程大學(xué)（碩士學(xué)位論文）,2007.

[2]于波.中文全文檢索技術(shù)研究[D].武漢:華中師范大學(xué)（碩士學(xué)位論文）,2004.

[3]陳洪猛.全文檢索技術(shù)的研究與實(shí)現(xiàn)[D].北京:北京工業(yè)大學(xué)（碩士學(xué)位論文）,2008.

[4]古輝,葉會(huì)華,賴(lài)松風(fēng).一種基于B+樹(shù)的程序信息庫(kù)設(shè)計(jì)[J].浙江工業(yè)大學(xué)學(xué)報(bào),2008,36（1）:67-71.

[5]關(guān)新民.動(dòng)態(tài)B-樹(shù)分析與應(yīng)用[J].吉林化工學(xué)院學(xué)報(bào), 1999,16（4）:52-56.

Information Retrieval Technique of Text Database Based on B+Tree

ZHANG Hua,GU Hong-fei,LIU Tao

（Institute of Engineering and Technology,FuYang College of Vcational and Technology,Fuyang236031,China）

With human into the information age,the contradiction between large amount of digital information and the information people really need becomes more and more incisive,and how quickly retrieve relevant information has become a hotspot.This article describes the principle of full text retrieval system,analysis of word-based index of the table structure methods and the establishment of the index database.By the comparison between B-tree and B+tree,we find that B+tree structure can be used as storage index tree to boost the speed of store and search greatly.

B+Tree;Full-text-Index;B-Tree;inverted index

TP391.3

A

1009-9735（2010）02-0031-05

2009-11-18

安徽省優(yōu)秀青年人才基金資助項(xiàng)目（2009SQRZ216）。

張華（1975-）,女,安徽六安人,碩士,講師,研究方向:基于數(shù)據(jù)壓縮的文本信息檢索。