基于雙哈希結(jié)構(gòu)的整詞二分詞典機(jī)制

張賢坤，李亞南，田 雪

（天津科技大學(xué) 計算機(jī)科學(xué)與信息工程學(xué)院，天津300222）

0 引 言

中文分詞技術(shù)在信息檢索、問答系統(tǒng)、文本挖掘等很多方面都有應(yīng)用［1］，其運行速度直接影響了后續(xù)處理的效率。機(jī)械分詞是一類相對成熟的分詞方法，該類方法實現(xiàn)和維護(hù)簡單，準(zhǔn)確率較高，新詞識別能力卻很低。目前，機(jī)械分詞已發(fā)展成為一類重要的輔助方法，一般與其它方法結(jié)合使用［2］。分詞詞典是機(jī)械分詞方法的基本構(gòu)件，其查詢速度直接影響著分詞算法的性能［3］。傳統(tǒng)的分詞詞典機(jī)制有整詞二分、TRIE索引樹和逐字二分。整詞二分機(jī)制結(jié)構(gòu)簡單，內(nèi)存使用較少，實施簡單；TRIE樹機(jī)制效率較高，但空間占用大，詞典的構(gòu)造、維護(hù)都相對困難；逐字二分機(jī)制是前二者的改進(jìn)版，內(nèi)存占用較小、查詢速度較快，由于受到存儲結(jié)構(gòu)的影響，其性能很難再提高［4］。整詞二分詞典機(jī)制擁有簡單易行的特點，較其它2種有很大的性能提升空間，本文將對該詞典機(jī)制進(jìn)行改進(jìn)。

逆向最大匹配 （reverse maximum matching，RMM）算法和正向最大匹配 （forward maximum matching，F(xiàn)MM）算法是機(jī)械分詞方法中2個主要算法。其中，RMM 的分詞精度比FMM 高［5］，使用時會根據(jù)需要選擇算法，對2 種算法的研究同等重要。但是，傳統(tǒng)的整詞二分詞典機(jī)制以詞條首字作為索引項，對逆向掃描的RMM 不適用；該詞典機(jī)制匹配詞串時存在無效匹配次數(shù)過多，索引效率很低等問題。針對這些問題，本文提出了雙哈希尾字詞典結(jié)構(gòu)，能夠?qū)MM 的分詞速率提高近一倍。

1 已有的詞典機(jī)制

分詞使用的詞典由外部存儲器調(diào)入內(nèi)存，包含了大量供匹配的漢語詞，詞典規(guī)模較大，時間和空間的開銷都很大。詞查詢速度、空間利用率和維護(hù)這3個要素可以限制詞典的性能。丁振國［5］改進(jìn)了整詞二分詞典結(jié)構(gòu)，提出了哈希結(jié)構(gòu)的分詞詞典，該詞典中記錄了首字下最大詞長，同時為每一個長度的詞條給出了索引指針，速率相對于原整詞二分詞典結(jié)構(gòu)有所提高。彭煥峰［6］提出了一種基于全哈希的整詞二分詞典結(jié)構(gòu)，將詞條按字?jǐn)?shù)存儲，進(jìn)行全詞哈希，減少了詞條匹配的次數(shù)，使用該詞典進(jìn)行分詞擁有較高的效率。葉繼平［7］利用哈希表提出了具有三級索引的新詞典結(jié)構(gòu)，并給出了對應(yīng)的最大正向匹配的改進(jìn)算法，降低了匹配過程的時間復(fù)雜度，提高了分詞算法的速率。莫建文［8］構(gòu)造了雙字哈希結(jié)構(gòu)，不但對詞條的首字進(jìn)行哈希查找，對于詞語的次字也采用查找哈希，實驗表明采用該詞典機(jī)制的分詞速度有一定的提高。

1.1 傳統(tǒng)的整詞二分詞典結(jié)構(gòu)

傳統(tǒng)的整詞二分詞典結(jié)構(gòu)［4］如圖1 所示。該詞典結(jié)構(gòu)包括詞典正文、詞索引表和首字哈希表組成。詞典正文是存儲詞條的有序表，詞索引表是指向詞典正文中每個詞條的指針表。通過首字哈希表的哈希定位和詞索引表可以輕易確定某個詞條在詞典正文中的可能位置范圍［7］。

