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