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

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

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

詞庫

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

原理

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

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

整句計算

簡單版

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

比如你輸入了 //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 ,這樣就可以避免一個很小的數和很大的數互相操作而被丟棄。我們使用對數的加法代替原本權重的乘法即可。

總結

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

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

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

anyShare分享到:

發表評論

您的電子郵件地址不會被公開. 必填字段標 *