該詞典結(jié)構(gòu)有以下三點不足：①第一層哈希表保存了所有詞條的首字，在分詞過程中，以首字表為入口，得到詞典正文的索引指針，進(jìn)而進(jìn)行詞條檢索。但是，對于逆向最大匹配算法來說，在對某字符串檢索失敗時，會將第一個漢字去掉，再對余下的字符串進(jìn)行檢索，這時，就不得不重新檢索首字哈希表，若是仍然檢索失敗會繼續(xù)刪除為首的漢字，檢索哈希表，直至分詞結(jié)束［9］。②在傳統(tǒng)的機(jī)械分詞算法中，匹配字符的最大長度一般設(shè)置為詞表中詞的最大詞長。但是，據(jù)統(tǒng)計，漢語中詞的出現(xiàn)頻率較高的主要是二 字詞，其次是三字詞和四字詞，更長的詞的出現(xiàn)頻率非常低［10］，而大多數(shù)詞表中的最大詞長至少為5，因此這種字符串長度的選擇的方法增加了算法無效匹配的次數(shù)［9］。③詞典正文以有序表進(jìn)行存儲，檢索速度很慢。

1.2 記錄詞長的哈希結(jié)構(gòu)尾字詞典結(jié)構(gòu)

針對傳統(tǒng)的整詞二分詞典結(jié)構(gòu)在用于逆向最大匹配算法時出現(xiàn)的問題，文獻(xiàn) ［9］對上述詞典結(jié)構(gòu)做出了改進(jìn)，提出了記錄詞長的哈希結(jié)構(gòu)尾字詞典，如圖2所示。該詞典由三部分組成：

圖1 整詞二分詞典結(jié)構(gòu)

圖2 記錄詞長的哈希結(jié)構(gòu)尾字詞典結(jié)構(gòu)

（1）記錄詞長的尾字哈希表

每個詞條的尾字哈希表都包含其尾字下的最大詞長，和指向以該漢字C為詞尾的詞條在詞匯索引表中的初始位置的指針。

（2）詞匯索引表

表中每條記錄包含一個指向詞典正文中對應(yīng)詞匯首地址的指針，和一個記錄詞典正文中除去尾字的詞條長度。詞匯索引項按各詞詞長進(jìn)行降序排列。

（3）詞典正文

詞典正文為以字C 作為詞尾的所有詞條的有序表，依序存儲各詞條中不包含尾字C的剩余漢字。

該詞典結(jié)構(gòu)的優(yōu)勢：①在哈希表中保存了詞條的尾字，以尾字作為檢索入口，在逆向匹配算法分詞的過程中，只須檢索哈希表一次，節(jié)省了時間。②為每一個尾字保存了以該字結(jié)尾的詞條的最大長度，這樣，在字符串長度選擇時，可以以該值作為基準(zhǔn)，減少了無效匹配次數(shù)。③在詞典正文中，只保存不包含尾字的剩余漢字，節(jié)省了空間。④為不同長度的詞條分別設(shè)立了索引，在一定程度上節(jié)省了檢索時間。

該結(jié)構(gòu)有兩點不足。第一，文獻(xiàn) ［9］提出的詞典結(jié)構(gòu)，解決了傳統(tǒng)的整詞二分詞典結(jié)構(gòu)在逆向匹配算法中的不適用問題。但是詞典正文仍然使用有序表存儲，雖然為不同長度的詞條分別設(shè)立了索引，但是有序表是不適合用于檢索數(shù)據(jù)的，若是相同長度的詞條非常多，在檢索時非常耗時。在3.1節(jié)中，將會對該詞典結(jié)構(gòu)和傳統(tǒng)的整詞二分詞典結(jié)構(gòu)的性能進(jìn)行分析，有分析結(jié)果可知，在最壞情況下，2種詞典結(jié)構(gòu)匹配同一個漢字串的時間復(fù)雜度是同階的。所以該尾字詞典結(jié)構(gòu)對提高分詞算法速率的意義并不是很大。第二，該詞典的實現(xiàn)比較復(fù)雜。

上述尾字詞典使用有序表存儲詞條，影響了詞典的性能，本文在該詞典結(jié)構(gòu)的基礎(chǔ)上，改進(jìn)了詞典正文的存儲結(jié)構(gòu)，提出了雙哈希結(jié)構(gòu)尾字詞典。

2 雙哈希結(jié)構(gòu)尾字詞典

2.1 詞典設(shè)計

雙哈希結(jié)構(gòu)尾字詞典的詞典結(jié)構(gòu)如圖3所示。詞典由2個部分組成：記錄詞長的尾字哈希表和詞典哈希表，哈希函數(shù)均由國際區(qū)位碼得出。

圖3 雙哈希結(jié)構(gòu)尾字詞典

（1）記錄詞長的尾字哈希表

