基于N—gram模型的中文分詞前k優算法

李書豪++陳宇++呂淑寶++張猛治

摘要：本文首先從中文輸入法應用的角度出發，在闡述了N-gram模型的基礎上對中文輸入法的分詞進行了詳細的剖析，進一步根據訓練數據的稀疏問題，使用Back-off模型進行數據的平滑處理。針對系統詞庫數量受限的問題，在構建詞圖的前提下，使用基于A*的算法求解前k優路徑。最后實驗結果表明，本文所使用的基于A*的算法與改進Dijkstra算法、基于DP的算法等常用的求前k優路徑的算法相比，具有較高的效率和準確率，為中文分詞及求取k-best算法的研究開拓了新的思路。

關鍵詞：中文輸入法； N-gram模型； k優路徑； A*算法

中圖分類號： TP391

文獻標志碼：A

文章編號： 2095-2163（2016）06-0031-05

0引言

[JP2]中文輸入法（Chinese input method）是指為了將漢字輸入計算機或手機等電子設備而采用的編碼方法，是中文信息處理的重要技術。時下的中文輸入法可分為基于音標（Phonetic-based）和基于字形（Shape-based）兩種類型[1]，本文使用的方法則屬于第一類。一個具有整句輸入功能的輸入法主要包括著以下部分：首先是語言模型，語言模型將提供輸入法其他部分所需要的信息；其次是輸入處理（拼音流切分）[2]，該部分把輸入的拼音流切分為單個音節的序列，供音-字轉換部分設計使用；最后是音-字轉換部分，該部分將處理好的單音節序列轉化為漢字編碼進行結果輸出。其中，漢語的語言模型大體上可劃定為基于字和基于詞的這樣2個研究進展方向。[JP3]

而為了提供整句輸入，并減少輸入成本，基于詞的語言模型即已成為本次分析處理首選。在此基礎上，研究可知，語言模型的建立還需要引進語料庫的優勢支持。總地來說，語料庫（Corpus）[3]將可分為生語料庫（未經處理的）和熟語料庫（經過處理，帶有標記的）兩種。相應地，熟語料庫通常需要經由商業購買且價格昂貴，而生語料庫卻不能提供基于詞的語言模型所要求的有效信息。推理至此可得，針對生語料庫則需要通過分詞（Word_segmentation）算法生成獲取研究所需要的特定信息[4]。[JP]

目前，中文分詞算法的核心類別可大致分為字符匹配[5]、理解法[6]和統計法。使用一個性能優良的分詞算法即能以更少的資源建立信息高度準確的語言模型，而這樣的語言模型就可以大大提升輸入法的用戶體驗，同時也將進一步減少用戶的輸入成本[7]。

另外，拼音流的切分算法是音-字轉換的前提，快速準確的切分是后續查詞、解碼的實現關鍵。而音-字轉換部分[8]則決定著整個輸入法的單詞轉化的時間成本。綜上所述，為了完成整句匹配的功能，輸入法將在基于詞的N-gram語言模型的研發過程后，以單音節序列建立有向無環詞圖，并將問題轉化為求解k-best問題。此后，對于k-best問題，本文還將重點對比改進Dijkstra算法、基于DP[9]的算法以及本文所用的基于A*的求解算法[10]。

1關鍵技術

[BT5]1.1N-gram語言模型

N-gram模型是大詞匯連續語音識別中常用的一種語言模型[11]。對于中文而言，可稱其為漢語語言模型（CLM，Chinese Language Model）。CLM利用上下文相鄰詞間的搭配信息，可以計算出具有最大概率的句子，從而實現到漢字的自動轉換，且無需用戶手動選擇，高效解決了許多漢字對應一個相同拼音的重碼問題。

N-gram模型是基于這樣一種假設，第n個詞的出現只與前面的n-1個詞相關，而與其他任何詞都不相關，整句的概率就是各個詞出現概率的乘積。每個詞的概率都可以通過從語料庫中直接統計n個詞出現的次數而最終得到。依據該假設，可給出該模型的概率表示：

由表 1可知，實驗選取了2個語料庫，訓練樣本總計選取文本句子共有761 972 個， 中文字符 10 719 630 個。

將選擇的樣本用于訓練N-gram模型，并對as_testing.utf8 語料庫處理展開基于N-gram的邊界探索法N-boundary 的不同參數的分詞研究。

設計時，將分別選取N=1，2，3，4 ，以此獲得迭代分詞的實驗測試效果。這樣，即可確定n-boundary 分詞算法中參數N對于生語料庫的作用影響，從而選擇提取最優參數。

結果指標設定為召回率、準確率和F值。當N=1，2，3，4 時，實驗結果中各指標呈現如圖5所示。分析圖5可知，參數N的選取，將會產生不同顆粒度的切分效果。

從圖5中還可以看出，當N=2 時，召回率與準確率最高，F值最大。N=1時，顆粒度偏小，不能得到正確分詞；而 N >= 3時，顆粒度偏大，準確率對比 N=1 時雖然有所提高，但召回率卻仍頗小；且函數收斂。

