1/1搜索引擎中文分詞原理與實(shí)現(xiàn)while(ts.incrementToken()){

//取得下一個(gè)詞

搜索引擎中文分詞原理與實(shí)現(xiàn)

因?yàn)橹形奈谋局?，詞和詞之間不像英文一樣存在邊界，所以中文分詞是一個(gè)專業(yè)處理中

文信息的搜索引擎首先面對(duì)的問(wèn)題，需要靠程序來(lái)切分出詞。一、LUCene中的中文分詞

LUCene在中處理中文的常用方法有三種，以皎死獵人的狗"為例說(shuō)明之：

單字:【咬】

【死】【獵】【人】【的】【狗】

二元覆蓋：【咬死】【死獵】【獵人】【人的】【的狗】

分

詞：【咬】【死】【獵人】【的】

【狗】

LUCene中的StandardTokenizer采用單子分詞方式，CJKTokenize采用二元覆蓋方式。1、LUCene切分原理

LUCene中負(fù)責(zé)語(yǔ)言處理的部分在org.apache.Iucene.analysis包，其中，TokenStream類用來(lái)進(jìn)行基本的分詞工作，Analyzer類是TokenStream的包裝類，負(fù)責(zé)整個(gè)解析工作，Analyzer類接收整段文本，解析出有意義的詞語(yǔ)。

通常不需要直接調(diào)用分詞的處理類analysis,而是由LUCene內(nèi)存內(nèi)部來(lái)調(diào)用，其中：

(1)在索引階段，調(diào)用addDocument(doc)時(shí)，LUCene內(nèi)部使用Analyzer來(lái)處理每個(gè)需要

索引的列，具體如下圖：

圖1LUCene對(duì)索引文本的處理

IndexWriterindex=newIndexWriter(indexDirectory,newCnAnalyzer(),//用于支持分詞的分析

器!inCremental,

IndexWriter.MaxFieldLength.UNLIMITED);

(2)在搜索階段，調(diào)用

QUeryParSer.parse(queryText)來(lái)解析查詢串時(shí)，QUeryParSer會(huì)調(diào)用Analyzer來(lái)拆分查詢字符串，但是對(duì)于通配符等查詢不會(huì)調(diào)用Analyzer。

Analyzeranalyzer=newCnAnalyzer();

//支持中文的分詞

QUeryParSerParSer=newQUeryParSer(VerSiOn.LUCENE_CURRENT,"title",analyzer);因?yàn)樵谒饕退阉麟A段都調(diào)用了分詞過(guò)程，索引和搜索的切分處理要盡量一致，所以分詞效果改變后需要重建索引。

為了測(cè)試LUCene的切分效果，下面是直接調(diào)用Analysis的例子：Analyzeranalyzer=newCnAnalyzer();

//創(chuàng)建一個(gè)中文分析器

TokenStreamts=analyzer.tokenStream("myfield",newStringReader("待切分文本"));

//

取得Token流

SyStem.out.println("token:"+ts);

}

2、LUCene中的Analyzer

為了更好地搜索中文，通過(guò)下圖來(lái)了解一下在LUCene中通過(guò)WhiteSPaCeTOkeniZer、WOrdDeIimiterFiIter、LOWerCaSeFiIter處理英文字符串的流程：

LeXCorPBFG-9000

WhitespareTokeniZer

LeXCorPBFG-9000

WordDeliiniterFilterCCltenaleWOrdii=1

r

LOWerCaSeFiIler

IejtCCrP

圖2LUCene處理英文字符串流程

、查找詞典算法

詞典格式可以是方便人工查看和編輯的文本文件格式，也可以是方便機(jī)器讀入的二進(jìn)

制格式。詞典的最基本文本文件格式就是每行一個(gè)詞。在基于詞典的中文分詞方法中，詞

典匹配算法是基礎(chǔ)。一般詞典規(guī)模都在幾十萬(wàn)詞以上，所以為了保證切分速度，需要選擇一個(gè)好的查找詞典算法。

1、標(biāo)準(zhǔn)Trie樹

一個(gè)數(shù)字搜索Trie樹的一個(gè)節(jié)點(diǎn)只保留一個(gè)字符，如果一個(gè)單詞比一個(gè)字符長(zhǎng)，則包

含第一個(gè)字符的節(jié)點(diǎn)有指針指向下一個(gè)字符的節(jié)點(diǎn)，依次類推。這樣組成一個(gè)層次結(jié)構(gòu)的