每個詞條的尾字哈希表都包含其尾字下的最大詞長，和指向以該漢字C為詞尾的所有詞條組成的哈希表的指針。

（2）詞典哈希表

以哈希表存儲數(shù)據(jù)。以字C 結(jié)尾的所有詞條都作為哈希表的健存儲在哈希表中，對應(yīng)的值都是一個常數(shù)，在算法中不會被使用。

該詞典使用了哈希表存儲詞典正文，而不再使用有序表，避免了有序表不適合檢索數(shù)據(jù)的問題，同時，因為哈希表是通過哈希值直接定位數(shù)據(jù)的，檢索速度非常快。由于只使用兩層哈希表存儲數(shù)據(jù)，詞典的實施和維護(hù)以及添加、刪除數(shù)據(jù)都非常簡單方便。

在加載詞典時，對于詞長為1的詞并不加載到詞表中，原因是如果一個字并不和其他字組成詞，或者沒有一個詞條以該字作為詞尾，那么在分詞過程中，如果一個匹配字符串是以該字作為結(jié)尾，是無需在詞典哈希表中進(jìn)行檢索的。所以，不需要為該字分配尾字哈希表位置。該詞典機(jī)制提高了空間利用率，避免了無效的存儲造成的空間浪費。

2.2 分詞算法

在算法調(diào)用前，需要對待切分文本進(jìn)行預(yù)處理，包括去除停用詞和對數(shù)字、字母等的處理。雙哈希結(jié)構(gòu)尾字詞典對應(yīng)的逆向最大匹配算法流程圖如圖4所示，對應(yīng)算法見算法1。

算法1：

（1）待分詞字串S＝C1C2…Cn （n∈N），S 長度為Length，若Length＝0，算法結(jié)束；若Length＞1，轉(zhuǎn)向（2）；否則將Cn作為單字詞，切分出去，算法結(jié)束；

（2）判斷外層哈希表中是否存在鍵Cn，若存在，則轉(zhuǎn)向 （4）；不存在轉(zhuǎn)向 （3）；

（3）將Cn作為單字詞，切分出去，若length＞0，剩下字串作為新的S字串，轉(zhuǎn)向 （1）；否則算法結(jié)束；

（4）檢索外層哈希表得到以Cn 為鍵的鍵值對End－Char，由EndChar得到以Cn 為詞尾的最大詞長Lm，若Length≥Lm，則令L＝Lm；若Length＜Lm，則令L＝Length；

（5）取S 字串的最末L 個字串得到S （L），以End－Char為入口，查詢內(nèi)層哈希表，判斷S （L）是否匹配詞典中的詞條；若不匹配，轉(zhuǎn)向 （7）；若匹配則繼續(xù)；

（6）將字串S （L）作為一個詞切分出去，Length＝Length－L；若length＞0，剩下字串作為新的S字串，轉(zhuǎn)向 （1）；否則算法結(jié)束；

（7）L＝L－1，若L＞1轉(zhuǎn)向（5）；若L＝1，將Cn作為單字詞，切分出去，剩下字串作為新的S字串，轉(zhuǎn)向（1）。

圖4 算法流程

3 性能分析與實驗

3.1 詞典性能分析

假設(shè)待匹配字串為S＝C1C2…Cn （n∈N），S 長度為n，假設(shè)以Cx 為首字的詞條數(shù)目為mx（x＝1，2…，n），令m 等于mx最大值；以Cn為尾字的詞條數(shù)目為g。則在3種詞典數(shù)據(jù)結(jié)構(gòu)下對該字串進(jìn)行逆向最大匹配分詞，且分出一個詞的時間復(fù)雜度如下：

（1）傳統(tǒng)的整詞二分詞典結(jié)構(gòu)

訪問首字哈希表的時間復(fù)雜度為O（1），在詞典正文中二分查找該詞條的時間復(fù)雜度為O（m1）。最壞情況下進(jìn)行n次查找和匹配，所以分詞的時間復(fù)雜度為：O（n）＋O（nm）≈O（nm）。

（2）記錄詞長的哈希結(jié)構(gòu)尾字詞典

訪問尾字哈希表的時間復(fù)雜度為O（1），在詞匯索引表中查找到詞典正文中詞長為n 的指針的時間復(fù)雜度為O（1），最壞情況下，所有以Cn為尾字的詞條具有相同長度，則在詞典正文中匹配該字串的時間復(fù)雜度為O（g）。在最壞情況下，值訪問尾字哈希表一次，要在詞典正文中匹配n－1次，分詞時間復(fù)雜度為：2O（1）＋O（（n－1）g）≈O（ng）。

