劉 勇，魏光澤

（青島科技大學 山東 青島 266061）

基于雙字哈希結(jié)構(gòu)的最大匹配算法機制改進

劉 勇，魏光澤

（青島科技大學 山東 青島 266061）

中文分詞是計算機進行文本分析的關(guān)鍵技術(shù)。基于提高分詞效率以滿足日益增長的文本分析需求，通過分析常用的基于詞典的機械分詞算法與詞典機制的優(yōu)缺點，在對最大匹配算法進行改進的同時，采用雙字哈希詞典設(shè)計了適合此算法的雙字哈希余字分組的詞典結(jié)構(gòu)，提出了基于雙字哈希結(jié)構(gòu)的最大匹配改進算法。該算法在保證原最大匹配算法分詞精度的前提下，大大提高了分詞速度。經(jīng)實驗證明，改進后的算法性能明顯提升。

中文分詞；最大正向匹配算法；詞典；哈希結(jié)構(gòu)；哈希函數(shù)

中文分詞[1]技術(shù)是中文信息處理最基礎(chǔ)、最核心的技術(shù)。該技術(shù)在搜索引擎、檢索翻譯、智能輸入法等多個領(lǐng)域廣泛應(yīng)用且擔綱重任，任何中文語言處理應(yīng)用都需要中文分詞，其性能優(yōu)劣對中文信息處理尤為重要[2-3]?？焖?、準確的進行中文分詞被越來越多的人關(guān)注和研究。

中文與英文不同，英文單詞與單詞直接有空格劃界，分詞相對容易。而中文句子中是連續(xù)的漢字串，詞與詞之間沒有分隔符，機械分詞困難得多，必須借助復雜的分詞算法將詞語分隔開[4]。目前中文分詞算法大致可以分為基于詞典的機械分詞算法、基于統(tǒng)計的分詞算法和基于理解的分詞算法3種[5]，其中基于詞典的機械分詞算法最為常用。

基于詞典的機械分詞方法按照掃描方向的不同，可分為正向匹配算法和逆向匹配算法；按照不同長度優(yōu)先匹配的方式，可分為最大匹配算法和最小匹配算法。其中占主流地位的分詞方法是正向最大匹配算法和逆向最大匹配算法[6]。對于基于詞典的機械分詞算法，分詞速度除跟算法本身的運行流程有關(guān)系外，合適的詞典結(jié)構(gòu)也對效率有舉足輕重的作用。機械分詞算法與分詞詞典的有效配合才能保證良好的分詞性能。

文中以最大正向匹配算法為例，通過針對待匹配文本首字合理設(shè)置初始最大詞長及根據(jù)詞典中以某字為首字的詞長序列逐次更改匹配長度，對算法流程加以優(yōu)化。并根據(jù)改進算法設(shè)計雙字哈希余字分組的詞典結(jié)構(gòu)，明顯改進了原算法的性能。最大逆向匹配算法改進途徑與之相通，只需設(shè)計相應(yīng)逆序詞典即可，文中不再贅述。

1 最大正向匹配算法分析

最大正向匹配算法FMM（Forward Maximum Matching method）遵循“長詞優(yōu)先”原則[7]，定義如下：假設(shè)一個已知詞典中，最長的詞條有m個漢字，則截取待匹配文本中前m個字作為匹配字段與分詞詞典進行匹配。若詞典中存在該詞則匹配成功，將匹配字段切分出去，然后從切分出去的字符串的下一字開始在待匹配文本中再取前m個字作為匹配字段重新與詞典匹配。若匹配不成功，則去掉待匹配字符串的最后一個字，用剩下的m-1個字組成的字符串與分詞詞典進行匹配，直到匹配成功為止。

通過對最大正向匹配算法分析可知其存在以下不足[8]：

1）在最大匹配算法中，匹配的初始最大詞長是所用詞典中最長詞的詞長。而根據(jù)文獻[9]統(tǒng)計，漢字詞中二字詞占比最多，三字詞、四字詞較多，五字以上詞所占比例很少，這樣在匹配較短詞語時，會造成多次無意義的匹配循環(huán)，極大的增加了時間和空間開銷。

2）因匹配失敗而對最大詞長進行更改時，逐一遞減的方式會產(chǎn)生多次無效循環(huán)影響效率。以使用最大正向匹配算法切分“中文與英文不同”為例，切分結(jié)果為“中文/與/英文/不同”，假設(shè)詞典中最長詞長度為7，則初始匹配長度為7，顯然切分結(jié)果中并無7字詞，程序需進行多次無意義匹配才能匹配成功。且詞典中以“與”為首字并無長度為6、5、4的詞，匹配詞長逐一遞減的方式也造成了時間浪費。

