正向最大匹配分詞算法的分析與改進

吳旭東

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

0 引言

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

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

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

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

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

圖1 MM 算法流程圖

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

1.2 算法分析

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

根據(jù)漢語中詞條的分布情況統(tǒng)計，在漢語中雙字詞語最多，而4字以上的詞則比較少，如下表所示。可見，當(dāng)初始值設(shè)置過長時，無效匹配的次數(shù)將在很大程度上消耗算法的效率。

表1 詞條分布情況表

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

2 改進的正向最大匹配分詞算法

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

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

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

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

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

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

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

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

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

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

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

例如：對語料“中華人民共和國是一個強大的國家”，使用本算法的處理過程如下：

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

2.2 分詞算法

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

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

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

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

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

3 結(jié)論

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

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

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

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

[4]孫茂松，左正平，黃昌寧.漢語自動分詞詞典機制的實驗研究[J].中文信息學(xué)報，2000，14(1)：1-7.