摘  要： 針對(duì)Lucene自帶中文分詞器分詞效果差的缺點(diǎn)，在分析現(xiàn)有分詞詞典機(jī)制的基礎(chǔ)上,，設(shè)計(jì)了基于全哈希整詞二分算法的分詞器,，并集成到Lucene中，算法通過對(duì)整詞進(jìn)行哈希,，減少詞條匹配次數(shù),，提高分詞效率。該分詞器詞典文件維護(hù)方便,，可以根據(jù)不同應(yīng)用的要求進(jìn)行定制,，從而提高了檢索效率。
關(guān)鍵詞： Lucene,；哈希,；整詞二分；最大匹配

    信息技術(shù)的發(fā)展,，形成了海量的電子信息數(shù)據(jù),，人們對(duì)信息檢索的要求越來越高，搜索引擎技術(shù)也得到了快速發(fā)展,，并逐漸地被應(yīng)用到越來越多的領(lǐng)域,。由于搜索引擎技術(shù)涉及信息檢索、人工智能,、自然語言處理等多種學(xué)科,，很多搜索算法都不公開[1]。Lucene是一個(gè)優(yōu)秀的開源全文搜索引擎框架,，通過Lucene可以方便地將全文搜索技術(shù)嵌入到各種應(yīng)用當(dāng)中,，有針對(duì)性地實(shí)現(xiàn)強(qiáng)大的搜索功能，因此近年來Lucene的應(yīng)用越來越廣泛,。
    Lucene在對(duì)信息進(jìn)行索引前,，需要進(jìn)行分詞，西方語言使用空格和標(biāo)點(diǎn)來分隔單詞,，而中文使用表意文字,，不能通過空格和標(biāo)點(diǎn)來進(jìn)行分詞。Lucene自帶中文分詞器有StandardAnalyzer,、ChineseAnalyzer,、CJKAnalyzer，這些分詞器要么是單字切分,，要么采用二分法切分,，它們并不能有效地解決中文分詞問題,。本文設(shè)計(jì)并實(shí)現(xiàn)了基于全哈希整詞二分算法的分詞器，并集成到Lucene中,，從而提高了Lucene處理中文信息的能力,。
1 Lucene簡(jiǎn)介
    Lucene是Apache軟件基金會(huì)jakarta項(xiàng)目組的一個(gè)子項(xiàng)目，是一個(gè)優(yōu)秀的開源全文搜索引擎工具包,，并不是一個(gè)完整的全文檢索應(yīng)用,。它提供了豐富的API函數(shù)，可以方便地創(chuàng)建索引,，嵌入到各種應(yīng)用中實(shí)現(xiàn)全文檢索[2],。Lucene作為開源的全文搜索引擎，架構(gòu)清晰,，易于擴(kuò)展,，而且索引文件格式獨(dú)立于應(yīng)用平臺(tái)，從而使索引文件能夠跨平臺(tái)共享,，能夠?qū)θ我饪赊D(zhuǎn)換為文本格式的數(shù)據(jù)進(jìn)行索引和搜索,，例如網(wǎng)頁(yè)、本地文件系統(tǒng)中的WORD文檔,、PDF文檔等一切可以從中提取文本信息的文件[3],。
2 基于全Hash的整詞二分分詞器
    目前中文分詞算法大致可分為三大類：機(jī)械分詞方法、基于理解分詞方法和基于統(tǒng)計(jì)分詞方法[4],。其中機(jī)械分詞把待分解的漢字串與詞典中的詞條進(jìn)行匹配來判斷是否是一個(gè)詞，是當(dāng)前應(yīng)用廣泛的一種分詞方法,。在深入研究整詞二分,、TRIE 索引樹和逐字二分這三種傳統(tǒng)的機(jī)械分詞算法及其改進(jìn)算法的基礎(chǔ)上，本文設(shè)計(jì)并實(shí)現(xiàn)了基于全哈希的整詞二分分詞器,。
