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

劉 勇，魏光澤

（青島科技大學(xué) 山東 青島 266061）

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

劉 勇，魏光澤

（青島科技大學(xué) 山東 青島 266061）

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

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

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

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

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

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

1 最大正向匹配算法分析

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

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

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

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

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

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

2.1 最大正向匹配算法的改進(jìn)

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

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

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

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

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

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

表1 人民日?qǐng)?bào)語(yǔ)料庫(kù)詞語(yǔ)統(tǒng)計(jì)信息

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

圖1 改進(jìn)的詞典機(jī)構(gòu)圖

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

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

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

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

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

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

4）詞典正文。順序存儲(chǔ)某長(zhǎng)度詞語(yǔ)除首字、次字外的剩余部分。

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

3 改進(jìn)后的算法及改進(jìn)機(jī)制分析

3.1 最大正向匹配算法的改進(jìn)

3.1.1 初始最大詞長(zhǎng)選擇

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

3.1.2 算法描述

改進(jìn)后的算法流程圖，如圖2所示。

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

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

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

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

4）當(dāng)前選擇匹配的字符串為Wi Wi+1…Wi+m-1，取除Wi Wi+1外的剩余字符串與m對(duì)應(yīng)的詞典正文進(jìn)行匹配，若匹配成功則切出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，進(jìn)入 1）。

6）設(shè)k為以Wi Wi+1為首二字對(duì)應(yīng)的詞長(zhǎng)序列表中的最小值，若m＞k，取詞長(zhǎng)序列表中小于當(dāng)前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 改進(jìn)的最大匹配算法流程圖

3.2 改進(jìn)機(jī)制分析

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

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

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

4 實(shí)驗(yàn)結(jié)果

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

圖3 各詞典機(jī)制分詞時(shí)間分布圖

5 結(jié) 論

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

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

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

[2]來(lái)斯惟.徐立恒，陳玉博，等.基于表示學(xué)習(xí)的中文分詞算法探索[J].中文信息學(xué)報(bào)，2013，27（5）:8-14.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[17]姚興山.基于哈希算法的中文分詞算法的改進(jìn)[J].圖書(shū)情報(bào)工作，2008，52（6）:60-62.

[18]張慶揚(yáng)，柴勝.使用二級(jí)索引的中文分詞詞典[J].計(jì)算機(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稿件編號(hào)：201605195

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