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

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

關(guān)鍵詞：中文輸入法； N-gram模型； k優(yōu)路徑； A*算法

中圖分類號(hào)： TP391

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)： 2095-2163（2016）06-0031-05

0引言

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

而為了提供整句輸入，并減少輸入成本，基于詞的語言模型即已成為本次分析處理首選。在此基礎(chǔ)上，研究可知，語言模型的建立還需要引進(jìn)語料庫的優(yōu)勢(shì)支持?？偟貋碚f，語料庫（Corpus）[3]將可分為生語料庫（未經(jīng)處理的）和熟語料庫（經(jīng)過處理，帶有標(biāo)記的）兩種。相應(yīng)地，熟語料庫通常需要經(jīng)由商業(yè)購買且價(jià)格昂貴，而生語料庫卻不能提供基于詞的語言模型所要求的有效信息。推理至此可得，針對(duì)生語料庫則需要通過分詞（Word_segmentation）算法生成獲取研究所需要的特定信息[4]。[JP]

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

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

1關(guān)鍵技術(shù)

[BT5]1.1N-gram語言模型

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

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

由表 1可知，實(shí)驗(yàn)選取了2個(gè)語料庫，訓(xùn)練樣本總計(jì)選取文本句子共有761 972 個(gè)， 中文字符 10 719 630 個(gè)。

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

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

結(jié)果指標(biāo)設(shè)定為召回率、準(zhǔn)確率和F值。當(dāng)N=1，2，3，4 時(shí)，實(shí)驗(yàn)結(jié)果中各指標(biāo)呈現(xiàn)如圖5所示。分析圖5可知，參數(shù)N的選取，將會(huì)產(chǎn)生不同顆粒度的切分效果。

從圖5中還可以看出，當(dāng)N=2 時(shí)，召回率與準(zhǔn)確率最高，F(xiàn)值最大。N=1時(shí)，顆粒度偏小，不能得到正確分詞；而 N >= 3時(shí)，顆粒度偏大，準(zhǔn)確率對(duì)比 N=1 時(shí)雖然有所提高，但召回率卻仍頗?。磺液瘮?shù)收斂。

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

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

2.2前k優(yōu)路徑選取實(shí)驗(yàn)

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

圖7給出了3種關(guān)于求解前k優(yōu)路徑研究算法在不同點(diǎn)數(shù)的有向無環(huán)圖中求取準(zhǔn)確率的示意圖，橫坐標(biāo)代表有向無環(huán)圖點(diǎn)的數(shù)量，縱坐標(biāo)代表準(zhǔn)確率的百分比。圖7表明，僅從準(zhǔn)確率的角度來說，3種算法都能滿足要求，在含普通點(diǎn)數(shù)的有向環(huán)圖中準(zhǔn)確率可以達(dá)到100%。

圖8是3種求解前k優(yōu)路徑算法隨著有向無環(huán)圖點(diǎn)的數(shù)量的遞增所顯示的消耗時(shí)間示意圖，橫坐標(biāo)代表有向無環(huán)圖所包含的點(diǎn)的個(gè)數(shù)，縱坐標(biāo)代表求取前k優(yōu)路徑所消耗的時(shí)間（以ms為單位）。本實(shí)驗(yàn)選用圖是在確保其是有向無環(huán)圖的前提下隨機(jī)生成的，由圖8對(duì)比試驗(yàn)結(jié)果可知這3種算法在對(duì)前k優(yōu)路徑的求取中，擬用的A*算法效率較高。

在此，針對(duì)本次設(shè)計(jì)的中文輸入法選用的A*算法進(jìn)行極限測(cè)試，驗(yàn)證算法的高效可用程度，即當(dāng)詞圖較為復(fù)雜的情況下算法依然能保持較高的處理效率。測(cè)試結(jié)果如圖9所示。圖9中，橫坐標(biāo)代表有向無環(huán)圖點(diǎn)的數(shù)目，縱坐標(biāo)代表求前k短路所用的時(shí)間（以ms為單位）。

[JP2]由實(shí)驗(yàn)結(jié)果可知，研究中基于A*的求解k-best的算法準(zhǔn)確率高達(dá)百分之百，因而能夠達(dá)到拼音輸入法對(duì)前k優(yōu)路徑的要求。此外，又經(jīng)過有向無環(huán)圖點(diǎn)數(shù)較多時(shí)的極限測(cè)試可以進(jìn)一步看出基于A*的k-best的求解算法具有較高的穩(wěn)定性，因此在輸入法的開發(fā)設(shè)計(jì)中采用了基于A*求解k-best的算法。[JP]

3結(jié)束語

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

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

參考文獻(xiàn)：

[1]宗成慶. 統(tǒng)計(jì)自然語言處理[M]. 北京： 清華大學(xué)出版社， 2008：14-143.

[2]王希杰. 最大正向匹配分詞算法的VC++實(shí)現(xiàn)[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]張俊. 基于神經(jīng)網(wǎng)絡(luò)的拼音漢字轉(zhuǎn)換[D]. 南京：南京理工大學(xué)，2004.[JP]

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

[6]崔剛. 從語言處理的復(fù)雜性與高效性看聯(lián)結(jié)主義[J]. 外語與外語教學(xué)，2007（5）：1-4，41.

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

[8] 鄒榮. 大詞匯量連續(xù)語音識(shí)別系統(tǒng)中統(tǒng)計(jì)語言模型的研究[D]. 北京：北京郵電大學(xué)， 2006.

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

[10]吳軍. 數(shù)學(xué)之美[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著. 統(tǒng)計(jì)自然語言處理基礎(chǔ)[M]. 苑春法，李慶中，王 昀，等譯. 北京：電子工業(yè)出版社，2005：37-111.