這是我離散數學課的大作業，用圖論算法解決某個複雜的問題，我選的題目是基於統計語言模型的拼音輸入法。通俗地講，就是實現一個支持智能組句的拼音輸入法。注意是智能組句，不是智能組詞，組詞其實就是查詞典，哪怕是人也是這麼做的，只不是這部詞典在大腦中而已，否則就是“造詞”了。而電腦組句的方法就和人有很大區別了，因為讓電腦理解一個句子的結構是極端困難的，尤其是作為分析語的中文，所以說這裡面蘊含著許多難題。說到這裡我想到了關於人工智能的討論，心理學家和工程科學家在對人工智能的認識上有著根本的分歧，即工程科學家認為人工智能就是實際效果顯得有類似人類的智能，而心理學家則把具有模仿認為思考、推理和行為的能力作為人工智能的判斷標準。在不同的認知基礎上人工智能的研究朝著不同的方向發展，事實情況是基於效果的人工智能的水平不斷在進步，而基於模仿的人工智能難有突破。作為一個拼音輸入法，實際效果比所謂智能的理解更為重要（況且作為表達思想和意志的工具，許多人並不希望自己輸入的所有內容被電腦“理解”），而統計語言模型就是一個被廣為應用的手段。

統計語言模型(Statistical Language Model)是聽起來像是個很深奧的東西，其實說出來並不複雜，簡而言之就是一個經過整理的大量語料的統計數據。這個數據有什麼用呢？用處非常大，像機器翻譯、語音識別、中文分詞、信息檢索乃至數據挖掘，都可能要用到統計語言模型，把它用到輸入法上面其實是最直接的使用。舉個簡單的例子來說，“wo shi zhong guo ren”這個音節序列中，“wo shi”可能對應了“我是”、“臥室”、“我市”、“臥式”等詞，而“zhong guo ren”則可能是“中國人”或者“種果人”，最佳的組句方案是什麼呢？這就要用到統計語言模型了，我們在這一大堆統計數據中，分別找到詞頻最大的單詞，如“我是”和“中國人”，句子就可以組合出來了。聽起來是不是很自然的想法呢？找出詞頻最大的詞組合到一起，就成了句子。事實上就是這樣，不少輸入法都以這種方式實現，而且效果也不差。例如早期的拼音加加、紫光拼音，Linux平臺下ibus-pinyin。追溯一下，使用這種方法的鼻祖應該是智能ABC輸入法吧，在當年這可是改變了中國人輸入習慣的一個劃時代產品。然而統計語言模型的應用遠遠不止於此，例如我們收集到的統計語言模型中，從單詞的詞頻上來說，“臥室”可能會比“我是”更高一些，但顯然“我是中國人”比“臥室中國人”更好，所以單看每個單詞的詞頻有時候不一定是最好的，這怎麼辦呢？我們可以不但考慮單詞的詞頻，也考慮兩個詞組合在一起的頻率，這樣的話“我是中國人”肯定是最好的結果了。甚至我們可以統計每三個詞、四個詞、乃至多元組的頻率，則必定會有更好的效果，於是N-gram模型應運而生。如果沒記錯的話，微軟拼音應該是最早做這種嘗試的輸入法了，只可惜微軟拼音的輸入模式偏偏那麼怪異，再加上推廣手段不力，一直默默無聞，反而是搜狗拼音在2006年異軍突起，迅速佔據了桌面市場。目前像搜狗、Google、QQ拼音等輸入法都採用了2-gram或者3-gram語言模型，在Linux和mac平臺下，開源的SunPinyin也是基於3-gram的。

統計語言模型說到底依賴於大量語料的統計，詞彙是數以十萬計的，兩個詞組合起來數據量就達到了百億，三元組則更是天文數字，何處找如此大的規模的語料來進行統計呢？想必一般人是沒有辦法，只有做搜索引擎的商業巨擘才有實力來做。但是時間和空間畢竟有限，不可能把輸入法做成如此一個龐然大物，桌面用戶是消受不起的，因此實際上在使用統計語言模型時，是需要對不少情況進行數學計算擬合出一個近似結果的，這便是從有窮模擬無窮的量化思想的體現。另一個方面，不少公司開始熱衷於做雲輸入法，用一臺超級計算機來計算龐大的數據，只需給出用戶結果，這樣就不必考慮用戶終端的計算能力了。

說了這麼多，談談我的設計吧。我用了盡可能簡單的建模方法實現了一個基於2-gram的拼音輸入法，為了突出圖論（畢竟是圖論課），我還設計了具有歧義的拼音字串的多重解析（如“翻案”和“發難”，對應fanan）。在我的設計中，我大量參考了SunPinyin，也得到了來自SunPinyin作者孫勇的不少幫助。我的程序的全部源碼和數據在slm_based_pinyin_ime.7z，源碼以Apache License 2.0發佈，數據來自open-gram項目。因為和SunPinyin使用了同樣的詞庫和語言模型，所以在測試中不少組句結果會與SunPinyin很接近，有心人可以試試比較一下。此外程序的圖標是ibus-pinyin的。寫完以後我發現我求k優最長路徑的算法寫得不好，在k比較大的時候會很慢，其實可以做到線性複雜度的。下面是一個演示文稿。

演示文稿