全文檢索的原理與實(shí)現(xiàn)探討

滿　鵬

〔摘 要〕本文主要在介紹全文檢索的概念和原理的基礎(chǔ)上,論述了全文檢索的幾種主要技術(shù),并給出了逆向最大分詞法的具體實(shí)現(xiàn)。

〔關(guān)鍵詞〕全文檢索;搜索引擎;中文分詞

〔中圖分類號〕TP31 〔文獻(xiàn)標(biāo)識碼〕A 〔文章編號〕1008-0821(2009)07-0138-03

Discussion on Principle and Implementation of Full Text SearchMan Peng

(Computer Center,Changchun University,Changchun 130022,China)

〔Abstract〕Based on the introduction of concept and theory of full text search,in this paper,it expounded a few primary technologies in full text search,proposed an implementation of reverse direction maximum word-dividing.

〔Key words〕full text search;search engine;chinese division

全文檢索是對大數(shù)據(jù)文本進(jìn)行索引,在建立的索引中對要查找的單詞進(jìn)行搜索,定位哪些文本數(shù)據(jù)包括要搜索的單詞。因此,全文檢索的全部工作就是建立索引和在索引中搜索定位,所有的工作都是圍繞這兩方面展開的。下面本文就對它的原理、技術(shù)和實(shí)現(xiàn),一一加以分析與探討。

1 原 理

全文搜索的典型代表是網(wǎng)絡(luò)蜘蛛程序(網(wǎng)絡(luò)機(jī)器人),可以通過對它的工作過程分析,分析出全文搜索的技術(shù)原理。網(wǎng)絡(luò)蜘蛛程序是一個自動搜索程序,可自動在互聯(lián)網(wǎng)上搜索信息。并且查看頁面的內(nèi)容,然后從中找到相關(guān)的信息,最后再從該頁面的所有鏈接出發(fā),繼續(xù)尋找其它相關(guān)的信息。網(wǎng)絡(luò)蜘蛛不斷的重復(fù)這個過程,并把經(jīng)過的所有網(wǎng)頁收集到搜索引擎所在的服務(wù)器中,這個過程一般采用的是廣度優(yōu)先算法。當(dāng)網(wǎng)絡(luò)蜘蛛收集到信息后,接下來要進(jìn)行以下幾個方面的工作:

1.1 建立索引數(shù)據(jù)庫

當(dāng)網(wǎng)絡(luò)蜘蛛存儲網(wǎng)頁后,再由自定義程序?qū)Ψ?wù)器中保存的網(wǎng)頁進(jìn)行分析,提取相關(guān)網(wǎng)頁的URL、編碼類型、關(guān)鍵詞位置、生成時間、大小和與其他網(wǎng)頁的鏈接關(guān)系等。根據(jù)網(wǎng)站自定義的相關(guān)度算法進(jìn)行運(yùn)算,最后得到相關(guān)度信息,然后用這些相關(guān)信息建立網(wǎng)頁索引數(shù)據(jù)庫。

1.2 在索引數(shù)據(jù)庫中搜索

當(dāng)用戶輸入搜索內(nèi)容,單擊搜索按鈕后,系統(tǒng)自定義程序開始根據(jù)相關(guān)技術(shù),分析用戶的搜索內(nèi)容,然后從網(wǎng)頁索引數(shù)據(jù)庫中,找到包含用戶搜索內(nèi)容的所有相關(guān)網(wǎng)頁。

1.3 對搜索結(jié)果進(jìn)行排序

在網(wǎng)站自己的索引庫中,對網(wǎng)頁的每個關(guān)鍵詞都有記載,根據(jù)關(guān)鍵詞的搜索次數(shù)以及在網(wǎng)頁中出現(xiàn)的次數(shù)等分析要素,對搜索到的結(jié)果進(jìn)行排序,也可以自己定義排序處理程序。最后將處理好的結(jié)果展現(xiàn)出來。

2 技 術(shù)

下面對于全文搜索中的主要幾種技術(shù),加以分析探討,以便為全文搜索的技術(shù)實(shí)現(xiàn)提供某種思路。

2.1 中文分詞技術(shù)

英文是以詞為單位的,詞與詞之間上靠空格隔開,而中文是以字為單位,句子中所有的字連起來才能描述一個意思。例如,英文句子I am Chinese,翻譯成“我是中國人”。計(jì)算機(jī)可以很簡單的通過空格知道Chinese是一個單詞,但是不能很明白“中”、“國”兩個字合起來才表示一個詞。把中文的漢字序列切分成有意義的詞,就是中文分詞?，F(xiàn)有的分詞算法有3種:基于字符串匹配的分詞算法、基于理解的分詞算法和基于統(tǒng)計(jì)的分詞算法。本文不對此一一分析,請讀者自行查閱相關(guān)文獻(xiàn)。