樹，樹的第一層包括所有單詞的第一個(gè)字符，樹的第二層包括所有單詞的第二個(gè)字符，依次

類推，數(shù)字搜索樹的最大高度是詞典中最長(zhǎng)單詞的長(zhǎng)度。比女口：如下單詞序列組成的詞典(asatbebyheinisitOfOnOrto)會(huì)生成如下圖所示的數(shù)字搜索樹:

圖3數(shù)字搜索樹

數(shù)字搜索樹的結(jié)構(gòu)獨(dú)立于生成樹時(shí)單詞進(jìn)入的順序，這里，Trie樹的高度是2。因?yàn)闃?/p>

的高度很小，在數(shù)字搜索Trie樹種搜索一個(gè)單詞的速度很快。但是，這是以內(nèi)存消耗為代

價(jià)的，樹中每個(gè)節(jié)點(diǎn)都需要很多內(nèi)存。假設(shè)每個(gè)詞都是由26個(gè)小寫英文字母中的一個(gè)組成

的，這個(gè)節(jié)點(diǎn)中會(huì)有26個(gè)指針。所以不太可能直接用這樣的數(shù)字搜索樹來(lái)存儲(chǔ)中文這樣的

大字符集。

Trie樹在實(shí)現(xiàn)上有一個(gè)樹類(SearChTrie)和一個(gè)節(jié)點(diǎn)類(TrieNode)。SearChTrie的主要方法有兩個(gè)：

(1)增加單詞到搜索樹，方法原型是：addWord(Stringword)。

(2)從文本的指定位置開始匹配單詞，方法原型是：matchLOng(Stringtext,intOffSet)。2、三叉Trie樹

在一個(gè)三叉搜索樹(TernarySearChTrie)中，每一個(gè)節(jié)點(diǎn)包括一個(gè)字符，但和數(shù)字搜索樹不同，三叉搜索樹只有三個(gè)指針：一個(gè)指向左邊的樹；一個(gè)指向右邊的樹；還有一個(gè)向下，指向單詞的下一個(gè)數(shù)據(jù)單元。三叉搜索樹是二叉搜索樹和數(shù)字搜索樹的混合體。它有

和數(shù)字搜索樹差不多的速度但是和二叉搜索樹一樣只需要相對(duì)較少的內(nèi)存空間。

樹是否平衡取決于單詞的讀入順序。如果按順序后的順序插入，則生成方式最不平衡。

單詞的讀入順序?qū)τ趧?chuàng)建平衡的三叉搜索樹很重要，但對(duì)于二叉搜索樹就不太重要。通過(guò)

選擇一個(gè)排序后數(shù)據(jù)單元集合的中間值，并把它作為開始節(jié)點(diǎn)，我們可以創(chuàng)建一個(gè)平衡的三

叉樹。如下代碼可以用來(lái)生成平衡的三叉樹詞典：

*在調(diào)用此方法前，先把詞典數(shù)組k排好序

*@Paramfp寫入的平衡序的詞典

*@Paramk排好序的詞典數(shù)組

*@ParamOffSet偏移量

*@Paramn長(zhǎng)度

*@throwsEXCePtiOn

*/