基于最大匹配算法的傳統(tǒng)中文分詞詞典機制主要有以下4種：基于整詞二分、Trie索引樹、逐字二分和雙字哈希[5]。文獻[10]提出了一種改進整詞二分法的詞典機制。該詞典將以某字為首字的詞按詞長分組，匹配時只需在對應(yīng)詞長的組內(nèi)進行二分查找，通過縮小查找范圍提高分詞效率。文獻[11]根據(jù)中文詞單字詞和二字詞占絕大多數(shù)的特點，設(shè)計了雙字哈希的詞典結(jié)構(gòu)。該結(jié)構(gòu)與首字哈希詞典結(jié)構(gòu)相比，可更快速的搜索詞語，大大提高了分詞效率。文獻[12]基于最大逆向匹配算法，設(shè)計記錄詞長的雙哈希結(jié)構(gòu)尾字詞典，有效降低了詞條匹配時間復雜度。文獻[13]提出一種基于多層哈希的詞典機制，并在首字哈希后標記對應(yīng)詞條長度；文獻[14]提出一種基于全哈希的整詞二分詞典機制；文獻[15]提出了一種具有三級索引的新詞典結(jié)構(gòu)。以上改進的詞典結(jié)構(gòu)都在一定程度上加快了分詞速度。

2 算法改進及詞典設(shè)計

2.1 最大正向匹配算法的改進

針對最大正向匹配算法的不足，若根據(jù)當前待匹配字符串的首字確定合適的最大詞長，且當匹配失敗時根據(jù)詞典中以該字為首字的詞詞長遞減設(shè)置下一待匹配字符串長度，該算法的效率會提高很多。改進如下：

1）根據(jù)在詞典中以當前待匹配字符串首字為詞的詞長度m與待匹配文本長度s做比較，選擇不大于s的m值作為初始最大詞長，其中s根據(jù)程序運行階段動態(tài)變化（初始值為待匹配文本長度，每切分成功一次對應(yīng)減?。?/p>

2）當匹配失敗需對最大詞長m進行更改時，選擇在詞典中以當前待匹配字符串首字為詞的下一最大詞長度對m重新賦值。假設(shè)初始待匹配文本長度為12，當前已切分字符串長度為6，詞典中以當前待匹配字符串首字為首字的詞長序列為7、5、3，則當前待匹配字符串長度s為6，根據(jù)當前待匹配字符串首字設(shè)置的初始最大詞長為5，當5字詞匹配不成功時，直接選擇3字詞繼續(xù)進行匹配。

2.2 基于改進算法設(shè)計詞典

傳統(tǒng)的漢字分詞詞典中，詞長以2為主，且普遍存在不定長的現(xiàn)象。選用文獻[16]對人民日報語料庫進行的統(tǒng)計和分析可知，二字詞所占比例很大，使用頻率很高，四字以上多字詞詞語占比較低，使用頻率也較低。統(tǒng)計與分析如表1所示。

漢字在計算機內(nèi)以內(nèi)碼的形式進行存儲[17]，通過哈希函數(shù)可以快速的定位漢字。基于漢字詞中二字詞所占比例較大，為了提高詞典中詞條的查找速度，本文選用雙字哈希的詞典機制，并根據(jù)算法需求加以優(yōu)化。該機制吸納了“整詞二分”和“TRIE索引樹”的優(yōu)點，只對詞條的前兩個字建立Hash索引，構(gòu)成深度為2的TRIE子樹，而詞的剩余字串則按詞長降序排列組成詞典正文，這樣既可以提高匹配效率又可以兼顧空間利用率。

表1 人民日報語料庫詞語統(tǒng)計信息

為進一步提高查詢效率，詞典采用分組思想，將首字、次字相同的所有詞條按照不同的詞長進行分組，且標記長度。這樣情況下最小組是首字、次字相同且詞長相同的詞條集合，查找范圍更加小的同時滿足了算法動態(tài)選擇最大詞長的要求。改進后的詞典結(jié)構(gòu)如圖1所示。

圖1 改進的詞典機構(gòu)圖

由圖可知，改進的詞典結(jié)構(gòu)分為4部分：首字哈希表、次字哈希表、詞長索引表、詞典正文。

1）首字哈希表。由散列表的關(guān)鍵字及次字哈希指針構(gòu)成，用于確定詞語首字的具體位置。

漢字在計算機中以內(nèi)碼形式存在，將內(nèi)碼計算后轉(zhuǎn)為為區(qū)位碼，再將區(qū)位碼轉(zhuǎn)換為一個十進制的數(shù)字，這個數(shù)字就是該漢字在哈希表中的序號。該序號指示了以該字為首字的詞的詞長表的入口地址。根據(jù)Hash函數(shù)[18]，入口地址的計算，如公式（1）所示。

