正向最大匹配分詞算法的分析與改進(jìn)

吳旭東

同濟(jì)大學(xué)軟件學(xué)院，上海 201804

0 引言

在自然語(yǔ)言處理中，“詞是最小的能夠獨(dú)立活動(dòng)的有意義的語(yǔ)言成分”[1]，而漢語(yǔ)和英語(yǔ)等其它西文比起來(lái),有著自身的特點(diǎn)。英語(yǔ)、法語(yǔ)等歐美語(yǔ)言在書(shū)寫(xiě)時(shí)就以詞為基本構(gòu)成單位，以空格作為分詞的依據(jù)；而漢語(yǔ)在書(shū)寫(xiě)時(shí)是一大串漢字的字符串，從形式上根本沒(méi)有詞的概念。中文分詞指的就是將一個(gè)漢字序列切分成一個(gè)一個(gè)單獨(dú)的具有實(shí)際意義的詞，它是中文信息處理的基礎(chǔ)。中文自動(dòng)分詞的現(xiàn)有的分詞算法可分為三大類(lèi)：基于字符串匹配的分詞方法、基于理解的分詞方法和基于統(tǒng)計(jì)的分詞方法[2]。

在基于字符串匹配的分詞算法中，詞典的設(shè)計(jì)往往對(duì)分詞算法的效率有很大的影響。本文通過(guò)對(duì)影響正向最大匹配算法效率因素的分析，設(shè)計(jì)一種帶詞長(zhǎng)信息的分詞詞典，同時(shí)在該詞典基礎(chǔ)上，對(duì)正向最大匹配算法做出一些改進(jìn)，以提高分詞的效率。

1 正向最大匹配分詞算法介紹和分析

1.1 正向最大匹配分詞算法介紹

最大匹配算法是最基本的字符串匹配算法之一，它能夠保證將詞典中存在的最長(zhǎng)復(fù)合詞切分出來(lái)。傳統(tǒng)的正向最大匹配分詞算法（Maximum Matching，簡(jiǎn)稱(chēng)MM算法）的算法流程如圖1所示。

圖1 MM 算法流程圖

假設(shè)分詞詞典中的最長(zhǎng)詞的字?jǐn)?shù)為M，令其作為最大匹配系數(shù)。假設(shè)讀取的漢字序列字?jǐn)?shù)為L(zhǎng)，判斷L是否小于最大匹配系數(shù)M。如果L大于最大匹配系數(shù)M，則截取前M個(gè)漢字作為待匹配字段進(jìn)行匹配，否則取整個(gè)漢字序列作為待匹配字段直接在分詞詞典中進(jìn)行匹配。若字典中存在這樣一個(gè)字?jǐn)?shù)為M的詞，則匹配成功，匹配字段被作為一個(gè)詞切分出來(lái)；若詞典中找不到這樣的詞，則匹配失敗，將待匹配字段中的最后一個(gè)字去掉，將剩下的漢字序列作為待匹配字段重新在字典中進(jìn)行匹配處理……如此進(jìn)行下去，直到匹配成功，即切分出一個(gè)詞，或者直到剩余字串的長(zhǎng)度為1為止，即為一個(gè)單字。這樣就完成了一輪查找匹配，然后取剩下的漢字序列以同樣的方法進(jìn)行匹配處理,直到文檔被掃描完為止。

1.2 算法分析

正向最大分詞算法有個(gè)弊端，就是在算法開(kāi)始前必須先預(yù)設(shè)一個(gè)匹配詞長(zhǎng)的初始值，而一般這個(gè)值是詞典中最長(zhǎng)詞的長(zhǎng)度，這個(gè)長(zhǎng)度限制是最大匹配算法在效率與詞長(zhǎng)之間的一種折中。詞長(zhǎng)過(guò)長(zhǎng)效率就比較低，詞典中各個(gè)詞的長(zhǎng)度都不一致，有點(diǎn)較長(zhǎng)，而有的卻只是二字詞或三字詞。如果詞長(zhǎng)過(guò)長(zhǎng)，在查找短字詞時(shí)，將會(huì)出現(xiàn)許多無(wú)效的匹配，這在很大程度上影響了分詞的效率。而如果初始值選取的過(guò)小，那么長(zhǎng)詞就不能得到有效的切分，達(dá)不到最大分詞的目的。

根據(jù)漢語(yǔ)中詞條的分布情況統(tǒng)計(jì)，在漢語(yǔ)中雙字詞語(yǔ)最多，而4字以上的詞則比較少，如下表所示?？梢?jiàn)，當(dāng)初始值設(shè)置過(guò)長(zhǎng)時(shí)，無(wú)效匹配的次數(shù)將在很大程度上消耗算法的效率。

表1 詞條分布情況表

同時(shí)，在確定了詞首字，在字典開(kāi)始查找后，在以該詞首字為前綴的詞語(yǔ)中，詞的長(zhǎng)度一般都不是逐字減少的。比方說(shuō)該字可能包含一個(gè)10字長(zhǎng)的詞語(yǔ)，但是并不含有9字，8字長(zhǎng)的詞語(yǔ)，而這時(shí)如果還是采用逐字減一的方法去匹配，又將增加無(wú)效匹配的次數(shù)，影響算法的效率。

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

針對(duì)如上對(duì)正向最大匹配分詞算法的分析，得出該算法在效率上存在的缺陷主要有：一固定最大匹配系數(shù)，二逐字遞減的匹配。算法改進(jìn)時(shí)將在這兩方面做文章，使最大匹配系數(shù)能以詞首字的改變而動(dòng)態(tài)改變，同時(shí)在減字匹配過(guò)程中，不是每次都逐字減一再去字典匹配，而是利用詞首字中包含的詞長(zhǎng)信息，來(lái)不定長(zhǎng)的減字，以減少無(wú)效匹配的次數(shù)，從而在一定程度上提高算法的效率。