VoidOUtPUtBaIanced(BufferedWriterfp,ArrayLiStVString>k,intoffset,intn){

intm;

if(n>1;//m=n/2

Stringitem=k.get(m+offset);

fp.write(item);//把詞條寫入到文件

fp.write('?n');

OUtPUtBaIanced(fp,k,offset,m);〃輸出左半部分

OUtPUtBaIanced(fp,k,OffSet+m+1,n-m-1);//輸出右半部分

}

再次以有序的數(shù)據(jù)單元(asatbebyheinisitofonorto)為例。首先把關(guān)鍵字"is乍為

中間值并且構(gòu)建一個(gè)包含字母“i的根節(jié)點(diǎn)。它的直接后繼節(jié)點(diǎn)包含字母“S并且可以存儲(chǔ)任何與“is有關(guān)聯(lián)的數(shù)據(jù)。對(duì)于“i的左樹，我們選擇“be作為中間值并且創(chuàng)建一個(gè)包含字母“b”的節(jié)點(diǎn)，字母“b的直接后繼節(jié)點(diǎn)包含“e。'該數(shù)據(jù)存儲(chǔ)在“e節(jié)點(diǎn)。對(duì)于“i的右樹，按照邏輯，選擇“On作為中間值，并且創(chuàng)建“0節(jié)點(diǎn)以及它的直接后繼節(jié)點(diǎn)“n”最終的三叉樹如下

圖所示：

圖4三叉樹

垂直的虛線代表一個(gè)父節(jié)點(diǎn)下面的直接后繼節(jié)點(diǎn)。只有父節(jié)點(diǎn)和它的直接后繼節(jié)點(diǎn)才能形成一個(gè)數(shù)據(jù)單元的關(guān)鍵字："i"和“S形成關(guān)鍵字“is,”但是“i和“b不能形成關(guān)鍵字，因

為它們之間僅用一條斜線相連，不具有直接后繼關(guān)系。上圖中帶圈的節(jié)點(diǎn)為終止節(jié)點(diǎn)。如果

查找一個(gè)詞以終止節(jié)點(diǎn)結(jié)束，則說(shuō)明三叉樹包含這個(gè)詞。以搜索單詞“is為例，向下到相等

的孩子節(jié)點(diǎn)“s”在兩次比較后找到“is;”查找“aX”，執(zhí)行三次比較達(dá)到首字符“a”然后

經(jīng)過(guò)兩次比較到達(dá)第二個(gè)字符“X；'返回結(jié)果是“ax不在樹中。

三、中文分詞原理

中文分詞就是對(duì)中文斷句，這樣能消除文字的部分歧義。除了基本的分詞功能，為了消除歧義還可以進(jìn)行更多的加工。中文分詞可以分成如下幾個(gè)子任務(wù)：

（1）分詞：把輸入的標(biāo)題或者文本內(nèi)容等分成詞。

（2）詞性標(biāo)注（POS：給分出來(lái)的詞標(biāo)注上名詞或動(dòng)詞等詞性。詞性標(biāo)注可以部分消除詞的歧義，例如行”作為量詞和作為形容詞表示的意思不一樣。

（3）語(yǔ)義標(biāo)注：把每個(gè)詞標(biāo)注上語(yǔ)義編碼。

很多分詞方法都借助詞庫(kù)。詞庫(kù)的來(lái)源是語(yǔ)料庫(kù)或者詞典，例如人民日?qǐng)?bào)語(yǔ)料庫(kù)”或

者《現(xiàn)代漢語(yǔ)大詞典》。

中文分詞有以下兩類方法：

（1）機(jī)械匹配的方法：例如正向最大長(zhǎng)度匹配（ForWardMaXimUmMatCh）的方法和逆向最大長(zhǎng)度匹配（ReVerSeMaXimUmMatChing）的方法。

（2）統(tǒng)計(jì)的方法：例如概率語(yǔ)言模型分詞方法和最大熵的分詞方法等。

正向最大長(zhǎng)度品牌的分詞方法實(shí)現(xiàn)起來(lái)很簡(jiǎn)單。每次從詞典中查找和待匹配串前綴最長(zhǎng)匹配的詞，如果找到匹配詞，則把這個(gè)詞作為切分詞，待匹配串減去該詞；如果詞典中沒

有詞與其匹配，則按單字切分。例如：Trie樹結(jié)構(gòu)的詞典中包括如下的詞語(yǔ)：

大大學(xué)大學(xué)生活動(dòng)生活中中心心

為了形成平衡的Trie樹，把詞先排序，結(jié)果為：

中中心大大學(xué)大學(xué)生心活動(dòng)生活

按平衡方式生成的詞典Trie樹如下圖所示，其中，粗黑顯示的節(jié)點(diǎn)可以作為匹配終止節(jié)點(diǎn)：

(

?

)

圖5三叉樹

輸入大學(xué)生活動(dòng)中心”首先匹配出大學(xué)生”然后匹配出活動(dòng)”，最后匹配出中心”切分過(guò)程如下表所示：

已匹配上的結(jié)果待匹配串

NULL大學(xué)生活動(dòng)中心

大學(xué)生活動(dòng)中心

大學(xué)生/活動(dòng)中心

大學(xué)生/活動(dòng)/中心NULL

在最大長(zhǎng)度匹配的分詞方法中，需要用到從指定字符串返回指定位置的最長(zhǎng)匹配詞的方法。例如：當(dāng)輸入串是大學(xué)生活動(dòng)中心”，則返回大學(xué)生”這個(gè)詞，而不是返回大”或者大學(xué)”。

四、中文分詞流程與結(jié)構(gòu)

中文分詞總體流程與結(jié)構(gòu)如下圖所示：

切分工具

詞査找模塊切分算法

JLI丿

圖6中文分詞結(jié)構(gòu)圖

簡(jiǎn)化版的中文分詞切分過(guò)程說(shuō)明