摘  要： 針對(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簡介
    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)碼獲取漢字對(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ù)。
    最長詞字?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)等信息。對(duì)相同首字的詞條按包含的字?jǐn)?shù)進(jìn)行分組，再對(duì)除首字外的剩余字符串進(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ù)組，對(duì)于詞典中首字相同且詞長相同的詞條，如果哈希值相同，則以動(dòng)態(tài)數(shù)組的形式保存，且只保存除首字之外的剩余字串。對(duì)于哈希值相同的詞條，采用二分查找。
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，在首字哈希表中找到對(duì)應(yīng)的位置，判斷單獨(dú)成詞標(biāo)志是否為F，如果是說明Str不是一個(gè)詞；否則說明Str是一個(gè)詞，分出該詞。設(shè)置待切分語句String=A2A3A4…An后轉(zhuǎn)第一步。
    (2)如果Str的長度大于1，轉(zhuǎn)第三步。
    第三步：對(duì)待匹配字符串分詞
    在A1對(duì)應(yīng)的哈希節(jié)點(diǎn)鏈表中查找詞長為字串Str長度的節(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)測試文檔集增大時(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] 胡長春，劉功申.面向搜索引擎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.