其中，Offset為該字在哈希表中的序號，ch1、ch2分別為該字機內(nèi)碼的高字節(jié)和低字節(jié)。

2）次字哈希表。包括關(guān)鍵字、是否能與首字組合成詞、以此首字次字開頭的詞長索引指針3部分。

3）詞長索引表。對應(yīng)以前述二字開頭的詞的剩余部分，包括以前述二字開頭的詞的長度及該長度詞集合構(gòu)成的詞典正文指針兩部分。

4）詞典正文。順序存儲某長度詞語除首字、次字外的剩余部分。

該詞典采用了雙字哈希的結(jié)構(gòu)。為適應(yīng)改進的算法需求，詞典在兩層哈希結(jié)構(gòu)后增加了詞長索引表，滿足了最大匹配算法更合理的選取最大詞長的需求，同時根據(jù)詞長對詞語進行了恰當?shù)姆纸M，使匹配的范圍進一步縮小，大大降低了算法的時間開銷。

3 改進后的算法及改進機制分析

3.1 最大正向匹配算法的改進

3.1.1 初始最大詞長選擇

對于每一個待匹配字符串首字設(shè)置初始最大詞長時，首先計算當前待匹配字符串長度s，然后將詞典中以該字為首字的所有詞長從大到小依次與s比較，直到得到不大于s的最大詞長m，以m作為當前狀態(tài)的初始最大詞長。本文采用雙字哈希的詞典結(jié)構(gòu)，所用詞典詞詞長索引表中標記的最小詞長為3。

3.1.2 算法描述

改進后的算法流程圖，如圖2所示。

假設(shè)待匹配字符串Str=W1W2…WiWi+1…Wn（i，n∈N），

1）待匹配字符串首字為Wi，字符串的長度s=ni+1，若 s=1，切出 Wn結(jié)束循環(huán)；否則轉(zhuǎn) 2）。

2）計算Wi的哈希值，確定其在哈希表中的位置。在以Wi為首字指向的次字哈希表中確定Wi+1的位置，若存在 Wi+1，則轉(zhuǎn)向 3），否則進入 5）。

3）計算以Wi Wi+1為首二字對應(yīng)的詞長序列表中的最大值 m（3＜=m＜=s）作為初始匹配長度，轉(zhuǎn) 4）；若不存在m轉(zhuǎn)7）。

4）當前選擇匹配的字符串為Wi Wi+1…Wi+m-1，取除Wi Wi+1外的剩余字符串與m對應(yīng)的詞典正文進行匹配，若匹配成功則切出Wi Wi+1…Wi+m-1，i=i+m 轉(zhuǎn)向 1）；否則轉(zhuǎn)向 6）。

5）從 Str中切出 Wi，若 i+1=n，則切出 Wn結(jié)束循環(huán)；否則 i=i+1，進入 1）。

6）設(shè)k為以Wi Wi+1為首二字對應(yīng)的詞長序列表中的最小值，若m＞k，取詞長序列表中小于當前m的最大值重新賦值轉(zhuǎn)m并轉(zhuǎn)4）；否則轉(zhuǎn)7）。

7）判斷Wi Wi+1是否成詞，若成詞則切出Wi Wi+1，i=i+2 轉(zhuǎn)向 1），否則轉(zhuǎn) 5）。

圖2 改進的最大匹配算法流程圖

3.2 改進機制分析

文中對最大正向匹配算法進行了兩處優(yōu)化：1）是根據(jù)不同首字設(shè)置恰當?shù)某跏甲畲笤~長；2）是在當前最大詞長匹配失敗時動態(tài)的獲得下次匹配的最大詞長。

根據(jù)算法要求采用雙字哈希結(jié)構(gòu)的分詞詞典并加以改進。查找某個詞語時，首先根據(jù)哈希函數(shù)對首字進行查找，而后哈希查找次字，然后獲得以該二字開頭對應(yīng)的詞長序列表，最后在某詞長組內(nèi)查找剩余部分。在匹配過程中，上一步能否成功與下一步是否進行緊密關(guān)聯(lián)，若前一步匹配不成功，則查找停止，系統(tǒng)重新進行新的查找。

如此設(shè)計的查找方式可以快速的定位待查找的內(nèi)容并進行比較，大大減少了無效流程，提高了分詞效率。

4 實驗結(jié)果

分別使用基于整詞二分的分詞詞典機制、基于逐字二分的分詞詞典機制、基于Trie索引樹的分詞詞典機制和本文設(shè)計的雙子哈希余字分組的詞典機制四種詞典機制對不同類型的測試文本進行若干組實驗，每組實驗采用相同的測試文本，實驗結(jié)果如圖3所示。

