用Python從0開始實現一個中文拼音輸入法

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

任務描述

實現一個中文拼音輸入法。

經過分析，分為以下幾個模塊來對中文拼音輸入法進行實現：

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

技術路線

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

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

也許我們還能問出更多的問題，中文拼音輸入法就是這樣，總有可以繼續摳下去的細節。
那么我們如何解決上面的問題？我們的方案如下：

如何切分拼音？

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

如何實時給用戶以反饋？

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

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

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

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

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

用到的數據

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

遇到的問題及解決方案，

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

性能評價

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

給出程序的運行環境

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

執行方法及參數

在項目Project目錄下，運行

$ python gui.py

即可。

Future Works

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

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