圖/IT可達鴨、網絡
前言
隨著大規模語料庫的建立，以及統計學、機器學習方法的研究和發展，基於統計的中文分詞算法逐漸成為主流。
基於統計分詞的詳解
主要思想：把每n(n>=1)個相鄰的字（可重疊）看作是一個待識別的詞，如果待識別的詞在不同文本中出現的次數越多，就說明這待識別的詞很可能就是一個詞。
因此，我們可以利用字與字相鄰出現的頻率來反應組成詞的可靠度，統計語料中相鄰共現的各個字的組合的頻率，當頻率高於某一個臨界值的時候，便可以認為該字的組合可能是一個詞。
基於統計的分詞算法: HMM
隱含馬爾可夫模型（HMM）是將分詞作為字在句子中的序列標註任務來實現分詞的。其基本思路是：
每個字在構造一個特定的詞語時都佔據著一個確定的詞位，現設定每個字最多隻有四種構詞位置：即B（Begin 詞首）、M（Middle 詞中）、E（End 詞尾）、S（single 單獨成詞）。
舉個例子：
在HMM之前，必須得有三個假設：
假設1: 有限歷史性假設，採用二元模式，每個字只與上一個字和下一個字有關聯;
假設2: 觀測獨立性假設，輸出僅與當前狀態有關;
假設3: 齊次性假設;
另外HMM的標註必須滿足：只有出現BE、BME、BMME、BM...ME（中間M的個數大於等於0）、S 這幾種情況。
簡單的理解，HMM就是通過觀察序列，求解隱含序列的一個過程。
即，最大化 P(字序列|標籤序列）
在求解HMM的過程中，需要維護三個矩陣：1. 初始概率分佈； 2.狀態轉移矩陣A（標籤->標籤的概率）；3. 觀察概率分佈B（標籤->觀察變量的概率）
由假設1可以知，如果最終的最優路徑經過某個o(i)節點，那麼從初始節點到o(i-1)點的路徑必然也是一個最優路徑，因為每個節點o(i)只會影響前後兩個節點的標籤概率。所以最大化 P(字序列|標籤序列）可以通過Viterbi 算法來解決。
基於統計的分詞算法: Viterbi
在HMM中，求解模型最常用的方法是Viterbi算法。它是一種動態規劃方法，核心思想如下圖所示，為了方便演示，將HMM中的BMES標註用1、2、3進行代替演示，字符用A、B、C代替演示。
基於假設1，每一列的節點只能和相鄰列的節點相連，不能跨列相連，節點之間有著不同的距離。
為了找出start到end之間的最短路徑，我們先從Start開始從左到右一列一列地看。
首先起點是Start，從Start到A列的路徑有三種可能：Start-A1、Start-A2、Start-A3，如下圖：
這時，不能武斷地說Start-A1、Start-A2、Start-A3中哪一段必定是全局最短路徑中的一部分，目前為止，任何一段都有可能是全局最短路徑的備選。
繼續往右看，看到了B列。按B列的B1、B2、B3逐個分析。
先看B1:
如上圖，經過B1的所有路徑只有三條： Start-A1-B1、Start-A2-B1、Start-A3-B1。
這三條路徑，各個節點的距離加起來對比，就知道其中哪一條最短。假設Start-A3-B1最短，那麼其他兩條路徑就可以大膽的刪除。現在所有經過B1的路徑只剩下一條路徑，如下圖：
接下來，繼續看B2:
同理，如上圖，經過B2的所有路徑只有三條： Start-A1-B2、Start-A2-B2、Start-A3-B2。
這三條路徑，各個節點的距離加起來對比，就知道其中哪一條最短。假設Start-A1-B2最短，那麼其他兩條路徑就可以大膽的刪除。現在所有經過B2的路徑只剩下一條路徑，如下圖：
接下來，繼續看B3：
同理，如上圖，經過B3的所有路徑只有三條： Start-A1-B3、Start-A2-B3、Start-A3-B3。
這三條路徑，各個節點的距離加起來對比，就知道其中哪一條最短。假設Start-A2-B3最短，那麼其他兩條路徑就可以大膽的刪除。現在所有經過B2的路徑只剩下一條路徑，如下圖：
現在對於B列的所有節點我們都過了一遍，B列的每個節點我們都刪除了一些不可能是答案的路徑，看看我們剩下哪些備選的最短路徑，如下圖：
上圖是我們刪掉了其它不可能是最短路徑的情況，留下了三個有可能是最短的路徑：Start-A3-B1、Start-A1-B2、Start-A2-B3。現在我們將這三條備選的路徑放在一起彙總到下圖：
至此，Start-A-B的最優備選路徑有3條已經確定，繼續往下看C列，這個時候，如果不明白，可以回頭再看一遍，前面的步驟決定你是否能看懂viterbi算法。
接下來講C列，從C1、C2、C3一個個節點進行分析，經過C1節點路徑有：Start-A3-B1-C1、Start-A1-B2-C1、Start-A2-B3-C1。
和B列做法一樣，從這三條路徑中找到最短的那條（假定是Start-A3-B1-C1）
同理，我們可以找到經過C2和C3節點的最短路徑，彙總一下：
到達C列時最終也只剩3條備選的最短路徑，我們仍然沒有足夠信息斷定哪條才是全局最短。最後，我們繼續看End節點，才能得出最後的結論。
到End 的路徑也只有3種可能性：
E點已經是終點了，我們稍微對比一下這三條路徑的總長度就能知道哪條是最短路徑了。
所以，對於ABC可觀察序列，其標註是2、3、2。
結語
HMM一開始比較難以理解，通過一些簡單的例子，可以很好的對HMM的過程進行推理。小編只是通過自己的看法和參考網上的一些例子，對HMM進行整合，難免有不對的地方，歡迎指出。
參考：如何通俗地講解Viterbi算法（來自知乎）
持續關注"IT可達鴨"，每天除了分享有趣Python源碼，還會介紹NLP算法。最後，感謝大家的閱讀，祝大家工作生活愉快！
閱讀更多 IT可達鴨 的文章