圖3 各詞典機制分詞時間分布圖

5 結(jié) 論

文中算法實現(xiàn)了合理設(shè)置初始最大詞長及動態(tài)選擇匹配詞長，并結(jié)合算法設(shè)計了雙字哈希余字按詞長分組的詞典機制，在不影響原最大匹配算法分詞質(zhì)量的前提下大大提高了分詞效率。

文中只針對算法流程及詞典結(jié)構(gòu)加以改進，提高了運算速度，對于最大匹配算法產(chǎn)生的分詞歧義問題并未涉及。下一步的研究重點是通過改進算法有效解決分詞歧義問題，進一步提高算法分詞性能。

[1]奉國和，鄭偉.國內(nèi)中文自動分詞技術(shù)研究綜述[J].圖書情報工作，2011，55（2）:41-45.

[2]來斯惟.徐立恒，陳玉博，等.基于表示學習的中文分詞算法探索[J].中文信息學報，2013，27（5）:8-14.

[3]張桂平，劉東生，尹寶生，等.面向?qū)＠墨I的中文分詞技術(shù)的研究[J].中文信息學報，2010，24（3）:112-116.

[4]德根，焦世斗，周惠巍.基于子詞的雙層CRFs中文分詞[J].計算機研究與發(fā)展，2010，47（5）:962-968.

[5]袁津生，李群.搜索引擎基礎(chǔ)教程[M].北京：清華大學出版社，2010.

[6]梁楨，李禹生.基于Hash結(jié)構(gòu)詞典的逆向回溯中文分詞技術(shù)研究[J].計算機工程與設(shè)計，2010，31（23）:5158-5161.

[7]張彩琴，袁鍵.改進的正向最大匹配分詞算法[J].計算機工程與設(shè)計，2010，31（11）:2595-2633.

[8]康晨陽.基于避免交集型歧義的最大匹配算法改進的研究與實現(xiàn)[D].西安：西安電子科技大學，2012.

[9]王瑞雷，欒靜，潘曉花，等.一種改進的中文分詞正向最大匹配算法[J].用與軟件，2011，28（3）:195-197.

[10]譚駿珊，吳惠雄.一種改進整詞二分法的中文分詞詞典設(shè)計[J].信息技術(shù)，2009（5）:40-42，45.

[11]張科.多次Hash快速分詞算法[J].計算機工程與設(shè)計，2007，28（7）:1716-1718.

[12]張賢坤，李亞南，田雪.基于雙哈希結(jié)構(gòu)的整詞二分詞典機制[J].計算機工程與設(shè)計，2014，35（11）:3956-3960.

[13]莫建文，鄭陽，首照宇，等.改進的基于詞典的中文分詞算法機. 計算機工程與設(shè)計，2013，34（5）:1802-1807.

[14]彭煥峰，丁宋濤.一種基于全Hash的整詞二分詞典機制[J].計算機工程，2011，21:40-42.

[15]葉繼平，張桂珠，中文分詞詞典結(jié)構(gòu)的研究與改進[J].計算機工程與應(yīng)用，2012（23）:139-142.

[16]褚敬年.面向企業(yè)信息檢索的中文分詞系統(tǒng)的研究與實現(xiàn)[D].沈陽:東北大學，2008.

[17]姚興山.基于哈希算法的中文分詞算法的改進[J].圖書情報工作，2008，52（6）:60-62.

[18]張慶揚，柴勝.使用二級索引的中文分詞詞典[J].計算機工程與應(yīng)用，2009，45（19）:139-141.

Improvement on maximum matching method mechanism based on double character Hash indexing

LIU Yong，WEI Guang-ze
（Qingdao University of Science&Technology，Qingdao 266061，China）

Chinese words segmentation is the key technology for computers to carry out text analysis.To improve efficiency of segmentation to meet the growing requirement for text analyzing，we have improved the maximum matching algorithm through analyzing the advantages and disadvantages of several commonly-used mechanical word segmentation algorithm based on dictionary and dictionary mechanism.In view of this，we have designed a dictionary structure，double character hash left words grouped for the maximum matching algorithm on the basis of double-character-hash dictionary，and also proposed improved method on maximum matching based on double character hash structure.This algorithm can be able to effectively avoid the invalid matching of maximum matching algorithm,and significantly improve the rate of segmentation for words under the condition of without influencing the accuracy of primary algorithm.Experimental results show that performance of improved algorithm is greatly improved.

Chinese segmentation； forward maximum matching algorithm； dictionary； Hash structure；Hash function

TP301

A

1674－6236（2017）16-0011-05

2016-05-20稿件編號：201605195

劉 勇（1971—），女，山東青島人，博士，副教授。研究方向：中文分詞，智能家居。