摘 要： 針對正向最大匹配算法的長詞丟失、匹配次數較多、歧義字段處理的準確率較低等問題，基于Trie樹詞典提出了3種正向增字最大匹配算法，分別使用逐詞掃描、尾部折半掃描和尾部減一掃描這3種掃描方式采集歧義字段，并建立了一套歧義處理方法。實驗結果表明,該3種算法在分詞速度和準確率上均有顯著提高,錯誤率降低到了原算法的三分之一以下。當文本規模大于200 MB時，3種正向增字最大匹配算法的分詞速度均比原最大匹配算法提高30%以上。
關鍵詞： 中文分詞；Trie樹；逐詞掃描；正向增字匹配
隨著互聯網行業的飛速發展，計算機在人們的日常生活中起著越來越大的作用。因此, 中文信息處理技術在我國信息化建設中占據了一個非常重要的地位。而漢語文本中詞與詞之間卻沒有明顯的分隔標記，是連續的漢字串，因而如何進行漢語分詞是中文信息處理中最為基礎、最為重要的問題, 是漢語文本自動標注、搜索引擎、機器翻譯以及Web 信息處理等核心應用中的關鍵步驟[1]。隨著信息時代數據的急劇膨脹，需要對海量的中文信息進行處理，而基于詞典的分詞算法因效率高而受到人們的密切關注。
本文選取正向最大匹配算法(FMM算法)進行改進研究。在對正向最大匹配算法的眾多研究中，參考文獻[2]提出了一種改進的FMM算法，提出了動態確定最大詞長的匹配算法，提升了效率。參考文獻[3] 提出先尋找長度為i(詞典中最長詞的長度) 的詞, 再尋找長度為i-1的詞,……, 直到整個句子被切分完畢。參考文獻[4]提出根據一個詞是否是其他詞的前綴來尋找長詞并切分和判斷是否為組合歧義。參考文獻[5]提出了一種改進的FMM分詞方法，采用“正向掃描+增字最大匹配(包括跳躍匹配)+詞尾歧義檢查+歸右原則(對連續型交集，需左部結合)”，可以消除某些類型的歧義，提高了切詞的精度。
本文基于Trie樹詞典，分別使用逐詞掃描、尾部折半掃描、尾部減一掃描3種掃描方法采集歧義字段，對正向增字最大匹配算法進行了研究，并提出了一套歧義處理的機制，相比原FMM算法大大提高了分詞速度和準確度。
1 正向最大匹配算法
FMM 算法的基本思想是:
(1)找出分詞詞典中最長詞條所含的漢字個數，設為MaxLen.
(2)讀入一句待切分字符串S1，從開始處截取一個長度為MaxLen的字符串W，令W同分詞詞典中的詞條進行匹配。
(3)如果沒有匹配成功，就從W的尾部減去一個字，繼續與詞典中詞條匹配。
(4)重復上述過程，直到匹配成功某一個詞條，或者W長度為0為止。
(5)如果匹配成功，則把W作為一個詞元從S1中切分出去，然后從S1的開始處截取另一個長度為MaxLen的字符串，重復匹配過程，到把句子切分成功為止。
正向最大匹配算法存在著關于匹配詞長初始值MaxLen的選取問題，這個長度限制是FMM算法在效率與詞長之間的一種妥協，如果詞長過短，長詞就會被切錯[5]。如果詞長過長，效率又會比較低。
另外，FMM算法對交集型歧義字段的處理精度不高。
例如以下句子：
句子1：“當中華人民共和國成立的時候”。
句子2：“處理機器發生的故障”。
句子1的切分結果是：“當中/華人/民/共和國/成立/的/時候”，句子2的切分結果是“處理機/器/發生/的/故障”，兩個句子的切分都是錯誤的。
參考文獻[6]表明語料庫中的詞主要是短詞，可是在FMM分詞過程中，必須從字串長詞開始匹配，因而在匹配過程中多數匹配操作都是無意義的，降低了分詞的速度。
針對以上問題，采取了正向增字最大匹配算法，利用Trie樹詞典的查詢機制進行增字查詢，避免了設置最大詞長的問題，減少了冗余匹配。
為了提高歧義處理的精度，分別采用逐詞掃描、尾部折半掃描、尾部減一掃描3種方法采集歧義字段，并建立了一套歧義處理的機制，大大提高了分詞的準確度。
2 逐詞掃描的正向增字最大匹配算法
2.1 逐詞掃描的正向增字最大匹配算法
逐詞掃描的正向增字最大匹配算法的基本思想是：先根據漢語標點符號把漢語句子切分為短句，然后再逐字向后推進，對每一個字進行增字最大匹配，得出以該字為首的最長詞元，然后后移一字重新開始匹配新字符串，并對前后兩詞元判斷是否存在歧義字段，如有歧義則對歧義進行處理。
算法基本過程如下：
輸入：待切分字符串N1N2N3…Nn （N1為字）
輸出：分詞之后的詞串，詞之間用“/”間隔
算法基本過程：
(1)對N1進行正向增字最大匹配，取得以該字為首的最長詞元。即：先取一字N1，在詞典中查找N1，若成詞則保存為詞元，若為詞前綴則再取一字N1N2在詞典中匹配，重復此過程，直到N1N2…Ni既不成詞也不為詞前綴為止，則最后保存的詞元即為以N1為首的最長詞元；
(2)指針后移一字，對N2進行正向增字最大匹配，取得以N2為首的最長詞元；
(3)判斷兩個詞元是否存在歧義字段，若有則對其進行歧義處理；
(4)指針后移一字，重復上述過程。
例如，對于句子“當中華人民共和國成立的時候”，該算法先后切分出以下詞元：“當中”“中華人民共和國”“華人”“人民”“共和國”“成立”“時候”，經歧義處理后得到最后結果：“當/中華人民共和國/成立/的/時候”。顯然比FMM算法準確，而且匹配次數更少。
該算法使用逐詞掃描，在成功匹配出詞元之后保存當前詞元及詞長等信息，并從詞首的下一字進行下次匹配，切分出了字符串中所有可以匹配的詞元，能識別所有的交集歧義字段，大大提高了分詞精度。
2.2 尾部折半掃描的正向增字最大匹配算法
對于逐詞掃描方法，如果存在長詞，就可能出現冗余匹配。例如對于“中華人民共和國”，“華人”“人民”“共和國”都是不必要切分出來的，造成了時間的浪費。因此本文提出了一種“尾部折半”的掃描方式來減少冗余。
該方法與逐詞掃描方法的區別是：對字符串中某一個字進行增字最大匹配后，得出以該字為首的最長詞元的長度n，然后將指針后移n/2個字，重新開始匹配。
該方法相比逐詞掃描方法減少了匹配次數，提高了分詞速度，且基本沒有降低精度。
2.3 尾部減一掃描的正向增字最大匹配算法
為了更進一步提高分詞速度，本文提出了尾部減一掃描的方法。
該方法與前兩種方法的區別是：對字符串中某一個字進行增字最大匹配后，得出以該字為首的最長詞元的長度n，然后將指針后移n-1個字，即來到該詞元尾部最后一個字的位置，重新開始匹配。
該方法進一步減少了匹配次數，但沒有考慮到鏈長為2及以上的歧義字段，在一定程度上使準確率稍有降低。
2.4 歧義處理
對占歧義字段85%以上的交集型歧義字段的研究已成為分詞方法中研究的重點，歧義字段的切分是這一轉換過程的主要困難之一[7]。又由統計可知，交集型歧義字段中，鏈長為1和2的歧義字段合計占到了歧義字段的97.61%，字段出現次數的95.41%[8]。
因此本文對鏈長為1,2,3的交集型歧義字段進行處理，設定消歧規則如下：
規則1：盡量不切分長詞；
規則2：盡量不造成單字；
規則3：如果兩詞元權重相同，則逆向最大匹配優先；
規則4：如果3個詞元相互有交集型歧義字段，則將中間詞元拆分給前后兩個詞元；
規則5：對于鏈長為2、3的交集型歧義字段，將歧義部分劃分給前詞元。
根據以上規則，本文消歧算法如下：
輸入：一組未消歧的詞元L1，L2，…，Ln（有前后位置的區別）
輸出：一組消歧后的詞元組成的詞串，詞之間用“/”間隔。
算法基本過程：
(1)取出最前面的兩個詞元L1、L2，設定初始權重為詞元長度，獲取它們的交集型歧義字段的鏈長N；
(2)若鏈長為0，則無歧義，將前詞元L1存入最終結果集，后詞元L2繼續與下一個詞元L3比較；
(3)如果L1權重大于L2，假如將歧義字段分給L1會造成L2只剩單字、且不能與后字連接成詞的話，判斷減去歧義字段后能否成詞，若能成詞，則將歧義字段分給L2，否則歧義字段分給L1；
(4)如果L1權重小于L2，假如將歧義字段分給L2會造成L1單字，判斷減去歧義字段后能否成詞，若能成詞，則將歧義字段分給L1，否則將歧義字段分給L2；
(5)如果L1權重等于L2，分3種情況討論：① 歧義字段鏈長為1，判斷L2與后一個詞元L3是否有歧義，若有則將L2拆分給L1和L3，且L3權重加一，否則將歧義字段分給L2；② 歧義字段鏈長為2，且L2拆分后能成詞，則將歧義字段劃分給L1，否則分給L2；③ 歧義字段鏈長為3，且L2拆分后能成詞，則將歧義字段劃分給L1，否則分給L2。劃分完畢后將L1存入最終結果集；
(6)重復以上過程，直到將所有詞元都處理完畢。
該算法有效地避免了生成單字，例如對于句子“處理機器發生的故障”中的前兩個詞元“處理機”“機器”，它們的歧義字段為“機”，如果將“機”劃分給前詞元，則后詞元只剩下單字“器”，且不能與后字成詞。而如果將“機”劃分給后詞元，前詞元剩下兩字“處理”可以單獨成詞。因此本算法將“處理機器”切分為“處理/機器”，比正向最大匹配算法要準確。
3 實驗結果及分析
3.1 實驗環境描述
實驗平臺：Inter(R) Core(TM) i5-3470四核四線程3.20 GHz處理器；三級緩存6 MB；4 GB內存；編譯環境為Java7.0版本，編譯器是Eclipse Java EE IDE。
詞典：SCWS簡體中文分詞詞典，共有284 726個詞條，詞典大小2.75 MB，最長詞條的長度為18。
正向最大匹配算法MaxLen選取：雖然最長詞條長度為18，但為了分詞速度不太慢，這里取MaxLen為9。
文本：分別選取5 MB，20 MB，50 MB，100 MMB，200 MB文本進行實驗，多次重復實驗后取平均值。文本編碼方式為utf-8。
測試性能指標：不同文本規模下的分詞速度；分詞的準確率。
3.2 實驗結果
3.2.1 分詞速度
采用逐詞掃描的正向增字最大匹配算法、尾部折半掃描的正向增字最大匹配算法、尾部減一掃描的正向增字最大匹配算法、FMM算法4種算法進行對比實驗。
圖1為在不同文本規模時，4組算法分詞所耗時間對比圖。4組算法對照運行時，分詞詞典和文本相同。
4組算法對比得出，3種正向增字最大匹配算法與原FMM算法相比，在分詞速度上均有明顯提升。其中逐詞掃描、尾部折半掃描、尾部減一掃描這3種方法的速度依次提高。
當文本大小超過20 MB時，3種正向增字最大匹配算法均比原FMM算法速度提升20%以上。隨著數據量的增大，速度的提升更加明顯。當文本規模大于200 MB時，3種正向增字最大匹配算法均比FMM算法提高30%以上。
3.2.2 分詞的準確率
本文用準確率和錯誤切分率來計算分詞的準確度。
準確率的計算公式為：
錯誤切分率的計算公式為：
對1998年1月的人民日報的第一篇文章《邁向充滿希望的新世紀》的正文進行中文分詞，將北大標注的經人工分詞的1998年1月的人民日報語料作為結果檢驗語料。由于詞庫的區別，如果將短詞合并為長詞也視為正確。 實驗結果如表1所示。
對比得知，3種正向增字最大匹配算法的正確率均高于原FMM算法，錯誤切分率降低到了FMM算法的1/3以下。其中尾部減一掃描算法由于沒考慮到鏈長為2以上的交集型歧義字段，正確率比其他兩種方法略低一些。
本文在經典的FMM算法的基礎上，提出了3種不同掃描方式的正向增字最大匹配算法，顯著提高了分詞速度和準確率。實驗證明，當文本規模大于200 MB時，3種正向增字最大匹配算法均比FMM算法提高30%以上。綜合分詞速度和準確率，尾部折半掃描的正向增字最大匹配算法最優。下一步工作將考慮未登錄詞識別、數量詞合并的問題。
參考文獻
[1] 周程遠，朱敏，楊云．基于詞典的中文分詞算法研究[J]．計算機與數字工程，2009, 37(3)：68-71．
[2] 王瑞雷，欒靜，潘曉花，等．一種改進的中文分詞正向最大匹配算法[J]．計算機應用與軟件，2011，28(3)：195-197．
[3] 郭輝, 蘇中義, 王文，等. 一種改進的MM分詞算法[ J] . 微型電腦應用,2002, 18(1): 13-15.
[4] 楊憲澤. 機器翻譯的詞處理研究[J] . 計算機工程與科學, 2009, 31(5): 156-158.
[5] 王惠仙, 龍華.基于改進的正向最大匹配中文分詞算法研究[J].貴州大學學報（自然科學版）,2011,28(5): 112-115
[6] 金春輝，金順福．基于優化最大匹配與統計結合的漢語分詞方法[J].燕山大學學報，2009，33(2): 124-129．
[7] 閆引堂，周曉強．交集型歧義字段切分方法研究[J]．情報學報，2000，19(6): 637-643．
[8] 翟風文，赫楓齡，左萬利．字典與統計相結合的中文分詞方法[J].小型微型計算機系統，2006，27(9): 1766-1771．