2.1 詞典設(shè)計(jì)
    詞典設(shè)計(jì)是機(jī)械分詞的關(guān)鍵,，詞典結(jié)構(gòu)應(yīng)與分詞算法相結(jié)合，這樣設(shè)計(jì)的分詞器分詞效率才能得到最大限度的提高[5],。全哈希整詞二分詞典機(jī)制由首字哈希表,、哈希節(jié)點(diǎn)、詞哈希表和詞碰撞表構(gòu)成,，如圖1所示,。

    (1)首字哈希表
    漢字在計(jì)算機(jī)中是以內(nèi)碼的形式存儲(chǔ)。根據(jù)內(nèi)碼獲取漢字對(duì)應(yīng)的區(qū)位碼,，從而給定一個(gè)漢字,，可以通過哈希函數(shù)直接得到其在首字哈希表中的位置[6]。用lowByte表示漢字內(nèi)碼的低字節(jié),，highByte表示漢字內(nèi)碼的高字節(jié),，則哈希函數(shù)設(shè)計(jì)如下：
    Index=((highByte-160)×100+lowByte-160)-1601
    詞個(gè)數(shù)：記錄以該字為首字的詞的個(gè)數(shù),。
    最長(zhǎng)詞字?jǐn)?shù)：記錄以該字為首字的最長(zhǎng)詞所包含的字?jǐn)?shù)。
    是否單字成詞：標(biāo)識(shí)該字是否可以單獨(dú)成詞,。
    哈希節(jié)點(diǎn)指針：指向以該字為首字的第一個(gè)哈希節(jié)點(diǎn),。
    (2)哈希節(jié)點(diǎn)
    記錄了詞長(zhǎng)(iLength)、相同詞長(zhǎng)的詞的個(gè)數(shù)(iNumber),、詞哈希表的地址(wordArray)以及下一個(gè)哈希節(jié)點(diǎn)的指針(nextNode)等信息,。對(duì)相同首字的詞條按包含的字?jǐn)?shù)進(jìn)行分組，再對(duì)除首字外的剩余字符串進(jìn)行全詞哈希,，哈希節(jié)點(diǎn)按照詞長(zhǎng)倒序排列,。
    (3)詞哈希表
    記錄了哈希值相同的詞條的個(gè)數(shù)（iNum）、指向保存詞條的動(dòng)態(tài)數(shù)組（wordList）,，即詞碰撞表,。詞哈希表的大小為詞長(zhǎng)相同的詞的數(shù)量，哈希函數(shù)的選取不能太復(fù)雜,，否則會(huì)增加分詞時(shí)間,，同時(shí)也要考慮哈希結(jié)果的均勻分布。
    (4)詞碰撞表
    詞碰撞表實(shí)際上是一個(gè)動(dòng)態(tài)數(shù)組,，對(duì)于詞典中首字相同且詞長(zhǎng)相同的詞條,，如果哈希值相同，則以動(dòng)態(tài)數(shù)組的形式保存,，且只保存除首字之外的剩余字串,。對(duì)于哈希值相同的詞條，采用二分查找,。
2.2 分詞算法
    該分詞詞典機(jī)制適用于正向最大匹配算法和逆向最大匹配算法,，本文采用正向最大匹配算法為例使用該詞典機(jī)制進(jìn)行分詞。
    第一步：取待匹配字符串
    假設(shè)String為待分詞語句,，如果String不包含任何字符(即長(zhǎng)度為零),，則表示語句分詞完畢。從String=A1A2A3A4…An中讀取第一個(gè)字A1,，從首字哈希表中獲取以該字為首字的最長(zhǎng)詞的字?jǐn)?shù)m,，如果String剩余待分詞的字?jǐn)?shù)不足m，則取Str為String的剩余待分詞的字符串,，否則取字符串Str=A1A2…Am為待匹配字符串,。
    第二步：判斷Str的長(zhǎng)度
    (1)如果Str的長(zhǎng)度為1，在首字哈希表中找到對(duì)應(yīng)的位置,，判斷單獨(dú)成詞標(biāo)志是否為F,，如果是說明Str不是一個(gè)詞；否則說明Str是一個(gè)詞，分出該詞,。設(shè)置待切分語句String=A2A3A4…An后轉(zhuǎn)第一步,。
    (2)如果Str的長(zhǎng)度大于1，轉(zhuǎn)第三步,。
    第三步：對(duì)待匹配字符串分詞
    在A1對(duì)應(yīng)的哈希節(jié)點(diǎn)鏈表中查找詞長(zhǎng)為字串Str長(zhǎng)度的節(jié)點(diǎn),，有如下兩種情況：
    (1)如果沒有找到，則Str字串不是一個(gè)詞,，則去掉Str的最后面的一個(gè)字,，轉(zhuǎn)第二步。
    (2)如果找到對(duì)應(yīng)的哈希節(jié)點(diǎn),，則計(jì)算Str(除去首字,，因?yàn)槭鬃植槐４?的哈希值，得到在詞哈希表中的位置,，有如下三種情況：
    ①若對(duì)應(yīng)的碰撞數(shù)(iNum)等于0,，說明Str不是一個(gè)詞。
    ②若對(duì)應(yīng)的碰撞數(shù)(iNum)等于1,，則比較去掉首字的Str與詞碰撞表中的詞,，如果相等，則Str成詞,，否則不成詞,。
    ③若對(duì)應(yīng)的碰撞數(shù)(iNum)大于1，則在詞碰撞表中進(jìn)行二分查找,，如果找到則成詞,，否則不成詞。
    上述三種情況若都不成詞,，則去掉Str的最后面的一個(gè)字,，轉(zhuǎn)第二步；若成詞,，則在String中分出一個(gè)詞Str，將語句String設(shè)置為除去Str的剩余字串,，轉(zhuǎn)第一步,。