（3）雙哈希結(jié)構(gòu)尾字詞典

訪問外層尾字哈希表的時間復(fù)雜度為O（1）。由于不包含重復(fù)的詞條，沒有再哈希現(xiàn)象，所以在內(nèi)層哈希表詞典正文中索引字串的時間復(fù)雜度為O（1）。在最壞情況下，值訪問外層哈希表一次，需要索引內(nèi)層哈希表n－1次，分詞的時間復(fù)雜度為O（1）＋O（n－1）≈O（n）。

因為O（ng）≈O（nm），所以記錄詞長的哈希結(jié)構(gòu)尾字詞典時間復(fù)雜度稍低于傳統(tǒng)的整詞二分詞典結(jié)構(gòu)，二者時間復(fù)雜度同階；又因為g 值遠(yuǎn)大于n 值，所以O(shè)（n）遠(yuǎn)小于O（ng），所以雙哈希結(jié)構(gòu)尾字詞典的時間復(fù)雜度最低。

通過上述分析可知，前2種詞典結(jié)構(gòu)均需對有序表進(jìn)行順序匹配，詞典中詞條數(shù)目對匹配的效率影響很大；而本文提出的雙哈希結(jié)構(gòu)尾字詞典完全利用了哈希表的快速查找優(yōu)勢，降低了查找的時間復(fù)雜度。根據(jù)分析也可以看出，雙哈希結(jié)構(gòu)尾字詞典的使用和維護(hù)都比其它2 種詞典簡單。

3.2 實驗結(jié)果分析

本文實驗的語料是1998 年1 月的人民日報分詞語料（北大語料），分成四份 （Data1，Data2，Data3，Data4）分別進(jìn)行分詞實驗，實驗中采用的詞典共104951個詞條。對每個語料分別使用本文提出的雙哈希結(jié)構(gòu)尾字詞典、文獻(xiàn)［9］提出的記錄詞長的哈希結(jié)構(gòu)尾字詞典和傳統(tǒng)的整詞二分詞典進(jìn)行逆向最大匹配分詞實驗，上述3種詞典依次命名為dic1、dic2和dic3。對于dic3使用傳統(tǒng)的逆向匹配算法；由于dic2 和dic1 均為尾字詞典，可用同一種調(diào)用策略，為了客觀地進(jìn)行比較，對這2種詞典結(jié)構(gòu)都使用上一節(jié)提到的算法1進(jìn)行實驗。

每個語料進(jìn)行10次實驗，計算平均時間。實驗語料大小見表1，語料大小單位是字節(jié) （b）。分詞結(jié)果統(tǒng)計如表2所示，時間單位是毫秒 （ms），平均速率單位是字節(jié)／毫秒（b／ms）。評估分詞結(jié)果好壞程度的標(biāo)準(zhǔn)是準(zhǔn)確率P 與召回率R 的調(diào)和平均值F［11］，F(xiàn)＝2RP／ （R＋P），其中準(zhǔn)確率是分詞的結(jié)果集中正確切分的詞數(shù)占分詞結(jié)果總詞數(shù)的比例，召回率是分詞結(jié)果中正確切分的詞數(shù)占標(biāo)準(zhǔn)答案中總詞數(shù)的比例。根據(jù)表1和表2得到3種詞典的分詞速率如圖5所示。

由圖5可以看出，在不降低分詞結(jié)果F值的條件下，2種使用尾字詞典 （dic1 和dic2）的逆向最大匹配分詞算法明顯比使用傳統(tǒng)的整詞二分詞典的逆向匹配算法分詞效率高，分詞速率比較穩(wěn)定。使用本文提出的雙哈希結(jié)構(gòu)詞典的分詞速率較使用文獻(xiàn) ［9］提出的尾字詞典結(jié)構(gòu)有很大的提高，并且相對于使用傳統(tǒng)的整詞二分詞典結(jié)構(gòu)的算法速率提高了將近一倍。

表1 實驗語料

表2 分詞結(jié)果統(tǒng)計

圖5 分詞速率比較

4 結(jié)束語

本文介紹了傳統(tǒng)的整詞二分詞典結(jié)構(gòu)和文獻(xiàn) ［9］提出的記錄詞長的尾字詞典，對這2種詞典結(jié)構(gòu)做出了全面的分析，指出了二者的不足，并提出了雙哈希結(jié)構(gòu)詞典和其對應(yīng)的逆向最大匹配分詞算法。實驗證明，本文提出的算法在不降低分詞結(jié)果F 值的條件，很大程度上提高了分詞算法的性能。

