徐有健

（華南理工大學(xué)，廣東廣州，510006）

基于Lucene的中文分詞算法研究與實(shí)現(xiàn)

徐有健

（華南理工大學(xué)，廣東廣州，510006）

本文重點(diǎn)研究了如何改進(jìn)中文分詞算法，并根據(jù)新的中文算法，設(shè)計(jì)出可以滿足Hadoop文件系統(tǒng)可視化文件搜索引擎研究的中文分析器MyAnalyzer。

lucene；Hadoop；搜索；中文分詞

1 研究背景

作為中文信息處理的基礎(chǔ)，中文分詞分析器的效率和準(zhǔn)確度對(duì)搜索引擎研究至關(guān)重要。中文分詞的準(zhǔn)確性會(huì)直接影響到中文搜索引擎的準(zhǔn)確率和工作效率。目前，中文搜索引擎技術(shù)比西文搜索引擎技術(shù)落后一段距離的原因就在于中文搜索需要經(jīng)過(guò)分詞程序，西文引擎的分詞分析器不適用于中文分詞。比如Lucene自帶的StandardAnalyzer分析器，英文分詞的效果非常好，但是在中文分詞方面是將每一個(gè)漢字當(dāng)做一個(gè)詞，對(duì)中文分詞并沒(méi)有實(shí)用價(jià)值。至于Lucene自帶的另外兩種內(nèi)置分析器，SmartChineseAnalyzer和CJKAnalyzer，雖然可以實(shí)現(xiàn)中文分詞，但是分詞效率比較低，尤其是CJKAnalyze，會(huì)產(chǎn)生大量的無(wú)用分詞。由于Hadoop本身不帶有可視化文件系統(tǒng)管理功能，要建立基于Lucene的Hadoop文件系統(tǒng)可視化搜索引擎，就要研究如何改進(jìn)Lucene中文分詞器，使其滿足項(xiàng)目需要。

2 基于Lucene的Hadoop文件系統(tǒng)可視化文件搜索中的中文分詞算法實(shí)現(xiàn)

2.1 中文分詞模塊設(shè)計(jì)

2.1.1 中文分詞模塊框架設(shè)計(jì)

設(shè)計(jì)一個(gè)高性能實(shí)用化的中文分詞模塊對(duì)實(shí)現(xiàn)引擎搜索結(jié)果的準(zhǔn)確性和快捷性具有重要的意義。設(shè)計(jì)中文分詞模塊框架時(shí)要考慮到分詞速度、分詞精確度和系統(tǒng)維護(hù)的便利性。根據(jù)三個(gè)考慮要素，設(shè)計(jì)中文分詞框架如圖1-1所示。設(shè)計(jì)的分詞框架包括詞典、分詞器和性能評(píng)測(cè)三個(gè)模塊。

圖1 -1

2.1.2 中文分詞算法設(shè)計(jì)

為了適應(yīng)人們的日常閱讀習(xí)慣與寫(xiě)作習(xí)慣，本中文分詞模塊中文分詞算法設(shè)計(jì)采用了最佳匹配法的分詞算法。最佳匹配法分為正向的最佳匹配法和逆向的最佳匹配法，以“長(zhǎng)詞優(yōu)先”原則為核心，按照在詞頻的大小順序?qū)υ~典中的詞條進(jìn)行排列。正向最佳匹配算法的形式定義為:對(duì)于文本中的字符串ABC,A∈Z，AB∈Z，ABC不屬于Z，Z為字典，那么這串字符就切分為AB/C。例如，一封毛澤東親筆信原稿，采用正向最佳匹配法時(shí)則劃分為一封/毛澤東/親筆信/原稿。逆向最佳匹配法與正向最佳匹配法相反，從句子或者文章末尾開(kāi)始處理。具體的算法設(shè)計(jì)如下：

（1）正向最佳逐字匹配算法

