滿　鵬

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

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

〔中圖分類號(hào)〕TP31 〔文獻(xiàn)標(biāo)識(shí)碼〕A 〔文章編號(hào)〕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

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

1 原 理

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

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

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

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

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

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

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

2 技 術(shù)

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

2.1 中文分詞技術(shù)

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

2.2 排序技術(shù)

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

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

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

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

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

3.1 如何分詞

分詞的好壞關(guān)系到查詢的準(zhǔn)確程度和生成索引的大小。在中文分詞發(fā)展中,早期經(jīng)常使用分詞方式是二元分詞法,該方法的基本原理是將包含中文的句子進(jìn)行二元分割,不考慮單詞含義,只對(duì)二元單詞進(jìn)行索引。因此該方法所分出的單詞數(shù)量較多,從而產(chǎn)生的索引數(shù)量巨大,查詢中會(huì)將無(wú)用的數(shù)據(jù)檢索出來(lái),好處是算法簡(jiǎn)單不會(huì)漏掉檢索的數(shù)據(jù)。之后又發(fā)展出最大匹配分詞方法,該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似,對(duì)常用單詞生成一個(gè)詞典,分析句子的過(guò)程中最大的匹配字典中的單詞,從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對(duì)偏正式詞語(yǔ)的分辨容易產(chǎn)生錯(cuò)誤,比如“首飾和服裝”會(huì)將“和服”作為單詞分出。本文實(shí)現(xiàn)的是逆向最大分詞方法,該分詞方法較正向正確率有所提高。最為復(fù)雜的是通過(guò)統(tǒng)計(jì)方式進(jìn)行分詞的方法。該方法采用隱式馬爾科夫鏈,也就是后一個(gè)單詞出現(xiàn)的概率依靠于前一個(gè)單詞出現(xiàn)的概率,最后統(tǒng)計(jì)所有單詞出現(xiàn)的概率的最大為分詞的依據(jù)。這個(gè)方法對(duì)新名詞和地名的識(shí)別要遠(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)閷⒚恳粋€(gè)單詞作為索引項(xiàng),根據(jù)該索引項(xiàng)查找包含該單詞的文本。因此,索引都是單詞和惟一記錄文本的標(biāo)識(shí)是一對(duì)多的關(guān)系。將索引單詞排序,根據(jù)排序后的單詞定位包含該單詞的文本。

3.3 逆向最大分詞算法

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

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

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

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

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

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

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

中國(guó)

中華民國(guó)

國(guó)家

人民

民主

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

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

3.4 索引的格式

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

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

3.5 全文索引的查詢

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

4 結(jié) 論

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

參考文獻(xiàn)

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

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

[3]譚建龍.串匹配算法及其在網(wǎng)絡(luò)內(nèi)容分析中的應(yīng)用[D].中國(guó)科學(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.