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

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

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

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