2.2 排序技術(shù)

排序技術(shù)類似于曝光率,誰出現(xiàn)的次數(shù)最多,誰排在前面。在互聯(lián)網(wǎng)上,鏈接就相當(dāng)于“曝光”,在B網(wǎng)頁中鏈接了A,相當(dāng)于在談話中提到了A,如果在C、D、E、F中都鏈接了A,那么說明A網(wǎng)頁是最重要的,A便會排在最前面。另外還有HillTop算法等。

2.3 網(wǎng)絡(luò)蜘蛛

網(wǎng)絡(luò)蜘蛛即Web Spider,是一種很形象的網(wǎng)頁搜索技術(shù)。把互聯(lián)網(wǎng)比喻成一個蜘蛛網(wǎng),那么Spider就是網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡(luò)蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁,從網(wǎng)站某一個頁面(通常是首頁)開始,讀取網(wǎng)頁的內(nèi)容,找到在網(wǎng)頁中的其他鏈接地址,然后通過這些鏈接地址尋找下一個網(wǎng)頁,這樣一直循環(huán)下去,直到把這個網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個互聯(lián)網(wǎng)當(dāng)成一個網(wǎng)站,那么網(wǎng)絡(luò)蜘蛛就可以用這個原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。在抓取網(wǎng)頁的時候,網(wǎng)絡(luò)蜘蛛一般有兩種算法:廣度優(yōu)先和深度優(yōu)先。廣度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會先抓取起始網(wǎng)頁中鏈接的所有的網(wǎng)頁,然后再選擇其中的一個鏈接網(wǎng)頁,繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng)頁。這是最常用的方式,因?yàn)檫@個方法可以讓網(wǎng)絡(luò)蜘蛛并行處理,提高其抓取速度。深度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會從起始頁開始,一個鏈接一個鏈接跟蹤下去,處理完這條線路之后再轉(zhuǎn)入下一個起始頁,繼續(xù)跟蹤鏈接。這個方法的優(yōu)點(diǎn)是比較容易設(shè)計(jì)。

3 實(shí) 現(xiàn)

建立全文索引中有兩項(xiàng)非常重要:一個是如何對文本進(jìn)行分詞;一個是建立索引的數(shù)據(jù)結(jié)構(gòu)。

3.1 如何分詞

分詞的好壞關(guān)系到查詢的準(zhǔn)確程度和生成索引的大小。在中文分詞發(fā)展中,早期經(jīng)常使用分詞方式是二元分詞法,該方法的基本原理是將包含中文的句子進(jìn)行二元分割,不考慮單詞含義,只對二元單詞進(jìn)行索引。因此該方法所分出的單詞數(shù)量較多,從而產(chǎn)生的索引數(shù)量巨大,查詢中會將無用的數(shù)據(jù)檢索出來,好處是算法簡單不會漏掉檢索的數(shù)據(jù)。之后又發(fā)展出最大匹配分詞方法,該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似,對常用單詞生成一個詞典,分析句子的過程中最大的匹配字典中的單詞,從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對偏正式詞語的分辨容易產(chǎn)生錯誤,比如“首飾和服裝”會將“和服”作為單詞分出。本文實(shí)現(xiàn)的是逆向最大分詞方法,該分詞方法較正向正確率有所提高。最為復(fù)雜的是通過統(tǒng)計(jì)方式進(jìn)行分詞的方法。該方法采用隱式馬爾科夫鏈,也就是后一個單詞出現(xiàn)的概率依靠于前一個單詞出現(xiàn)的概率,最后統(tǒng)計(jì)所有單詞出現(xiàn)的概率的最大為分詞的依據(jù)。這個方法對新名詞和地名的識別要遠(yuǎn)遠(yuǎn)高于最大匹配法,準(zhǔn)確度隨著取樣文本的數(shù)量的增大而提高。二元分詞方法和統(tǒng)計(jì)方法是不依賴于詞典的,而最大匹配法分詞方法是依賴于詞典的,詞典的內(nèi)容決定分詞結(jié)構(gòu)的好壞。

3.2 索引的結(jié)構(gòu)

索引的數(shù)據(jù)結(jié)構(gòu)基本上采用倒排索引的結(jié)構(gòu)。全文檢索的索引被稱為倒排索引,之所以稱為倒排索引,是因?yàn)閷⒚恳粋€單詞作為索引項(xiàng),根據(jù)該索引項(xiàng)查找包含該單詞的文本。因此,索引都是單詞和惟一記錄文本的標(biāo)識是一對多的關(guān)系。將索引單詞排序,根據(jù)排序后的單詞定位包含該單詞的文本。

