基于B+樹的文本信息檢索技術

張 華,顧紅飛,劉 濤

（阜陽職業(yè)技術學院工程科技學院,安徽阜陽 236031）

基于B+樹的文本信息檢索技術

張 華,顧紅飛,劉 濤

（阜陽職業(yè)技術學院工程科技學院,安徽阜陽 236031）

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

B+樹;全文索引;B-樹;倒排索引

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

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

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

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

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

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

2 索引的數(shù)據(jù)結構

2.1 索引組織

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

圖2 正向索引和倒排索引

圖3 字表圖

圖4 字表及字表段結構

2.2 建立索引庫

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

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

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

2.3 索引的存儲結構及查找方式

全文索引[2]（P9-10）把正文看作一個長的字符串,可以對每一個字符建立索引,從而使查詢不再限于關鍵詞,但也需要更大的空間,因此索引庫[3]（P7-10）所需的空間很大。因此選擇合理的存儲結構,使其能夠快速地得到關鍵字對應的文檔id集,倒排存儲結構有指針鏈表、Hash表、B樹、二級索引等多種方法,這里我們采用B+[4]樹存儲結構。

2.3.1 B-樹[5]的結構與特點

B-樹的結構如下:

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

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

假設m階B-樹包含N個關鍵字,由分析可知第k層至少有2×k-1個結點,

對B-樹進行插入,會產生分裂。設L是內部結點的個數(shù),除根外的所有內部結點都包括-1個關鍵字時,B-樹所包括的總關鍵字個數(shù)最少,故

2.3.2 B+樹的性能

2.3.2.1 B+樹的結構

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

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

2.3.2.2B+樹的檢索效率

假設m階B+樹中包含N個關鍵字,由B+樹結構可知每層上最少關鍵字個數(shù)和結點數(shù)如下:

第0層結點數(shù)1個,關鍵字數(shù)1個;

2.3.2.3B+樹的結點分裂次數(shù)

圖5 B+樹

2.3.3B+樹和B-樹的性能比較

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

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

2.4 B+樹的算法

2.4.1 結點結構

對于m階B+樹,設計的結點結構對應數(shù)據(jù)模型如下:

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

2.4.2 B+樹的檢索

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

表示查找結果的類型Result:

2.4.3B+樹的插入

B+樹的生成是從空樹開始逐個插入關鍵字,由下而上生成。由B+樹定義知道關鍵字必然插在葉結點,因此插入分兩個步驟:一、從根向下查找,找到目標結點q;二、在目標結點中插入關鍵字k。在樹T中結點q中i位置中插入關鍵字k會產生如下幾種情況:

（1）當樹為空時生成根結點

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

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

3 結束語

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

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

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

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

[4]古輝,葉會華,賴松風.一種基于B+樹的程序信息庫設計[J].浙江工業(yè)大學學報,2008,36（1）:67-71.

[5]關新民.動態(tài)B-樹分析與應用[J].吉林化工學院學報, 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)秀青年人才基金資助項目（2009SQRZ216）。

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