2.3 實(shí)驗(yàn)結(jié)果及分析
    可以很方便地將分詞器集成到Lucene中，該分詞器不妨命名為MyAnalyzer,。對(duì)3個(gè)分詞器ChineseAnalyzer,、CJKAnalyzer、MyAnalyzer進(jìn)行實(shí)驗(yàn),，采用復(fù)合索引結(jié)構(gòu),，只對(duì)文檔內(nèi)容創(chuàng)建域，且只對(duì)文檔內(nèi)容進(jìn)行索引但不存儲(chǔ)，在分詞時(shí)間,、索引文件大小兩方面做對(duì)比,，分別對(duì)兩個(gè)文檔集進(jìn)行實(shí)驗(yàn)，文檔集1含有3個(gè)文件,，共2.38 MB,，文檔集2含有126個(gè)文件，共164 MB,。表1為實(shí)驗(yàn)結(jié)果數(shù)據(jù),。

    通過實(shí)驗(yàn)數(shù)據(jù)可知，采用CJKAnalyzer二分法切分形成的索引文件要遠(yuǎn)大于采用ChineseAnalyzer 單字切分所形成的索引文件,，但兩者在索引時(shí)間上相差并不大,，由于索引文件中記錄關(guān)鍵字及其詞頻和所在文檔等信息，所以當(dāng)測(cè)試文檔集增大時(shí),，采用本文設(shè)計(jì)的MyAnalyzer分詞器所產(chǎn)生的索引文件大小與采用ChineseAnalyzer所產(chǎn)生的索引文件相差逐步減少,，但遠(yuǎn)小于采用CJKAnalyzer分詞器產(chǎn)生的索引文件大小。最為關(guān)鍵的是,，采用MyAnalyzer生成的索引能大大提高全文檢索的查準(zhǔn)率和查全率,。
3 應(yīng)用
    Lucene具有方便使用、易于擴(kuò)展等優(yōu)點(diǎn),，越來越多的開發(fā)者將其嵌入到不同的應(yīng)用中實(shí)現(xiàn)全文檢索功能,。各種應(yīng)用有著不同的檢索需求，本文通過擴(kuò)展Lucene的中文分詞器,，使開發(fā)者可以針對(duì)系統(tǒng)的特點(diǎn)定制自己的分詞詞典,，根據(jù)具體的需求進(jìn)行分詞，并創(chuàng)建索引,，從而提高全文檢索的效率,。
參考文獻(xiàn)
[1] 胡長(zhǎng)春，劉功申.面向搜索引擎Lucene的中文分析器[J]. 計(jì)算機(jī)工程與應(yīng)用,，2009,，45（12）157-159.
[2] 索紅光，孫鑫.基于Lucene的中文全文檢索系統(tǒng)的研究與設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì),，2008,，29(19)：5083-5085.
[3] 吳青，夏紅霞.基于Lucene全文檢索引擎的應(yīng)用與改進(jìn)[J].武漢理工大學(xué)學(xué)報(bào),，2008,，30(7)：145-148.
[4] 孫茂松，左正平,，黃昌寧.漢語自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報(bào),，1999,，14(1)：1-6.
[5] 李慶虎，陳玉健,，孫家廣.一種中文分詞詞典新機(jī)制-雙字哈希機(jī)制[J].中文信息學(xué)報(bào),，2002，17(4)：13-18.
[6] 張科.多次Hash快速分詞算法[J].計(jì)算機(jī)工程與設(shè)計(jì),，2007,，28(7)：1716-1718.