最大匹配算法研究

萬 莛

（武漢理工大學 計算機科學與技術學院，湖北 武漢430063）

作為計算機信息處理中最基礎、最關鍵的技術，中文分詞一直是人們研究的熱點。中文分詞就是將連續的漢字序列按照一定的規律分割成一個個單獨的詞的過程[1]。在英文句子中，單詞之間是以空格作為自然分界符的，所以英文分詞比較簡單；而中文以字為基本單位，將一序列字串聯在一起形成句子，從而表達意思，中文的句和段能通過明顯的分界符來劃分，但是詞沒有一個形式上的分界符，所以中文分詞比英文分詞相對困難許多。中文分詞方法總結起來大致可分為三大類：基于詞典直接匹配的分詞方法、基于規則和理解的分詞方法和基于統計模型的分詞方法[2]。本文主要討論基于詞典匹配算法中的最大匹配算法，針對其過分依賴詞典這一弊端進行了探討并提出了對策。

1 最大匹配算法

最大匹配算法是最常用也是最基本的字符串匹配算法之一。它能夠保證切分出來的詞長度最大，同時易于實現[3]。最大匹配算法包括正向最大匹配算法、逆向最大匹配算法和雙向最大匹配算法。

1.1 正向最大匹配算法

正向最大匹配算法流程[4]如圖1所示。

圖1 正向最大匹配算法流程圖

以“中華人民共和國簡稱中國”為例，設定取詞長度n為8，待匹配字符串為s，按照上述步驟處理過程為：

(1)s為“中華人民共和國簡”，查找詞典進行匹配操作，發現沒有該詞；

(2)s去掉最后一個字，變為“中華人民共和國”，查找詞典進行匹配操作，發現該詞，將該詞存入結果文檔中；

(3)更新s，發現剩余的字“簡稱中國”長度不足 8，所以s為“簡稱中國”，查找詞典進行匹配操作，發現沒有該詞；

(4)s去掉最后一個字，變為“簡稱中”，查找詞典進行匹配操作，發現沒有該詞；

(5)s去掉最后一個字，變為“簡稱”，查找詞典進行匹配操作，發現該詞，將其存入結果文檔中；

(6)更新 s，發現剩余的字“中國”長度不足 8，所以 s為“中國”，查找詞典進行匹配操作，發現該詞，將其存入結果文檔中；

(7)更新s，發現 s為空，至此分詞操作結束。分詞結果為“中華人民共和國/簡稱/中國”。

1.2 逆向最大匹配算法

逆向最大匹配算法與正向最大匹配算法流程相似[5]，只是取詞操作與待匹配字串更新操作不同。逆向最大匹配算法從文檔末尾開始進行取詞，匹配不成功刪除的是待匹配字符串的第一個字而不是最后一個。

1.3 雙向最大匹配算法

將正向最大匹配算法與逆向最大匹配算法相結合所產生的算法即是雙向最大匹配算法，它能夠選取正向最大匹配算法和逆向最大匹配算法中分詞效果較好的一方，以提高分詞效果。

1.4 最大匹配算法的問題

最大匹配算法存在以下問題：(1)待匹配字符串最大長度的設定困難，過長易造成效率低，過短則造成分詞不精確；(2)對詞典依賴程度過大，分詞效果取決于詞典。

2 n-gram技術

隨著時間推移，肯定有大量新詞產生。為了豐富詞典，本實驗采用n-gram技術擴充詞典。n-gram就是對一個字序列進行分割，分割產生的字符串是該字序列的子串[6]。 例如：對“中華人民共和國簡稱中國”進行 ngram 2元切分，得到 2元組：中華|華人|人民|民共|共和|和 國|國 簡|簡 稱|稱 中|中 國 。

本實驗中，n-gram擴充詞典步驟[7]如下：

(1)選擇語料庫，本次實驗選擇2010年 10月14日～18日參考消息作為預料庫；

(2)對語料庫進行預處理，將數字、標點、字母等全部刪掉，只剩下漢字；

(3)進行切分并統計詞頻，本次實驗最大詞長為8，所以切分為2元組至8元組，詞頻統計如表1所示。

表1 詞頻數所占比例

(4)選取候選詞。如圖2所示，根據觀察，當設置使用詞頻大于5的詞作為候選詞時，可靠性較高。所以本次實驗設定候選詞的詞頻數大于5。

(5)使用候選詞對詞典進行更新。

3 實驗

為了提高分詞效果，本次實驗采用雙向匹配算法同時使用n-gram技術來負責詞典的更新操作。

由于逆向最大匹配算法比正向最大匹配算法有更高的精度[8]，所以本次實驗中雙向匹配算法的選擇策略是：當正向最大匹配分詞所分出的詞數小于逆向最大匹配算法所分出的詞數時，分詞結果采用正向最大匹配所得結果；否則使用逆向最大匹配算法所得結果。

本次實驗代碼采用java編寫，分詞算法中使用的方法主要有：(1)public StringBuffer result(String s,Set＜String>dic)。用一個StringBuffer來存儲結果，并返回。參數s表示從待分詞文檔中讀到的行字符串，dic表示詞典 。 (2)public void segment(String max,String s,Set＜String>dic)。參數max表示待匹配字符串。(3)public void n_gram()。n_gram的實現，主要使用 HashMap＜String,Integer>，其中String用來存儲詞，Integer存儲詞頻。

在未進行詞典更新操作之前，對“胡錦濤提出了科學發展觀”進行分詞操作得到的結果是“胡錦濤/提出/了/科學發展/觀”；進行詞典更新之后，“科學發展觀”成為單獨一詞，結果為“胡錦濤/提出/了/科學發展觀”，說明使用n-gram對詞典進行更新的確能起到提高分詞效果的作用。

本文首先對最大匹配算法進行了詳細的闡述，繼而提出最大匹配算法的不足之處，即對詞典依賴程度過大，詞典的好壞直接決定了分詞的質量。為解決該問題，提出使用n-gram技術來進行詞典的自我更新，提高詞典質量，從而提高最大匹配算法分詞效果。通過實驗驗證了該方法的可行性。但是仍有不足之處：第一是對用來更新詞典的語料庫要求較高，語料庫必須具有代表性，能包含當前社會所使用的主流詞語；其次語料庫必須足夠大才能得到更好的效果；再次更新詞典對計算機性能消耗較大，必須選擇合理的時間進行更新操作。

[1]周宏宇，張政.中文分詞技術綜述[J].安陽師范學院學報，2010(2)：54-56.

[2]劉春輝.基于優化最大匹配的中文分詞方法研究[D].秦皇島：燕山大學，2009.

[3]林浩，韓冰，楊樂華.一種基于改進最大匹配快速中文分詞算法[J].科技創新導報，2009(9)：248.

[4]趙源.基于最大匹配的中文分詞改進算法研究[J].科技信息，2010(35)：487，496.

[5]王瑞雷，欒靜，潘曉花，等.一種改進的中文分詞正向最大匹配算法[J].計算機應用與軟件，2011，28(3)：195-197.

[6]吳勝遠.一種漢語分詞方法[J].計算機研究與發展，1996，33(4)：306-311.

[7]李文，洪親，滕忠堅，等.基于 n-gram的字符串分割技術的算法實現[J].計算機與現代化，2010(9)：85-87.

[8]張磊，張代遠.中文分詞算法解析[J].電腦知識與技術，2009，5(1)：192-193.