基于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]

而為了提供整句輸入，并減少輸入成本，基于詞的語言模型即已成為本次分析處理首選。……