用Python從0開始實(shí)現(xiàn)一個(gè)中文拼音輸入法

眾所周知，中文輸入法是一個(gè)歷史悠久的問題，但也實(shí)在是個(gè)繁瑣的活，不知道這是不是網(wǎng)上很少有人分享中文拼音輸入法的原因，接著這次NLP Project的機(jī)會，我覺得實(shí)現(xiàn)一發(fā)中文拼音輸入法，看看水有多深，結(jié)果發(fā)現(xiàn)還挺深的，但是基本效果還是能出來的，而且看別的組都做得挺好的，這次就分 享一下我們做的結(jié)果吧。 （注：此文假設(shè)讀者已經(jīng)具備一些隱馬爾可夫模型的知識）

任務(wù)描述

實(shí)現(xiàn)一個(gè)中文拼音輸入法。

經(jīng)過分析，分為以下幾個(gè)模塊來對中文拼音輸入法進(jìn)行實(shí)現(xiàn)：

• 核心功能包括拼音切分(SplitPinyin.py)
• HMM模型訓(xùn)練(TrainMatrix.py)
• Trie樹構(gòu)建與搜索接口實(shí)現(xiàn)(PinyinTrie.py)
• 維特比算法實(shí)現(xiàn)以及提供給UI的服務(wù)接口(GodTian_Pinyin.py)
• 最后的UI實(shí)現(xiàn)(gui.py)

技術(shù)路線

在中文拼音輸入法中，我們需要完成拼音序列到漢字序列的轉(zhuǎn)換，比如輸入“nihao”，輸入法會給出我們想輸入的字“你好”，到這里我們就可以問出幾個(gè)問題：

• 如何切分拼音？?
  如： 用戶輸入”xiana”， 輸入法應(yīng)該判斷用戶想輸入”xian a”（閑?。?還是”xia na”（夏娜） 還是”xi an a”（西安啊）？
• 如何實(shí)時(shí)給用戶以反饋？
• 對于切分好的拼音，怎樣找出用戶最想輸入的一串中文顯示給用戶？
• 用戶輸入的拼音是錯(cuò)的的情況下，如何容忍這種錯(cuò)誤？該如何顯示？

也許我們還能問出更多的問題，中文拼音輸入法就是這樣，總有可以繼續(xù)摳下去的細(xì)節(jié)。
那么我們?nèi)绾谓鉀Q上面的問題？我們的方案如下：

如何切分拼音？

這 里我們暫時(shí)采用最長匹配的方式，也就是說，如果用戶輸入的首個(gè)串是拼音或者是某個(gè)合法拼音的前綴，那么我們會繼續(xù)向后發(fā)現(xiàn)，等待用戶輸入，直到用戶輸完后 發(fā)現(xiàn)這個(gè)字符（假設(shè)是第n個(gè)）與原來n-1個(gè)不是合法的拼音也不是合法的拼音的前綴，那么此時(shí)將前面n-1串切分成拼音，這就完成了一個(gè)拼音的發(fā)現(xiàn)，比如 說輸入”xiant”（想輸xiantian），則我們會掃描這個(gè)串，一直到”xian”，到”xiant”的時(shí)候發(fā)現(xiàn)既不是合法拼音的前綴也不是合法拼 音，那么從t前面劃分開，得到”xian’t”，同樣的道理發(fā)現(xiàn)后續(xù)的拼音。
在實(shí)時(shí)任務(wù)中，用戶即使沒有輸完我們?nèi)詰?yīng)該顯示東西，那么我們先切分 拼音，最多只會有最后一個(gè)是不完整的拼音前綴，那么我們將完整的和不完整的分開處理。假設(shè)是”xian’t”的情況，我們將”xian”放入 viterbi算法中，通過HMM得出概率最大的一個(gè)輸出串，然后將最后的”t”在訓(xùn)練過的Trie樹中搜索出所有以”t”為前綴的字，以及他們出現(xiàn)的頻 率，取頻率最高的若干個(gè)，作為viterbi算法的下一個(gè)狀態(tài)的可能集合，然后得到他們的拼音，與前面n-1個(gè)拼音組合起來跑Viterbi算法，得到最 可能的一個(gè)中文串，由于這些頻率最高的字的拼音（即我們可能的觀測值）可能不相同，我們只能將相同音的字作為一次viterbi算法運(yùn)行的下一狀態(tài)，這樣 viterbi跑的次數(shù)就是這些字里面不同音的個(gè)數(shù)，但是由于總數(shù)固定，異音越多，每個(gè)音對應(yīng)的越少，所以總時(shí)間是沒有差別的。
具體Trie樹會在后面講解。

如何實(shí)時(shí)給用戶以反饋？

上 面其實(shí)已經(jīng)初步解釋了如何實(shí)時(shí)反饋，實(shí)時(shí)反饋我們要做的就是用戶每輸一個(gè)字母，我們就能夠顯示出用戶可能想要打的字，那么，以一個(gè)字母開頭的拼音有很多， 每個(gè)拼音對應(yīng)的字也可能有很多，也即結(jié)果有很多，但是我們又不能漏掉，所以只能考慮所有的字，比較選出概率最大的若干個(gè)字，這時(shí)候我們可以采用Trie樹 來解決。Trie樹就是前綴樹，說白了就是將拼音的字母按順序順著根插入到樹中，每個(gè)葉子節(jié)點(diǎn)就是一個(gè)拼音，這個(gè)拼音就是順著根一路走下來取的字母的順序 組合，這樣我們就可以找出以任意字符串為前綴的所有拼音，方法就是dfs遍歷每一個(gè)以其為前綴的子樹的葉子節(jié)點(diǎn)，這時(shí)候我們?nèi)~子節(jié)點(diǎn)存的其實(shí)是一個(gè)字 典，key為這個(gè)拼音對應(yīng)的可能的字，value為這個(gè)字出現(xiàn)的頻率，以作為比較。