而后，在第一步的基礎上又基于不同參數進行了二次迭代。文中使用了不同N值作為第一次迭代的對比，對比效果如圖6所示。實驗發現，通過迭代就能多次控制分詞顆粒度，提高分詞的準確率，召回率和F值。具體來說，使用4-2 迭代將獲得最好的分詞效果，而且提高準確率至0.783 5。

綜上實驗過程可知，本輸入法將使用n-boundary 邊界探索算法來設計選定二次迭代分詞，參數選擇為4-2，原理是先用N=4進行大顆粒度的切分，再對處理后的語言模型用N=2實現迭代小顆粒度的切分。

2.2前k優路徑選取實驗

在構造出詞圖后，按照切分詞之間轉移的概率拼湊成短語或句子，然后選取整句的概率大小作為輸入法響應詞的返回順序。這樣中文輸入法就轉換成了基本k-best（有向無環圖的求k優路徑）的問題，針對準確率和耗時為輸入法選擇A*作為求取前k優路徑的算法。實驗就準確率和耗時與改進Dijkstra算法和基于DP的算法進行對比，最終驗證了A*算法的優越性。

圖7給出了3種關于求解前k優路徑研究算法在不同點數的有向無環圖中求取準確率的示意圖，橫坐標代表有向無環圖點的數量，縱坐標代表準確率的百分比。圖7表明，僅從準確率的角度來說，3種算法都能滿足要求，在含普通點數的有向環圖中準確率可以達到100%。

圖8是3種求解前k優路徑算法隨著有向無環圖點的數量的遞增所顯示的消耗時間示意圖，橫坐標代表有向無環圖所包含的點的個數，縱坐標代表求取前k優路徑所消耗的時間（以ms為單位）。本實驗選用圖是在確保其是有向無環圖的前提下隨機生成的，由圖8對比試驗結果可知這3種算法在對前k優路徑的求取中，擬用的A*算法效率較高。

在此，針對本次設計的中文輸入法選用的A*算法進行極限測試，驗證算法的高效可用程度，即當詞圖較為復雜的情況下算法依然能保持較高的處理效率。測試結果如圖9所示。圖9中，橫坐標代表有向無環圖點的數目，縱坐標代表求前k短路所用的時間（以ms為單位）。

[JP2]由實驗結果可知，研究中基于A*的求解k-best的算法準確率高達百分之百，因而能夠達到拼音輸入法對前k優路徑的要求。此外，又經過有向無環圖點數較多時的極限測試可以進一步看出基于A*的k-best的求解算法具有較高的穩定性，因此在輸入法的開發設計中采用了基于A*求解k-best的算法。[JP]

3結束語

基于N-gram模型的中文分詞前k優算法對于中文拼音輸入法的各個功能實現展開了全面的研究，較為細致地論述[CM（26]了中文輸入法實現過程中需要語言模型及算法，具有較高的[CM）][LL]

實用性和準確性，對中文拼音輸入法的深入研究奠定了良好基礎。而且，雖然本文是針對中文拼音輸入法給出的研究設計，但是對于其他的拼音文字語言，如日文、泰文等，同樣具有重要參考價值。

參考文獻：

[1]宗成慶. 統計自然語言處理[M]. 北京： 清華大學出版社， 2008：14-143.

[2]王希杰. 最大正向匹配分詞算法的VC++實現[J]. 福建電腦， 2011（4）：71-72.

[3]WOLK K， MARASEK K. A sentence meaning based alignment method for parallel text corpora preparation[J]. Advances in Intelligent Systems and Computing，2014， 275（275）：229-237.

[4][JP3]張俊. 基于神經網絡的拼音漢字轉換[D]. 南京：南京理工大學，2004.[JP]

[5]劉剛，丁曉青，彭良瑞，等. 多知識綜合判決的字符切分算法[J]. 計算機工程與應用，2002（17）：59-61，72.

[6]崔剛. 從語言處理的復雜性與高效性看聯結主義[J]. 外語與外語教學，2007（5）：1-4，41.

[7]徐志明， 王曉龍， 姜守旭. 一種語句級漢字輸入技術的研究[J]. 高技術通訊， 2000（1）：51-55.

[8] 鄒榮. 大詞匯量連續語音識別系統中統計語言模型的研究[D]. 北京：北京郵電大學， 2006.

[9]（美）CORMEN T H， LEISERSON C E， RIVEST R L，等著. 算法導論[M]. 殷建平，徐云，王剛，等譯. 北京：機械工業出版社， 2013：78-301.

[10]吳軍. 數學之美[M]. 北京：人民郵電出版社，2012：154-208.

[11]FIGUEROA A， ATKINSON J. Contextual language models for ranking answers to natural language definition questions[J].Computational Intelligence， 2012，28（4）：528-548.

[12]（美）MANNING C D，（德）SCHTZEH， H著. 統計自然語言處理基礎[M]. 苑春法，李慶中，王 昀，等譯. 北京：電子工業出版社，2005：37-111.