采用正向最佳逐字匹配算法，要堅(jiān)持“長(zhǎng)詞優(yōu)先”原則，即當(dāng)一個(gè)漢字字符出現(xiàn)多種切分結(jié)果時(shí)，取含有長(zhǎng)度最長(zhǎng)的詞條切分結(jié)果。運(yùn)用長(zhǎng)詞優(yōu)先原則，有利于縮短對(duì)分詞詞典的檢索時(shí)間，提高分詞速度。運(yùn)用正向最佳逐字匹配算法進(jìn)行分詞的設(shè)計(jì)思路為：首先，在詞典中搜索字符串的最前面的字符，形成以該首字字符節(jié)點(diǎn)為根的詞典樹(shù)，將該字符串與詞典樹(shù)進(jìn)行匹配，一次匹配一個(gè)字符，匹配成功則繼續(xù)向下匹配，否則就回溯，找到上一個(gè)可以成詞的字，即終止標(biāo)識(shí)符為“T”，形成分詞結(jié)果。具體描述如下：

輸出：切分出的單詞集合S

Step1：在首字散列中定位待查詢漢字符串首字據(jù)待查詢字符串的首字的Unicode值。如果字符節(jié)點(diǎn)為根的詞典樹(shù)存在，則得到子樹(shù)節(jié)點(diǎn)的指針，并通過(guò)子樹(shù)節(jié)點(diǎn)的指針找到子節(jié)點(diǎn)表，記錄該節(jié)點(diǎn)的層數(shù)k，i=i+1，轉(zhuǎn)Step2。如果不存在，則單獨(dú)成詞，將該字添加到單詞集合S中，指向，重復(fù)Step1。

Step3：判斷該節(jié)點(diǎn)組詞標(biāo)識(shí)是否為T(mén)，如果是，則轉(zhuǎn)Step4；如果不是，則i=i+1，找到該節(jié)點(diǎn)的子節(jié)點(diǎn)表，轉(zhuǎn)Step2。

Step4：判斷該節(jié)點(diǎn)是否為葉子節(jié)點(diǎn)，如果是，若i＜n，將添加到單詞表S中，i=i+1，轉(zhuǎn)Step1；若i=n，將添加到單詞表S中，算法結(jié)束。如果不是，i=i+1，記錄該節(jié)點(diǎn)層次 k，轉(zhuǎn) Step2。

與傳統(tǒng)的正向最佳逐字配算法相比，這種正向最佳逐字配算法減少了分詞過(guò)程中試探性查詢的次數(shù)，無(wú)需預(yù)知待查詢?cè)~的長(zhǎng)度，實(shí)現(xiàn)一次匹配完成分詞，極大地提高了分詞的效率。以“今天我們要上學(xué)”為例，假設(shè)詞典的最長(zhǎng)詞長(zhǎng)為5。

一般的最大匹配分詞算法的查找過(guò)程為：

用本文設(shè)計(jì)的最大匹配算法的查找過(guò)程為：

今天我們要上學(xué)我們要上學(xué)要上學(xué)上學(xué)。

通過(guò)比較，一般的最大匹配分詞算法的查找次數(shù)為12次，本文的最大匹配算法為4次，大大減少了查找的次數(shù)，提高了查找的效率。

（2）逆向最佳逐字匹配算法

逆向最佳逐字匹配算法的原理與正向最佳逐字匹配算法基本相同，因此不以加贅述。與正向最佳逐字匹配算法不同的是，逆向最長(zhǎng)匹配的分詞算法是從右至左，從字符串后面進(jìn)行掃描，需要配合逆向最長(zhǎng)匹配的詞典結(jié)構(gòu)進(jìn)行使用。

2.1.3 詞典設(shè)計(jì)

為了實(shí)現(xiàn)中文分詞模塊的順利使用，要結(jié)合分詞算法設(shè)計(jì)出詞典。

