彭煥峰

(南京工程學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 南京211167)

信息技術(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ì)如下：

詞個(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ù)。

表1 不同分詞器實(shí)驗(yàn)數(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)建索引，從而提高全文檢索的效率。

[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.