本文詳細闡述了結巴分詞的分詞原理，主要包括分詞的具體過程和對未登錄詞的分詞。本文主要參考https://blog.csdn.net/rav009/article/details/12196623中的內容，感謝原作者！
本文如有不正確的地方，懇請各位讀者指出。
結巴分詞算法原理基於前綴詞典實現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖 (DAG)採用了動態規劃查找最大概率路徑, 找出基於詞頻的最大切分組合對於未登錄詞，採用了基於漢字成詞能力的 HMM 模型，使用了 Viterbi 算法下面逐條來解釋。
一、基於前綴詞典實現高效的詞圖掃描，生成句子中漢字所有可能成詞情況所構成的有向無環圖(DAG)結巴分詞自帶了一個叫做dict.txt的詞典，裡面有349046條詞，其每行包含了詞條、詞條出現的次數（這個次數是於作者自己基於人民日報語料等資源訓練得出來的）和詞性，如下圖所示。
dict.txt文件一覽在基於詞典的中文分詞方法中，詞典匹配算法是基礎。為了保證切分速度，需要選擇一個好的查找詞典算法。這裡介紹詞典的Tre樹組織結構。基於前綴詞典實現的詞圖掃描，就是把這34萬多條詞語，放到一個trie樹的數據結構中，trie樹也叫前綴樹或字典樹，也就是說一個詞語的前面幾個字一樣，就表示他們具有相同的前綴，就可以使用trie樹來存儲，具有查找速度快的優勢。一個搜索數字的trie樹的一個節點只保留一個字符。如果一個單詞比一個字符長，則包含第個字符的節點有指針指向下一個字符的節點，以此類推。這樣組成一個層次結構的樹，樹的第一層包括所有單詞的第一個字符，樹的第二層包括所有單詞的第二個字符，以此類推。很顯然，trie樹的最大高度是詞典中最長單詞的長度。
査詢的過程對於查詢詞來說，從前往後一個字符一個字符的匹配。對於trie樹來說，是從根節點往下匹配的過程。
一些人可能會想到把dict.txt中所有的詞彙全部刪掉，然後再試試結巴能不能分詞。結果會發現，結巴依然能夠分詞，不過分出來的詞，大部分的長度為2。這個就是第三條的任務，基於HMM來預測分詞了，我們得會兒再說。
DAG有向無環圖，就是後一句中的生成句子中漢字所有可能成詞情況所構成的有向無環圖，這個是說，給定一個待分詞的句子，將它的所有詞匹配出來，構成詞圖，即是一個有向無環圖DAG，如下圖所示：
DAG詞圖，每條邊上是一個詞那麼具體是怎麼做的呢？分為兩步：1. 根據dict.txt詞典生成trie樹；2. 對待分詞句子，根據trie樹，生成DAG。實際上，通俗的說，就是對待分詞句子，根據給定的詞典進行查詞典操作，生成幾種可能的句子切分，形成類似上圖所示的DAG圖。
對於DAG的實現，在源碼中，作者記錄的是句子中某個詞的開始位置，從0到n-1(n為句子的長度)，設置一個python的字典，每個開始位置作為字典的鍵，value是個python的list，其中保存了可能的詞語的結束位置（通過查字典得到詞，然後將詞的開始位置加上詞語的長度得到結束位置）。例如：{0:[1,2,3]}這樣一個簡單的DAG，就是表示0位置開始，在1,2,3位置都是某個詞的結束位置，就是說0 ~ 1, 0 ~ 2，0 ~ 3這三個位置範圍之間的字符，在dict.txt中都是詞語。
二、採用了動態規劃查找最大概率路徑, 找出基於詞頻的最大切分組合作者的代碼中將字典在生成trie樹的同時，也把每個詞的出現次數轉換為了頻率。頻率其實也是一個0~1之間的小數，是事件出現的次數/實驗中的總次數，因此在試驗次數足夠大的情況下，頻率約等於概率，或者說頻率的極限就是概率。
動態規劃中，先查找待分詞句子中已經切分好的詞語，對該詞語查找該詞語出現的頻率(次數/總數)，如果沒有該詞(既然是基於詞典查找，應該是有可能沒有該詞)，就把詞典中出現頻率最小的那個詞語的頻率作為該詞的頻率。也就是說，P(某詞語)=FREQ.get(『某詞語』, min_freq)， 然後根據動態規劃查找最大概率路徑。對句子從右往左反向計算最大概率(也可以是從左往右，這裡反向是因為漢語句子的重心經常落在後面，就是落在右邊，主要是因為在通常情況下形容詞太多，後面的才是主幹，因此，從右往左計算，正確率要高於從左往右計算，類似於逆向最大匹配的分詞方法)，P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒數第一個詞))，依次類推，最後得到最大概率路徑，即得到最大概率的切分組合。
三、對於未登錄詞，採用了基於漢字成詞能力的HMM模型，使用了Viterbi算法未登錄詞(Out Of Vocabulary word, OOV word)，在這裡指詞典dict.txt中沒有記錄的詞。上面說了，把dict.txt中的所有詞語都刪除了，結巴分詞一樣可以分詞，就是說的這個。怎麼做到的? 這個就基於作者採用的HMM模型了，中文詞彙按照BEMS四個狀態來標記，B是開始begin位置，E是是結束end位置，M是中間middle位置，S是single，單獨成詞的位置。也就是說，他採用了狀態為(B,E,M,S)這四種狀態來標記中文詞語，比如北京可以標註為 BE, 即北/B京/E，表示北是開始位置，京是結束位置。中華民族可以標註為BMME，就是開始，中間，中間，結束。
經過作者對大量語料的訓練，得到了finalseg目錄下的三個文件(來自結巴項目的issues(https://github.com/fxsjy/jieba/issues/7#issuecomment-9692518)):
要統計的主要有三個概率表：
1)位置轉換概率，即B(開頭)，M(中間)，E(結尾)，S(獨立成詞) 四種狀態的轉移概率，該表存放於prob_trans.py中，下面為表中內容；
{'B': {'E': 0.8518218565181658, 'M': 0.14817814348183422},
'E': {'B': 0.5544853051164425, 'S': 0.44551469488355755},
'M': {'E': 0.7164487459986911, 'M': 0.2835512540013088},
'S': {'B': 0.48617017333894563, 'S': 0.5138298266610544}}
例如，P(E|B) = 0.851, P(M|B) = 0.149，說明當我們處於一個詞的開頭時，下一個字是結尾的概率。要遠高於下一個字是中間字的概率，符合我們的直覺，因為二個字的詞比多個字的詞更常見。
2）位置到單字的發射概率，比如P("和"|M)表示一個詞的中間出現"和"這個字的概率，該表存放於prob_emit.py中；
3）詞語以某種狀態開頭的概率，其實只有兩種，要麼是B，要麼是S，該表存放於prob_start.py。這個就是起始向量，就是HMM系統的最初模型狀態
實際上，BEMS之間的轉換有點類似於2元模型，就是2個詞之間的轉移。二元模型考慮一個單詞後出現另外一個單詞的概率，是N元模型中的一種。例如：一般來說，中國之後出現北京的概率大於中國之後出現北海的概率，也就是：中國北京比中國北海出現的概率大些，更有可能是一個中文詞語。
將一個給定的待分詞的句子視為一個觀察序列，對HMM(BEMS)四種狀態的模型來說，就是為了找到一個最佳的BEMS隱狀態序列，這個就需要使用Viterbi算法來得到這個最佳的隱藏狀態序列。通過提前訓練好的HMM轉移概率、發射概率，使用基於動態規劃的viterbi算法的方法，就可以找到一個使概率最大的BEMS序列。按照B打頭，E結尾的方式，對待分詞的句子重新組合，就得到了分詞結果。
比如，對待分詞的句子全世界都在學中國話得到一個BEMS序列 [S,B,E,S,S,S,B,E,S]這個序列只是舉例，不一定正確，通過把連續的BE湊合到一起得到一個詞，S為一個單獨的詞，就得到一個分詞結果了：上面的BE位置和句子中單個漢字的位置一一對應，得到全/S 世界/BE 都/S 在/S 學/S 中國/BE 話/S，從而將句子切分為詞語。
總結結巴分詞的過程:
給定待分詞的句子，使用正則獲取連續的中文字符和英文字符，切分成短語列表，對每個短語使用DAG(查字典)和動態規劃，得到最大概率路徑，對DAG中那些沒有在字典中查到的字，組合成一個新的片段短語，使用HMM模型進行分詞，也就是作者說的識別新詞，即識別字典外的新詞；
使用python的yield語法生成一個詞語生成器，逐詞語返回。
結巴分詞的分詞功能的實現，首先是在大語料上人工對其中的詞語進行統計其出現的頻率，然後對切分的句子形成DAG詞圖，並使用動態規劃的方法找到DAG詞圖中的最短路徑(概率最大)，選取該最短路徑為切分方法。對於OOV詞，使用了HMM，將BEMS視為隱藏狀態，待切分句子為觀測狀態，同樣通過一種動態規劃的算法來找出是概率最大的路徑，該路徑即為最佳切分組合。
參考https://github.com/fxsjy/jieba對Python中文分詞模塊結巴分詞算法過程的理解和分析(https://blog.csdn.net/rav009/article/details/12196623)中文分詞的基本原理以及jieba分詞的用法(https://blog.csdn.net/John_xyz/article/details/54645527)jieba中文分詞源碼分析（一）(https://blog.csdn.net/daniel_ustc/article/details/48195287)結巴分詞原理講解(https://houbb.github.io/2020/01/08/jieba-source-01-overview)《解密搜尋引擎技術實戰 LUCENE & JAVA精華版 第3版》https://zhuanlan.zhihu.com/p/66904318https://zh.wikipedia.org/wiki/Trie