首先，要統(tǒng)計(jì)中文中的詞的字?jǐn)?shù)個(gè)數(shù)的頻率，根據(jù)頻率制定各字?jǐn)?shù)的詞條。一般來(lái)說(shuō)，中文詞中，字?jǐn)?shù)為2的詞語(yǔ)數(shù)量比較多，多字（四個(gè)字以上）的使用頻率比較低。其次，為了配合正向最佳逐字匹配算法使用，要設(shè)計(jì)出正序詞典機(jī)制。詞典中首字的索引值即為首字的 Unicode 編碼。詞典的第一層要建立起以詞語(yǔ)首字為索引的首字散列表，使各個(gè)首字相同的詞語(yǔ)采用同一根節(jié)點(diǎn)的詞典結(jié)構(gòu)。除了詞語(yǔ)的首字外，剩余部分在內(nèi)存中采用樹(shù)的形式存放。最后，為了配合逆向最佳匹配算法，要設(shè)計(jì)出逆序詞典作為使用基礎(chǔ)。逆序詞典結(jié)構(gòu)與正序詞典結(jié)構(gòu)完全相同，但是要將每個(gè)詞條的順序顛倒，建立起存儲(chǔ)詞語(yǔ)尾字W以及在每個(gè)W下記錄了以尾字W為詞尾的所有詞匯的首字散列表。

2.2 中文分詞機(jī)制的實(shí)現(xiàn)

實(shí)現(xiàn)分詞機(jī)制首先要實(shí)現(xiàn)分詞預(yù)處理，將需要分詞的內(nèi)容轉(zhuǎn)換為分詞模塊可以處理的文本格式。其次，通過(guò)Lucene的工具包中的Analayzer類工具，實(shí)現(xiàn)設(shè)計(jì)的中文分詞模塊。由于Lucene自帶的SmartChineseAnalyzer和CJKAnalyze不能滿足引擎中的中文分詞需要，因此要開(kāi)發(fā)出新的中文分析器。本文將新的分詞算法加入到Lucene當(dāng)中開(kāi)發(fā)出適合需要的MyAnalyzer，通過(guò)MyAnalyzer實(shí)現(xiàn)新設(shè)計(jì)的中文分詞算法。

2.3 分詞性能測(cè)試

2.3.1 分詞速度測(cè)試

（1）實(shí)驗(yàn)方法: 以經(jīng)過(guò)分詞預(yù)處理后得到的純文本為速度測(cè)試材料，通過(guò)計(jì)算分詞的速度與質(zhì)量對(duì)分詞模塊的分詞性能進(jìn)行測(cè)試。

（2）實(shí)驗(yàn)方案：文本長(zhǎng)度從500字符開(kāi)始，以1500個(gè)字符為一個(gè)遞增區(qū)間，分別計(jì)算每次分詞所耗的時(shí)間。

（3）實(shí)驗(yàn)數(shù)據(jù)測(cè)量：由于實(shí)驗(yàn)環(huán)境無(wú)法達(dá)到理想狀態(tài)，同一個(gè)文本每次切分所耗費(fèi)的時(shí)間并不完全相同導(dǎo)致記錄時(shí)間有誤差，為了使實(shí)驗(yàn)數(shù)據(jù)更加接近標(biāo)準(zhǔn)數(shù)據(jù)，要對(duì)每個(gè)文本進(jìn)行反復(fù)測(cè)試，取數(shù)據(jù)的平均值。

（4）實(shí)驗(yàn)結(jié)果：經(jīng)過(guò)反復(fù)測(cè)驗(yàn)，獲得實(shí)驗(yàn)數(shù)據(jù)如表1-3

（5）數(shù)據(jù)分析：從表1-3可以看出，分析器的分詞速度一直都保持在20字/ms至25字/ms的速度之間。以這個(gè)速度，本分詞模塊每秒鐘處理字符數(shù)在20000到250000之間，可以滿足現(xiàn)在中文搜索引擎對(duì)速度的要求。

表1 -3

2.3.2 分詞精準(zhǔn)度測(cè)試

