DAG介紹
DAG根據我們生成的前綴字典來構造一個這樣的DAG，對sentence DAG是以{key:list[i,j…], …}的字典結構存儲，其中key是詞的在sentence中的位置，list存放的是在sentence中以key開始且詞sentence[key:i+1]在我們的前綴詞典中 的以key開始i結尾的詞的末位置i的列表，即list存放的是sentence中以位置key開始的可能的詞語的結束位置，這樣通過查字典得到詞, 開始位置+結束位置列表。
例如句子」去北京大學玩「對應的DAG為： {0 : [0], 1 : [1, 2, 4], 2 : [2], 3 : [3, 4], 4 : [4], 5 : [5]}
例如DAG中{0:[0]} 這樣一個簡單的DAG, 就是表示0位置對應的是詞, 就是說0~0,即」去」這個詞 在dict.txt中是詞條。DAG中{1:[1,2,4]}, 就是表示1位置開始, 在1,2,4位置都是詞, 就是說1~1,1~2,1~4 即 「北」，「北京」，「北京大學」這三個詞 在dict.txt對應文件的詞庫中。
通過上面兩小節可以得知，我們已經有了詞庫(dict.txt)的前綴字典和待分詞句子sentence的DAG，基於詞頻的最大切分 要在所有的路徑中找出一條概率得分最大的路徑，該怎麼做呢？
jieba中的思路就是使用動態規劃方法，從後往前遍歷，選擇一個頻度得分最大的一個切分組合。具體實現見代碼，已給詳細注釋。
#動態規劃，計算最大概率的切分組合
def calc(self, sentence, DAG, route):
N = len(sentence)
route[N] = (0, 0)
# 對概率值取對數之後的結果
logtotal = log(self.total)
# 從後往前遍歷句子 反向計算最大概率
for idx in xrange(N - 1, -1, -1):
# [x+1][0]即表示取句子x+1位置對應元組(概率對數，詞語末字位置)的概率對數
route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) - logtotal + route[x + 1][0], x) for x in DAG[idx])
從代碼中可以看出calc是一個自底向上的動態規劃(重疊子問題、最優子結構)，它從sentence的最後一個字(N-1)開始倒序遍歷sentence的字(idx)的方式，計算子句sentence[isdx~N-1]概率對數得分（這裡利用DAG及歷史計算結果route實現，同時贊下 作者的概率使用概率對數 這樣有效防止 下溢問題）。然後將概率對數得分最高的情況以（概率對數，詞語最後一個字的位置）這樣的tuple保存在route中。 根據上面的結束寫了如下的測試：輸出結果為：
「去北京大學玩」的前綴字典:
去 123402
去北 0
去北京 0
去北京大 0
去北京大學 0
去北京大學玩 0
「去北京大學玩」的DAG:
0 : [0]
1 : [1, 2, 4]
2 : [2]
3 : [3, 4]
4 : [4]
5 : [5]
route:
{0: (-26.039894284878688, 0), 1: (-19.851543754900984, 4), 2: (-26.6931716802707, 2), 3: (-17.573864399983357, 4), 4: (-17.709674112779485, 4), 5: (-9.567048044164698, 5), 6: (0, 0)}
去/北京大學/玩
中文分詞的未登錄詞
因此可以看到，未登錄詞是分詞中的一個重要問題，jieba分詞中對於OOV的解決方法是：採用了基於漢字成詞能力的 HMM 模型，使用了 Viterbi 算法。
分詞規範，詞的定義還不明確 (《統計自然語言處理》宗成慶)
歧義切分問題，交集型切分問題，多義組合型切分歧義等 結婚的和尚未結婚的 => 結婚／的／和／尚未／結婚／的 結婚／的／和尚／未／結婚／的
未登錄詞問題 有兩種解釋：一是已有的詞表中沒有收錄的詞，二是已有的訓練語料中未曾出現過的詞，第二種含義中未登錄詞又稱OOV(Out of Vocabulary)。對於大規模真實文本來說，未登錄詞對於分詞的精度的影響遠超歧義切分。一些網絡新詞，自造詞一般都屬於這些詞。
因此可以看到，未登錄詞是分詞中的一個重要問題，jieba分詞中對於OOV的解決方法是：採用了基於漢字成詞能力的 HMM 模型，使用了 Viterbi 算法。
關於HMM的介紹網絡上有很多資源，比如 52nlp HMM系列,在此不再具體介紹了，但一些基礎知識要明確的：
HMM(Hidden Markov Model): 隱式馬爾科夫模型。HMM模型可以應用在很多領域，所以它的模型參數描述一般都比較抽象，以下篇幅針對HMM的模型參數介紹直接使用它在中文分詞中的實際含義來講：
HMM解決的三類問題：a. 評估問題(概率計算問題) 即給定觀測序列 O=O1,O2,O3…Ot和模型參數λ=(A,B,π)，怎樣有效計算這一觀測序列出現的概率. (Forward-backward算法) b. 解碼問題(預測問題) 即給定觀測序列 O=O1,O2,O3…Ot和模型參數λ=(A,B,π)，怎樣尋找滿足這種觀察序列意義上最優的隱含狀態序列S。(viterbi算法,近似算法) c. 學習問題 即HMM的模型參數λ=(A,B,π)未知，如何求出這3個參數以使觀測序列O=O1,O2,O3…Ot的概率儘可能的大. (即用極大似然估計的方法估計參數,Baum-Welch,EM算法)
HMM 模型的五元組表示：{ states，//狀態空間 observations，//觀察空間 start_probability，//狀態的初始分布，即π transition_probability，//狀態的轉移概率矩陣，即A emission_probability//狀態產生觀察的概率，發射概率矩陣,即B }
使用jieba對句子:」到MI京研大廈」進行分詞，若是使用非HMM模式則分詞的結果為：到/MI/京/研/大廈， 使用HMM分詞則結果為：到/MI/京研/大廈。下面一段是利用上一節的程序的計算結果。
"到MI京研大廈"的前綴字典:
到 205341
到M 0
到MI 0
到MI京 0
到MI京研 0
到MI京研大 0
到MI京研大廈 0
"到MI京研大廈"的DAG:
0 : [0]
1 : [1]
2 : [2]
3 : [3]
4 : [4]
5 : [5, 6]
6 : [6]
route:
{0: (-73.28491710434629, 0), 1: (-67.60579126740393, 1), 2: (-49.69423813964871, 2), 3: (-31.78268501189349, 3), 4: (-22.663377731606147, 4), 5: (-11.256112777387571, 6), 6: (-12.298425021367148, 6), 7: (0, 0)}
到/MI/京/研/大廈
...
Loading model cost 0.696 seconds.
Prefix dict has been built succesfully.
# HMM切分結果：
到/MI/京研/大廈
從句子」到MI京研大廈」對應的前綴字典可以看出「京研」並沒有在字典中，但是也被Viterbi算法識別出來了，可以看出HMM的強大之處了，也正是 HMM 三大基本問題之一，即根據觀察序列，求隱藏狀態序列。上一節中我們說明了HMM由五元組表示，那麼這樣的五元組參數在中文分詞中的具體含義是：
states(狀態空間) & observations(觀察空間). 漢字按照BEMS四個狀態來標記，分別代表 Begin End Middle 和 Single， {B:begin, M:middle, E:end, S:single}。分別代表每個狀態代表的是該字在詞語中的位置，B代表該字是詞語中的起始字，M代表是詞語中的中間字，E代表是詞語中的結束字，S則代表是單字成詞。觀察空間為就是所有漢字(我她…)，甚至包括標點符號所組成的集合。狀態值也就是我們要求的值，在HMM模型中文分詞中，我們的輸入是一個句子(也就是觀察值序列)，輸出是這個句子中每個字的狀態值，用這四個狀態符號依次標記輸入句子中的字，可方便的得到分詞方案。如：觀察序列：我在北京 狀態序列：SSBE 對於上面的狀態序列，根據規則進行劃分得到 S/S/BE/ 對應於觀察序列：我/在/北京/ 分詞任務就完成了。同時我們可以注意到：B後面只可能接(M or E)，不可能接(B or E)。而M後面也只可能接(M or E)，不可能接(B, S)。
上文只介紹了五元組中的兩元 states & observations，下文介紹剩下的三元（start_probability，transition_probability，emission_probability）.
start_probability(狀態的初始分布). 初始狀態概率分布是最好理解的，如下 P={ 'B': -0.26268660809250016, 'E': -3.14e+100, 'M': -3.14e+100, 'S': -1.4652633398537678 }示例數值是對概率值取對數之後的結果(trick, 讓概率相乘變成對數相加)，其中-3.14e+100作為負無窮，也就是對應的概率值是0。它表示了一個句子的第一個字屬於{B,E,M,S}這四種狀態的概率，如上可以看出，E和M的概率都是0，這和實際相符合，開頭的第一個字只可能是詞語的首字(B)，或者是單字成詞(S)，這部分內容對應 jieba/finalseg/prob_start.py文件，具體源碼。
transition_probability（狀態的轉移概率矩陣） 轉移概率是馬爾科夫鏈很重要的一個知識點，馬爾科夫鏈(一階)最大的特點就是當前T=i時刻的狀態state(i)，只和T=i時刻之前的n個狀態有關，即: {state(i-1), state(i-2), … state(i - n)} HMM模型有三個基本假設：a. 系統在時刻t的狀態只與時刻t-1處的狀態相關,(也稱為無後效性）; b. 狀態轉移概率與時間無關,(也稱為齊次性或時齊性); c. 假設任意時刻的觀測只依賴於該時刻的馬爾科夫鏈的狀態，與其它觀測及狀態無關,(也稱觀測獨立性假設)。其中前兩個假設為馬爾科夫模型的假設。模型的這幾個假設能大大簡化問題。再看下transition_probability，其實就是一個嵌套的字典，數值是概率求對數後的值,示例: P={'B': {'E': -0.510825623765990, 'M': -0.916290731874155}, 'E': {'B': -0.5897149736854513, 'S': -0.8085250474669937}, 'M': {'E': -0.33344856811948514, 'M': -1.2603623820268226}, 'S': {'B': -0.7211965654669841, 'S': -0.6658631448798212}} 如P[『B』][『E』]代表的含義就是從狀態B轉移到狀態E的概率，由P[『B』][『E』] = -0.510825623765990，表示狀態B的下一個狀態是E的概率對數是-0.510825623765990。這部分內容對應 jieba/finalseg/prob_trans.py文件，具體源碼。
emission_probability(狀態產生觀察的概率，發射概率) 根據HMM觀測獨立性假設發射概率，即觀察值只取決於當前狀態值，也就是: P(observed[i], states[j]) = P(states[j]) * P(observed[i]|states[j]),其中P(observed[i]|states[j])這個值就是從emission_probability中獲取。emission_probability示例如下：P={'B': {'\u4e00': -3.6544978750449433, '\u4e01': -8.125041941842026, '\u4e03': -7.817392401429855, '\u4e07': -6.3096425804013165, ..., 'S':{...}, ... }
比如P[『B』][『\u4e00』]代表的含義就是』B』狀態下觀測的字為』\u4e00』(對應的漢字為』一』)的概率對數P[『B』][『\u4e00』] = -3.6544978750449433。這部分內容對應 jieba/finalseg/prob_emit.py文件，具體源碼。
到這裡已經結合HMM模型把jieba的五元參數介紹完，這五元的關係是通過一個叫Viterbi的算法串接起來，observations序列值是Viterbi的輸入，而states序列值是Viterbi的輸出，輸入和輸出之間Viterbi算法還需要藉助三個模型參數，分別是start_probability，transition_probability，emission_probability。對於未登錄詞（OOV）的問題，即已知觀察序列S，初始狀態概率prob_start，狀態觀察發射概率prob_emit，狀態轉換概率prob_trans。求狀態序列W，這是個解碼問題，維特比算法可以解決。
Viterbi 維特比算法 HMM第二個問題又稱為解碼問題(預測問題)即給定觀測序列 O=O1,O2,O3…Ot和模型參數λ=(A,B,π)，怎樣尋找滿足這種觀察序列意義上最優的隱含狀態序列S。(viterbi算法,近似算法)，同樣的，暴力算法是計算所有可能性的概率，然後找出擁有最大概率值的隱藏狀態序列。與問題一的暴力解決方案類似，複雜度為O(N^T)。那應該用什麼方案呢？還是動態規劃！假設觀察序列為O1,O2,O3,…,Ot. 在時刻i ∈ (1,t]時，定義D為觀察O1,O2,…,Oi且Si=Sk時產生該觀察序列的最大概率：vb 其中，S1,S2,….S(i-1),在此時也已經可以得到(子問題)。vb2 它是一個是對子問題求最大值的最優解問題。對於解碼問題，因為需要求出的是使得觀察序列概率最大的隱藏狀態的序列，而不是最大概率，所以，在算法計算過程中，還需要記錄前一個隱藏狀態的值。
jieba Viterbi 的應用：jieba中對於未登錄詞問題，通過__cut_DAG 函數我們可以看出這個函數前半部分用 calc 函數計算出了初步的分詞，而後半部分就是就是針對上面例子中未出現在語料庫的詞語進行分詞了。由於基於頻度打分的分詞會傾向於把不能識別的詞組一個字一個字地切割開，所以對這些字的合併就是識別OOV的一個方向，__cut_DAG定義了一個buf 變量收集了這些連續的單個字，最後把它們組合成字符串再交由 finalseg.cut 函數來進行下一步分詞。
利用 viterbi算法得到句子分詞的生成器
def __cut(sentence):
global emit_P
# viterbi算法得到sentence 的切分
prob, pos_list = viterbi(sentence, 'BMES', start_P, trans_P, emit_P)
begin, nexti = 0, 0
# print pos_list, sentence
for i, char in enumerate(sentence):
pos = pos_list[i]
if pos == 'B':
begin = i
elif pos == 'E':
yield sentence[begin:i + 1]
nexti = i + 1
elif pos == 'S':
yield char
nexti = i + 1
if nexti < len(sentence):
yield sentence[nexti:]
對應的viterbi算法:
#狀態轉移矩陣，比如B狀態前只可能是E或S狀態
PrevStatus = {
'B':('E','S'),
'M':('M','B'),
'S':('S','E'),
'E':('B','M')
}
def viterbi(obs, states, start_p, trans_p, emit_p):
V = [{}] # 狀態概率矩陣
path = {}
for y in states: # 初始化狀態概率
V[0][y] = start_p[y] + emit_p[y].get(obs[0], MIN_FLOAT)
path[y] = [y] # 記錄路徑
for t in xrange(1, len(obs)):
V.append({})
newpath = {}
for y in states:
em_p = emit_p[y].get(obs[t], MIN_FLOAT)
# t時刻狀態為y的最大概率(從t-1時刻中選擇到達時刻t且狀態為y的狀態y0)
(prob, state) = max([(V[t - 1][y0] + trans_p[y0].get(y, MIN_FLOAT) + em_p, y0) for y0 in PrevStatus[y]])
V[t][y] = prob
newpath[y] = path[state] + [y] # 只保存概率最大的一種路徑
path = newpath
# 求出最後一個字哪一種狀態的對應概率最大，最後一個字只可能是兩種情況：E(結尾)和S(獨立詞)
(prob, state) = max((V[len(obs) - 1][y], y) for y in 'ES')