〔摘 要〕本文主要在介紹全文檢索的概念和原理的基礎(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ī)器人)，可以通過對(duì)它的工作過程分析，分析出全文搜索的技術(shù)原理。網(wǎng)絡(luò)蜘蛛程序是一個(gè)自動(dòng)搜索程序，可自動(dòng)在互聯(lián)網(wǎng)上搜索信息。并且查看頁面的內(nèi)容，然后從中找到相關(guān)的信息，最后再?gòu)脑擁撁娴乃墟溄映霭l(fā)，繼續(xù)尋找其它相關(guān)的信息。網(wǎng)絡(luò)蜘蛛不斷的重復(fù)這個(gè)過程，并把經(jīng)過的所有網(wǎng)頁收集到搜索引擎所在的服務(wù)器中，這個(gè)過程一般采用的是廣度優(yōu)先算法。當(dāng)網(wǎng)絡(luò)蜘蛛收集到信息后，接下來要進(jìn)行以下幾個(gè)方面的工作:

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

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

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

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

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

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

2 技 術(shù)

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

2.1 中文分詞技術(shù)

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

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

網(wǎng)絡(luò)蜘蛛即Web Spider，是一種很形象的網(wǎng)頁搜索技術(shù)。把互聯(lián)網(wǎng)比喻成一個(gè)蜘蛛網(wǎng)，那么Spider就是網(wǎng)上爬來爬去的蜘蛛。網(wǎng)絡(luò)蜘蛛是通過網(wǎng)頁的鏈接地址來尋找網(wǎng)頁，從網(wǎng)站某一個(gè)頁面(通常是首頁)開始，讀取網(wǎng)頁的內(nèi)容，找到在網(wǎng)頁中的其他鏈接地址，然后通過這些鏈接地址尋找下一個(gè)網(wǎng)頁，這樣一直循環(huán)下去，直到把這個(gè)網(wǎng)站所有的網(wǎng)頁都抓取完為止。如果把整個(gè)互聯(lián)網(wǎng)當(dāng)成一個(gè)網(wǎng)站，那么網(wǎng)絡(luò)蜘蛛就可以用這個(gè)原理把互聯(lián)網(wǎng)上所有的網(wǎng)頁都抓取下來。在抓取網(wǎng)頁的時(shí)候，網(wǎng)絡(luò)蜘蛛一般有兩種算法:廣度優(yōu)先和深度優(yōu)先。廣度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會(huì)先抓取起始網(wǎng)頁中鏈接的所有的網(wǎng)頁，然后再選擇其中的一個(gè)鏈接網(wǎng)頁，繼續(xù)抓取在此網(wǎng)頁中鏈接的所有網(wǎng)頁。這是最常用的方式，因?yàn)檫@個(gè)方法可以讓網(wǎng)絡(luò)蜘蛛并行處理，提高其抓取速度。深度優(yōu)先是指網(wǎng)絡(luò)蜘蛛會(huì)從起始頁開始，一個(gè)鏈接一個(gè)鏈接跟蹤下去，處理完這條線路之后再轉(zhuǎn)入下一個(gè)起始頁，繼續(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ì)將無用的數(shù)據(jù)檢索出來，好處是算法簡(jiǎn)單不會(huì)漏掉檢索的數(shù)據(jù)。之后又發(fā)展出最大匹配分詞方法，該方法又分為正向最大分詞和逆向最大分詞。其原理和查字典類似，對(duì)常用單詞生成一個(gè)詞典，分析句子的過程中最大的匹配字典中的單詞，從而將句子拆分為有意義的單詞鏈。最大匹配法中正向分詞方法對(duì)偏正式詞語的分辨容易產(chǎn)生錯(cuò)誤，比如“首飾和服裝”會(huì)將“和服”作為單詞分出。本文實(shí)現(xiàn)的是逆向最大分詞方法，該分詞方法較正向正確率有所提高。最為復(fù)雜的是通過統(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)算法說明:

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

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

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

(4)如果是字典中最大單詞或者超過最大單詞數(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全部查找出來，并根據(jù)這些rowid在存儲(chǔ)實(shí)際數(shù)據(jù)的b樹中，將包含這些數(shù)據(jù)的行過濾出來。

4 結(jié) 論

本文簡(jiǎn)單地介紹了全文檢索技術(shù)的基本概念、原理和相關(guān)技術(shù)，并給出了逆向最大分詞技術(shù)的具體實(shí)現(xiàn)。隨著搜索引擎市場(chǎng)空間越來越大，搜索引擎也分得越來越細(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ī)模信息過濾技術(shù)研究及其在Web問答系統(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.