基於動態規劃的整句輸入法

一般來說，我們不會在用動態規划算法求解的問題上稱呼它為“動態規劃“，而是稱之為“隱馬爾可夫模型“，不過，如果我們單純用動態規划算法來求解一個普通的有向無環圖，那麼就只能說是動態規劃了……

這次我們要來說的，是基於詞庫的整句輸入法。而不是基於狀態轉移的隱馬爾可夫模型求解。

詞庫

由於不需要模型，我們的整句輸入是基於詞彙的，就需要一個詞庫。這個詞庫裡應該記錄了普通人大部分的常用詞彙，而且有一點就是詞頻（權重）一定要是正確的。

原理

你可以這樣理解，當你輸入一串拼音的時候，每一個音會對應一大堆的中文字，如果每一個字單獨來看，就會有太多的字與之對應——這就是所謂的重碼了。而對應詞庫的話，如果用戶輸入的是一個詞彙，那麼我們就優先命中詞庫，這樣一來，由於詞彙的碼比較長，那麼重碼的概率和數量就大大減少了，再配合詞頻，我們就能得到一個比較符合常理的候選字序列供用戶選擇了。

可是整句呢？當用戶輸入了太長而無法從詞庫中匹配到詞彙的時候，我們該怎麼辦呢？

整句計算

簡單版

照著上文中的原理，我們順著思路想想看，這麼長的句子，我們可以考慮把它們拆分開，比如從前往後，依次匹配能找到的最大（長）詞彙，那麼整句輸入就可以實現了！

比如你輸入了 羅/給/shu/ru/前/該/neng/shi/qi/jin/wei/zhi/zui/hao/yong/的/shu/ru/前

那麼我就按照從前往後依次遍歷每一個音，找到最可能的那個，這是可能的一種結果，答案取決於你的詞庫有多爛：

羅格／輸入法／可能是其／近衛／致最好用／的／輸入法

顯然，這距離我們想要的東西還差了很遠。如果你做成這樣就發布，那麼用戶得打死你。所以，我們換一種思路，還是依次匹配最長的可能的詞，但不會自動匹配所有，從第一個能匹配到的詞彙開始，暫停計算讓用戶自己去選擇合適的候選字。

好吧，這樣雖然不算是完整的智能整句輸入，但是如果配合用戶詞庫，那麼勉強能用的，如果你的詞庫數據又比較全，那麼效果應該也不差。

進階版

那麼，就這樣了嗎？當然不是，你看我們還沒有用到題目中的“動態規劃”呢。其實仔細想一想，我們的詞庫，有著準確的詞頻，該怎麼給它利用起來呢？我們通過算法，把詞庫的詞頻進行規劃，將詞頻轉換為權重，詞的權重大於字的權重。

這樣一來，我們在把所有可能的組合一一列舉，然後把每一個詞的詞頻相乘，最後得到結果越大，那麼語句中詞彙就越多，同時還能找到最優的組合（整體詞頻最大），這樣應該就差不多了。

比如 羅/給/shu/ru/前

我們用的詞庫是這樣的：

• 落格：0.11；羅格：0.15；羅哥：0.13
• 個數：0.15；格數：0.13
• 輸入：0.21；淑如：0.19
• 儒法：0.09
• 輸入法：0.29
• 發：0.05；法：0.03

那麼結果就可能有這些（部分）：

1. 羅格／輸入法 —— 0.15*0.29 = 0.0435
2. 落格／輸入法 —— 0.11*0.29 = 0.0319
3. 羅格／輸入／發 —— 0.15*0.21*0.05 = 0.001575
4. 落格／輸入／發 —— 0.11*0.21*0.05 = 0.001155

你看，這下就可以得到更優質一點的解了，雖然看上去和簡單版一樣能夠得到“羅格輸入法”，但上文是無腦匹配，那麼很有可能會將後邊的詞比如“迄今為止”，給拆到了前一個詞裡。但在我們現在的高級算法裡，會計算“迄今為止”的權重，它要比“可能是其”更高，那麼就不會被拆開了，配合權重，我們就能極大概率地避免高頻詞彙被拆的情況。

維特比算法

維特比可能是應用最為廣泛的動態規划算法了吧，從數字通信到語言分詞，無一例外。所以，我們同樣在這裡使用它。不過，我們不是數學家，單純去研究這個算法恐怕不是很有必要，所以算法問題暫時揭過不提，主要還是來看看如何用它來給我們的整句求解。

畢竟，要計算整句中所有的可能的詞彙組合，窮舉是一個 SB 的行為，短了還行，用戶輸入了10個字呢？ 50個字呢？

我們從一串音的頭部開始，依次遍歷整個語句，找到能在詞庫裡找到的所有開始，然後拿它們生成圖的開始，比如還是我們的 羅/給/shu/ru/前 ，我們假定詞庫裡沒有“落格輸入法”這個詞彙，那麼可能的開始就會有：

• 咯（等等等一系列單字）
• 落格
• 羅格
• 羅哥
• 羅格書

將這些依次建立路徑的起始，然後依次遍歷圖的每一條路徑，再重複這個過程，直到結束，這樣，我們就能得到所有可能的組合了，由於我們將計算的問題轉化為了籬笆網絡的有向圖，配合動態規划算法，我們可以將計算複雜度極大地降低，讓我們的算法得以運行。

溢出

由於可能句子會很長，那麼你可能在計算的時候遇到一個問題，就是權重太小以至於計算機的精度不夠導致結果不正確。這裡我簡單說下，那就是使用對數。比如一個很小的值 0.000000000000232，對數的結果就是 −12.6345120151091 ，這樣就可以避免一個很小的數和很大的數互相操作而被丟棄。我們使用對數的加法代替原本權重的乘法即可。

總結

單純用動態規劃+詞庫來實現整句輸入，理解起來不是很難，實現也很簡單，這也是落格輸入法一直在使用的算法——畢竟快！相對於隱馬爾可夫模型基於字的求解，顯然，詞彙的重碼數量小多了！

不過前提也高，要詞庫盡可能的大，否則詞庫中不存在的詞無法參與計算；要求你的詞頻符合實際且質量高，否則計算出的結果差強人意。

另外，我們文中並沒有討論拼音分詞的問題，由於落格輸入法是雙拼輸入法，所以目前得益於雙拼的特性我還沒有面臨這個問題，全拼拼音是變長的，最好的辦法是給它們進行編碼，同時涉及到拼音的分詞問題，這就是另外一塊的知識了。

本文由 落格博客 原創撰寫：落格博客 » 基於動態規劃的整句輸入法

轉載請保留出處和原文鏈接：https://www.logcg.com/archives/2338.html