3.3 逆向最大分詞算法

逆向最大分詞的實(shí)現(xiàn)算法說明:

(1)讀取一整條句子到變量str中,轉(zhuǎn)到(2);

(2)從句子的尾端讀取1個字到變量word中,轉(zhuǎn)到(3);

(3)在字典查找word中保存的單詞。如果存在則保存word,轉(zhuǎn)到(4),否則轉(zhuǎn)到(5);

(4)如果是字典中最大單詞或者超過最大單詞數(shù)(認(rèn)定為新詞),從句尾去掉該單詞,返回(2);

(5)讀取前一個字到word中,構(gòu)成新單詞,轉(zhuǎn)到(3)。

假設(shè)字典中有如下的單詞:

中國

中華民國

國家

人民

民主

在內(nèi)存中按照如下方式按層排列:其中每一個方塊代表一個字,箭頭所指向?yàn)樵搯卧~的前一個字。

那么,如查找單詞“中華民國”:(1)首先在第一層中使用二分法找到“國”字,獲得“國”下層的數(shù)組“中民”;(2)在該層使用二分法查找“民”,獲得“民”下層的數(shù)組“華”;(3)在該層使用二分法查找“華”,獲得“華”下層的數(shù)組“中”;(4)最后在該層找到“中”,至此匹配完畢。

3.4 索引的格式

索引的格式是倒排索引的格式,也就是一個單詞對應(yīng)若干個文本表示。比如,建立全文索引的對象是rec中的字段,生成倒排索引使用數(shù)據(jù)庫中的b樹進(jìn)行存儲。在數(shù)據(jù)庫是對某個字符字段進(jìn)行全文索引,因此,rec的rowid作為該rec上該field的標(biāo)示是必須要被記錄的。因此倒排索引存儲的格式如下:

字段1字段2單詞1Rowid1,rowid2…單詞1 Rowid1,rowid2………字段1字段2字段3單詞1單詞1Rowid的格數(shù)Rowid1,rowid2…單詞1單詞2Rowid的格數(shù)Rowid1,rowid2…………

3.5 全文索引的查詢

全文的索引查詢首先將對要查詢的單詞進(jìn)行分詞,然后在存儲倒排索引的b樹中將包含這些單詞的rowid全部查找出來,并根據(jù)這些rowid在存儲實(shí)際數(shù)據(jù)的b樹中,將包含這些數(shù)據(jù)的行過濾出來。

4 結(jié) 論

本文簡單地介紹了全文檢索技術(shù)的基本概念、原理和相關(guān)技術(shù),并給出了逆向最大分詞技術(shù)的具體實(shí)現(xiàn)。隨著搜索引擎市場空間越來越大,搜索引擎也分得越來越細(xì),搜索需求不可能都一樣,搜索引擎會不斷細(xì)化,各具特色的搜索引擎也陸續(xù)出現(xiàn)。本文中的所實(shí)現(xiàn)的技術(shù),在這些不同的應(yīng)用領(lǐng)域中,都將會有一定的使用價值。

參考文獻(xiàn)

[1]李盛韜.基于主題的Web信息采集技術(shù)研究[D].中國科學(xué)院計(jì)算技術(shù)研究所碩士畢業(yè)論文,2002.

[2]許洪波.大規(guī)模信息過濾技術(shù)研究及其在Web問答系統(tǒng)中的應(yīng)用[D].中國科學(xué)院計(jì)算技術(shù)研究所博士畢業(yè)論文,2003.

[3]譚建龍.串匹配算法及其在網(wǎng)絡(luò)內(nèi)容分析中的應(yīng)用[D].中國科學(xué)院計(jì)算技術(shù)研究所博士畢業(yè)論文,2003.

[4]Winter.中文搜索引擎技術(shù)揭密:系統(tǒng)架構(gòu)[EB].中文全文檢索網(wǎng),2004.

[5]Lawrence S,Giles C L.Searching the world wide web[J].Science,1998,280(4).

[6]http:∥www.bhasha.com[EB].2007.5.

[7]Hendler J.Agents and the Semantic Web.IEEE Intelligent Systems,2001-03-04.

[8]T Berners Lee.J Handler.O Lassila,The Semantic Web.Scientific America,May 2001:219.

[9]Cardie C.Empirical methods in information extraction.AI Magazine,1997,18(4).

[10]HSUC N,DUNG M.Generating finite-state transducers for semi-structured data extraction from the Web[J].Information System,1998,23(8):521-538.