本文只對詞典機(jī)制做了改進(jìn)，對于逆向最大匹配算法的分詞歧義問題并沒有給出解決辦法，下一步的工作是提出一種有效解決分詞歧義的算法，結(jié)合本文提出的詞典機(jī)制，進(jìn)一步提高分詞算法的分析效率。

［1］Fu Guohong，Chunyu Kit，Jonathan J Webster.Chinese word segmentation as morpheme－based lexical chunking ［J］.Information Sciences，2008，178 （9）：2282－2296.

［2］FENG Guohe，ZHENG Wei.Review of Chinese automatic word segmentation ［J］.Library and Information Service，2011，55（2）：41－45（in Chinese）.［奉國和，鄭偉.國內(nèi)中文自動分詞技術(shù)研究綜述［J］.圖書情報工作，2011，55 （2）：41－45.］

［3］CHEN Ping，LIU Xiaoxia，LI Yajun.Chinese word segmentation based on dictionary and statistic ［J］.Computer Engineering and Applications，2008，44 （10）：144－146 （in Chinese）.［陳平，劉曉霞，李亞軍.基于字典和統(tǒng)計的分詞方法 ［J］.計算機(jī)工程與應(yīng)用，2008，44 （10）：144－146.］

［4］ZHOU Chengyuan，ZHU Min，YANG Yun.Research on Chinese word segmentation algorithm based on the dictionary ［J］.Computer ＆ Digital Engineering，2009，37 （3）：68－71 （in Chinese）.［周程遠(yuǎn)，朱敏，楊云.基于詞典的中文分詞算法研究 ［J］.計算機(jī)與數(shù)字工程，2009，37 （3）：68－71.］

［5］DING Zhenguo，ZHANG Zhuo，LI Jing.Improvement on reverse directional maximum matching method based on hash structure for Chinese word segmentation ［J］.Computer Engineering and Design，2008，29 （12）：3208－3211（in Chinese）.［丁振國，張卓，黎靖.基于Hash結(jié)構(gòu)的逆向最大匹配分詞算法的改進(jìn) ［J］.計算機(jī)工程與設(shè)計，2008，29 （12）：3208－3211.］

［6］PENG Huanfeng，DING Songtao.Binary－seek－by－word dictionary mechanism based on all－Hash ［J］.Computer Engineering，2011，37 （21）：40－42 （in Chinese）. ［彭煥峰，丁宋濤.一種基于全Hash的整詞二分詞典制 ［J］.計算機(jī)工程，2011，37 （21）：40－42.］

［7］YE Jiping，ZHANG Guizhu.Research and improvement of Chinese word segmentation dictionary ［J］.Computer Engineering and Applications，2012，48 （23）：139－142 （in Chinese）. ［葉繼平，張桂珠.中文分詞詞典結(jié)構(gòu)的研究與改進(jìn)［J］.計算機(jī)工程與應(yīng)用，2012，48 （23）：139－142.］

［8］MO Jianwen，ZHENG Yang，SHOU Zhaoyu，et al.Improved Chinese word segmentation method based on dictionary［J］.Computer Engineering and Design，2013，34 （5）：1802－1807（in Chinese）.［莫建文，鄭陽，首照宇，等.改進(jìn)的基于詞典的中文分詞方法［J］.計算機(jī)工程與設(shè)計，2013，34 （5）：1802－1807.］

［9］LIANG Zhen，LI Yusheng.Reverse backtracking research of Chinese segmentation based on dictionary of Hash structure［J］.Computer Engineering and Design，2010，31 （23）：5158－5161 （in Chinese）.［梁楨，李禹生.基于Hash結(jié)構(gòu)詞典的逆向回溯中文分詞技術(shù)研究 ［J］.計算機(jī)工程與設(shè)計，2010，31 （23）：5158－5161.］

［10］WANG Ruilei，LUAN Jing，PAN Xiaohua，et al.An improved word maximum matching algorithm for Chinese word segmentation ［J］.Computer Applications and Soft Ware，2011，28 （3）：195－197 （in Chinese）. ［王瑞雷，欒靜，潘曉花，等.一種改進(jìn)的中文分詞正向最大匹配算法 ［J］.計算機(jī)應(yīng)用與軟件，2011，28 （3）：195－197.］

［11］HUANG Changning，ZHAO Hai.Chinese word segmentation：A decade review ［J］.Journal of Chinese Information Processing，2007，21 （3）：8－19 （in Chinese）.［黃昌寧，趙海.中文分詞十年回顧 ［J］.中文信息學(xué)報，2007，21 （3）：8－19.］