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

    信息技術(shù)的發(fā)展，形成了海量的電子信息數(shù)據(jù),，人們對信息檢索的要求越來越高,，搜索引擎技術(shù)也得到了快速發(fā)展，并逐漸地被應(yīng)用到越來越多的領(lǐng)域,。由于搜索引擎技術(shù)涉及信息檢索,、人工智能、自然語言處理等多種學(xué)科,，很多搜索算法都不公開[1],。Lucene是一個(gè)優(yōu)秀的開源全文搜索引擎框架，通過Lucene可以方便地將全文搜索技術(shù)嵌入到各種應(yīng)用當(dāng)中,，有針對性地實(shí)現(xiàn)強(qiáng)大的搜索功能,，因此近年來Lucene的應(yīng)用越來越廣泛。
    Lucene在對信息進(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簡介
    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)頁,、本地文件系統(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)碼獲取漢字對應(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ù)。
    最長詞字?jǐn)?shù)：記錄以該字為首字的最長詞所包含的字?jǐn)?shù),。
    是否單字成詞：標(biāo)識(shí)該字是否可以單獨(dú)成詞,。
    哈希節(jié)點(diǎn)指針：指向以該字為首字的第一個(gè)哈希節(jié)點(diǎn)。
    (2)哈希節(jié)點(diǎn)
    記錄了詞長(iLength),、相同詞長的詞的個(gè)數(shù)(iNumber),、詞哈希表的地址(wordArray)以及下一個(gè)哈希節(jié)點(diǎn)的指針(nextNode)等信息。對相同首字的詞條按包含的字?jǐn)?shù)進(jìn)行分組,，再對除首字外的剩余字符串進(jìn)行全詞哈希，哈希節(jié)點(diǎn)按照詞長倒序排列,。
    (3)詞哈希表
    記錄了哈希值相同的詞條的個(gè)數(shù)（iNum）,、指向保存詞條的動(dòng)態(tài)數(shù)組（wordList），即詞碰撞表,。詞哈希表的大小為詞長相同的詞的數(shù)量,，哈希函數(shù)的選取不能太復(fù)雜，否則會(huì)增加分詞時(shí)間,，同時(shí)也要考慮哈希結(jié)果的均勻分布,。
    (4)詞碰撞表
    詞碰撞表實(shí)際上是一個(gè)動(dòng)態(tài)數(shù)組，對于詞典中首字相同且詞長相同的詞條,，如果哈希值相同,，則以動(dòng)態(tài)數(shù)組的形式保存，且只保存除首字之外的剩余字串,。對于哈希值相同的詞條,，采用二分查找。
2.2 分詞算法
    該分詞詞典機(jī)制適用于正向最大匹配算法和逆向最大匹配算法,，本文采用正向最大匹配算法為例使用該詞典機(jī)制進(jìn)行分詞,。
    第一步：取待匹配字符串
    假設(shè)String為待分詞語句，如果String不包含任何字符(即長度為零),，則表示語句分詞完畢,。從String=A1A2A3A4…An中讀取第一個(gè)字A1，從首字哈希表中獲取以該字為首字的最長詞的字?jǐn)?shù)m,，如果String剩余待分詞的字?jǐn)?shù)不足m,，則取Str為String的剩余待分詞的字符串，否則取字符串Str=A1A2…Am為待匹配字符串,。
    第二步：判斷Str的長度
    (1)如果Str的長度為1,，在首字哈希表中找到對應(yīng)的位置，判斷單獨(dú)成詞標(biāo)志是否為F,，如果是說明Str不是一個(gè)詞,；否則說明Str是一個(gè)詞,，分出該詞。設(shè)置待切分語句String=A2A3A4…An后轉(zhuǎn)第一步,。
    (2)如果Str的長度大于1,，轉(zhuǎn)第三步。
    第三步：對待匹配字符串分詞
    在A1對應(yīng)的哈希節(jié)點(diǎn)鏈表中查找詞長為字串Str長度的節(jié)點(diǎn),，有如下兩種情況：
    (1)如果沒有找到,，則Str字串不是一個(gè)詞，則去掉Str的最后面的一個(gè)字,，轉(zhuǎn)第二步,。
    (2)如果找到對應(yīng)的哈希節(jié)點(diǎn)，則計(jì)算Str(除去首字,，因?yàn)槭鬃植槐４?的哈希值,，得到在詞哈希表中的位置，有如下三種情況：
    ①若對應(yīng)的碰撞數(shù)(iNum)等于0,，說明Str不是一個(gè)詞,。
    ②若對應(yīng)的碰撞數(shù)(iNum)等于1，則比較去掉首字的Str與詞碰撞表中的詞,，如果相等,，則Str成詞，否則不成詞,。
    ③若對應(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,。對3個(gè)分詞器ChineseAnalyzer、CJKAnalyzer,、MyAnalyzer進(jìn)行實(shí)驗(yàn),，采用復(fù)合索引結(jié)構(gòu)，只對文檔內(nèi)容創(chuàng)建域,，且只對文檔內(nèi)容進(jìn)行索引但不存儲(chǔ),，在分詞時(shí)間,、索引文件大小兩方面做對比，分別對兩個(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)測試文檔集增大時(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ā)者可以針對系統(tǒng)的特點(diǎn)定制自己的分詞詞典,，根據(jù)具體的需求進(jìn)行分詞,，并創(chuàng)建索引，從而提高全文檢索的效率,。
參考文獻(xiàn)
[1] 胡長春,，劉功申.面向搜索引擎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.