（1）實(shí)驗(yàn)方案：隨機(jī)選擇一個(gè)句子，通過(guò)MyAnalyzer、SmartChineseAnalyzer和CJKAnalyze三種分析器進(jìn)行分詞，對(duì)結(jié)果進(jìn)行比較，判斷新設(shè)計(jì)的中文分詞模塊的精準(zhǔn)度。

（2）實(shí)驗(yàn)步驟：①選擇了“2008年12月26日，中國(guó)海軍首批護(hù)航編隊(duì)踏上了遠(yuǎn)洋護(hù)航的漫長(zhǎng)征程?！弊鳛榉衷~文本

②參與實(shí)驗(yàn)的分析器包括MyAnalyzer、SmartChineseAnalyzer和CJKAnalyze

（3）實(shí)驗(yàn)結(jié)果：MyAnalyzer的分詞結(jié)果是 2008/年/12/月/26/日/中國(guó)/海軍/首批/護(hù)航/編隊(duì)/踏上/了/遠(yuǎn)洋/護(hù)航/的/漫長(zhǎng)/征程/

SmartChineseAnalyzer的分詞結(jié)果是年/月/日/中/國(guó)/海/軍/首/批/護(hù)/航/編/隊(duì)/踏/上/了/遠(yuǎn)/洋/護(hù)/航/的/漫/長(zhǎng)/征/程/

CJKAnalyze的分詞結(jié)果是2008/年/12/月/26/日中/中國(guó)/國(guó)海/海軍/軍首/首批/批護(hù)/護(hù)航/航編/編隊(duì)/踏上/上了/了遠(yuǎn)/遠(yuǎn)洋/洋護(hù)/護(hù)航/航的/的漫/漫長(zhǎng)/長(zhǎng)征/征程/

（4）實(shí)驗(yàn)結(jié)論：通過(guò)對(duì)分詞結(jié)果進(jìn)行對(duì)比，可以發(fā)現(xiàn)MyAnalyzer的分詞準(zhǔn)確性最高，具體體現(xiàn)在：SmartChineseAnalyzer將中文外的其他字符種類都給過(guò)濾掉了。CJKAnalyze保留了其他種類的字符，但是產(chǎn)生了許多無(wú)用的切分。相比之下，MyAnalyzer保留了中文外的其他字符種類，并且分詞字?jǐn)?shù)不限于兩個(gè)字?jǐn)?shù)，準(zhǔn)確率較高。因此，MyAnalyzer可以滿足Hadoop文件系統(tǒng)可視化文件搜索引擎設(shè)計(jì)的需要。

3 結(jié)束語(yǔ)

關(guān)于中文分詞的算法，目前仍然沒(méi)有完美的設(shè)計(jì)方案，可以完美兼顧中文分詞的準(zhǔn)確性與高效率，而是或多或少會(huì)存在一定的局限性。但是，通過(guò)比較各種分詞算法的優(yōu)劣，并不斷對(duì)分詞算法加以改善，取長(zhǎng)補(bǔ)短，終有一日可以整合出一個(gè)效率高、準(zhǔn)確率高的分詞方法，推動(dòng)中文引擎技術(shù)的發(fā)展。

[1] 戴洪，蔣靜，樊程，等.一種基于LUCENE的中文分詞算法研究[J].青島大學(xué)學(xué)報(bào)：自然科學(xué)版，2011（3）：53-58.

[2] 趙珂，逯鵬，李永強(qiáng).基于Lucene的搜索引擎設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2011（16）：39-41.

[3] 趙旭，王慶樺.向LUCENE搜索引擎中加入中文同義詞查詢[J].科技信息，2011（7）：60-61.

Lucene the Chinese word segmentation algorithm and implementation of research-based

Xu Youjian
(South China University of Technology，Guangzhou，510006)

This paper is aimed at improving Chinese word segmentation module.According to the new Chinese word segmentation module,an analyzer named MyAnalyzer that can process Hadoop file System research is developed.

lucene;Hadoop;search;Chinese word