對于切分好的拼音，怎樣找出用戶最想輸入的一串中文顯示給用戶？

這里我們使用隱馬爾可夫模型，將用戶想輸入的中文字作為隱狀態(tài)，用戶輸入的拼音為顯狀態(tài)，通過最大似然估計(jì)即頻率估計(jì)出HMM的三個(gè)矩陣的值，最后通過viterbi算法找出概率最大的若干個(gè)中文字串顯示出來。

用戶輸入的拼音是錯(cuò)的的情況下，如何容忍這種錯(cuò)誤？該如何顯示？

由于考慮到實(shí)現(xiàn)高度容錯(cuò)的復(fù)雜性，我們假設(shè)用戶會輸入正確的拼音，在想分割的時(shí)候會自行添加分隔符”‘“，由于大部分輸入法用戶絕大部分時(shí)間都會輸入正確的拼音，所以，這樣一個(gè)假設(shè)既簡化了實(shí)現(xiàn)的過程，又沒有損失太大的用戶體驗(yàn)。

用到的數(shù)據(jù)

由于訓(xùn)練HMM模型的需要，我們從搜狗實(shí)驗(yàn)室找到了SogouQ用戶查詢數(shù)據(jù)集，預(yù)處理成合法的句子之后大約有360M，且為了避免查詢句太短，我們也增加了將近30M的搜狐新聞數(shù)據(jù)作為訓(xùn)練語料，這里面包含了很多的長句子。
通過這兩個(gè)語料的訓(xùn)練，我們得到了長句和短句皆可表現(xiàn)較好效果的HMM模型。并且我們還可以繼續(xù)拓展語料，以增加我們HMM模型的準(zhǔn)確性，這是后話，不提。

遇到的問題及解決方案，

1. UI界面的問題，由于UI設(shè)計(jì)的復(fù)雜性與不同系統(tǒng)的考慮，出現(xiàn)了許多莫名其妙的BUG，這使得我們花了許多時(shí)間。
2. viterbi算法的效率問題，由于以某個(gè)字母開頭的拼音對應(yīng)的字有很多個(gè)，假設(shè)我們?nèi)∽顑?yōu)的K個(gè)，我們需要將這K個(gè)與前面已有的拼音組 合，然后跑一遍Viterbi算法，由于Viterbi算法從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的計(jì)算量很大，我們使用了記憶（cache）的方法來加速，具體方 法就是記錄下某一個(gè)完整拼音串所對應(yīng)的viterbi算法的最后一個(gè)狀態(tài)的相關(guān)情況，這樣如果我們再次遇到這個(gè)拼音串（A） 加上另一個(gè)拼音（B）跑viterbi的情況，我們就不需要從這個(gè)組合串的開頭開始跑viterbi算法了，而是直接從A 串跑完viterbi的最后一個(gè)狀態(tài)（從記憶單元讀?。╅_始，向B進(jìn)行轉(zhuǎn)移。
   這個(gè)記憶單元會隨著程序而一直存在，并且我們對這個(gè)對象做了持久化， 在輸入法啟動時(shí)我們會讀取這個(gè)文件（記憶單元），這也就意味著，如果我們曾經(jīng)輸入過某個(gè)拼音串，那么我們以后再輸入同樣的拼音串的時(shí)候，不再需要跑核心算 法，而是直接顯示結(jié)果，這樣在速度上就取得了顯著的提高，就會出現(xiàn)，輸入法越用越好用，越用越快的好處，當(dāng)然這犧牲了一些存儲空間，但是如今我們都不缺存 儲空間。
3. 重復(fù)計(jì)算的問題，比如在用戶覺得打錯(cuò)了的時(shí)候，往后退格，這時(shí)就會退到某一個(gè)前綴，但是其實(shí)這個(gè)前綴我們是算過了的，也顯示過了的，就是說 我們退回到我們以前顯示過的內(nèi)容的時(shí)候，如果不加優(yōu)化，那么又會重新跑一遍核心的viterbi算法，這樣就會很慢，那么我們還是利用cache思想，將 輸入的拼音串以及對應(yīng)的顯示結(jié)果相對應(yīng)并且存起來，這樣我們就做到了飛速的退格操作。
4. Python語言固有的性能問題，解決這個(gè)問題只有更換語言，事實(shí)上用C++語言實(shí)現(xiàn)的話我相信會快很多，這在后面可以考慮用C++實(shí)現(xiàn)，這也是完全可行的。Python學(xué)習(xí)q-u-n七八四，七五八，二一四教程視頻，工具，各類實(shí)戰(zhàn)操作分享

性能評價(jià)

輸入比較迅速，絕大多數(shù)輸入能在1秒以內(nèi)顯示。輸入過的句子再輸入和退格操作都是毫秒級別的。

給出程序的運(yùn)行環(huán)境

1. Python 2.7
2. 需要安裝的Python包： Tkinter, cPickle, pypinyin等模塊

執(zhí)行方法及參數(shù)

在項(xiàng)目Project目錄下，運(yùn)行

$ python gui.py

即可。

Future Works

由上面我們可以看到其實(shí)可以做的工作還很多，比如

• 改換編譯型語言，如C++，大幅減小計(jì)算開銷
• 不斷隨著用戶的輸入更新HMM模型
• 將軟件嵌入系統(tǒng)中
• 我們觀察到，長句輸入很少有多個(gè)是想打的，不想短句可能想打的情況很多，所以很多與輸入拼音串長度相同的句子我們可以換成短句。
• 。。。