2.1 分詞詞典的設(shè)計(jì)

詞典的組織結(jié)構(gòu)為首字索引結(jié)構(gòu)，所有以同一個(gè)字為首的詞條都組織在一起。詞典由兩部分組成，一部分是首字索引，另一部分是詞典的正文。索引部分由字和以該字為前綴的詞條的詞長(zhǎng)信息兩部分組成。正文部分為詞條內(nèi)容和詞條長(zhǎng)度兩部分信息組成。其中詞條長(zhǎng)度是用來(lái)給詞條排序的，以詞長(zhǎng)從大到小來(lái)組織詞典的正文，同時(shí)在匹配過(guò)程中，先用詞長(zhǎng)比較來(lái)代替直接比較字符串的方法，在詞長(zhǎng)相等的情況下再比較字符序列，來(lái)提高匹配的效率，而且詞長(zhǎng)信息能有效的記錄已查詢(xún)列表的索應(yīng)信息，從而在改變?cè)~長(zhǎng)繼續(xù)查找時(shí)，能高效地減少匹配次數(shù)。其機(jī)構(gòu)如圖所示。

圖2 詞典結(jié)構(gòu)

Step1：取出待處理的漢字序列的首字，在首字hash表中查找，如果存在該字，則轉(zhuǎn)step3；

Step2：不存在則是單字，分出該單字word，轉(zhuǎn)step6；

Step3：取出該字的信息，包含詞長(zhǎng)信息和詞典信息，轉(zhuǎn)Step4；

Step4：遍歷詞長(zhǎng)列表，按序分別取出詞長(zhǎng)設(shè)為匹配詞長(zhǎng)，然后在詞典中查找，詞典包含了詞長(zhǎng)值，在查找時(shí)先比較詞長(zhǎng)，若相等則再比較字符序列，轉(zhuǎn)step5；

Step5：如果存在某一詞長(zhǎng)匹配成功，則分出該詞word，轉(zhuǎn)step7；

Step6：如果全部詞長(zhǎng)匹配都不成功，則說(shuō)明是單字，分出該單字word，轉(zhuǎn)step7；

Step7:從待分詞序列中去掉已分出的詞word，若漢字序列沒(méi)有分詞結(jié)束，轉(zhuǎn)step1，否則結(jié)束。

例如：對(duì)語(yǔ)料“中華人民共和國(guó)是一個(gè)強(qiáng)大的國(guó)家”，使用本算法的處理過(guò)程如下：

1）取序列首字“中”在首字hash表中查詢(xún)，存在該字則取出該首字信息，遍歷詞長(zhǎng)信息列表得到，以該字為前綴的最長(zhǎng)詞

2.2 分詞算法

長(zhǎng)為14，則再取序列中余下的13個(gè)字“華人民共和國(guó)是一個(gè)強(qiáng)大的國(guó)”，在詞典中匹配，發(fā)現(xiàn)匹配不成功；再取下一個(gè)詞長(zhǎng)得到詞長(zhǎng)為10，取序列為“華人民共和國(guó)是一個(gè)”，還是不成功……直到詞長(zhǎng)為7時(shí)，匹配“中華人民共和國(guó)”成功，取出該詞。在匹配過(guò)程中，充分利用詞長(zhǎng)信息，在字符比較之前，先通過(guò)比較詞長(zhǎng)來(lái)篩選，在詞長(zhǎng)相等的情況下，才比較字符序列；

2）然后再取首字“是”，查找首字hash表，不存在以該字為前綴的詞，分出單字“是”；

3）接著處理首字“強(qiáng)”，按照上述方法依次處理余下的字串；

4）最后得到的分詞結(jié)果為：中華人民共和國(guó)/是/一個(gè)/強(qiáng)大/的/國(guó)家。

由以上的一次分詞過(guò)程可以看出，動(dòng)態(tài)設(shè)置最長(zhǎng)匹配詞長(zhǎng)的方法，有效的避免和減少了傳統(tǒng)MM算法（靜態(tài)設(shè)置匹配詞長(zhǎng)的方法）的比較次數(shù)，大大的提高了長(zhǎng)詞匹配的效率。同時(shí)，利用比較先詞長(zhǎng)再比較字符的方法，也在一定程度上提高的算法的效率。

3 結(jié)論

本文主要通過(guò)對(duì)影響正向最大匹配算法效率的因素的分析，提出對(duì)該算法的一些改進(jìn)，以及設(shè)計(jì)了相應(yīng)的詞典結(jié)構(gòu)，以在匹配過(guò)程中盡可能的減少了比較的次數(shù)，在一定程度上提高了分詞的效率。本文沒(méi)有提供對(duì)歧義和未登錄詞的處理，而這是影響基于詞典分詞算法準(zhǔn)確率的重要因素，這將是今后需要解決和處理的方向。

[1]朱德熙.語(yǔ)法講義[M].商務(wù)印書(shū)館，1982.

[2]張啟宇，朱玲，張雅萍.中文分詞算法研究綜述情報(bào)探索，2008，l1.

[3]胡錫衡.正向最大匹配法在中文分詞技術(shù)中的應(yīng)用[J].鞍山師范學(xué)院學(xué)報(bào)，2008，10(2)：42-45.

[4]孫茂松，左正平，黃昌寧.漢語(yǔ)自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報(bào)，2000，14(1)：1-7.