jieba原理
一茁帽、步驟
1房待、基于Trie樹結(jié)構(gòu)實(shí)現(xiàn)高效的詞圖掃描蜕猫，生成句子中漢字所有可能成詞情況所構(gòu)成的有向無(wú)環(huán)圖（DAG)
2、采用了動(dòng)態(tài)規(guī)劃查找最大概率路徑, 找出基于詞頻的最大切分組合
3佩迟、對(duì)于未登錄詞粘招，采用了基于漢字成詞能力的HMM模型逆瑞，使用了Viterbi算法
二雌续、名詞解釋
1、 Trie半抱，又經(jīng)常叫前綴樹脓恕，字典樹等等膜宋。它有很多變種，如后綴樹炼幔，Radix Tree/Trie秋茫，PATRICIA tree，以及bitwise版本的crit-bit tree乃秀。當(dāng)然很多名字的意義其實(shí)有交叉肛著。
定義：在計(jì)算機(jī)科學(xué)中，trie跺讯，又稱前綴樹或字典樹枢贿，是一種有序樹，用于保存關(guān)聯(lián)數(shù)組刀脏，其中的鍵通常是字符串局荚。與二叉查找樹不同，鍵不是直接保存在節(jié)點(diǎn)中火本，而是由節(jié)點(diǎn)在樹中的位置決定。一個(gè)節(jié)點(diǎn)的所有子孫都有相同的前綴聪建，也就是這個(gè)節(jié)點(diǎn)對(duì)應(yīng)的字符串钙畔，而根節(jié)點(diǎn)對(duì)應(yīng)空字符串。一般情況下金麸，不是所有的節(jié)點(diǎn)都有對(duì)應(yīng)的值擎析，只有葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)所對(duì)應(yīng)的鍵才有相關(guān)的值。
trie中的鍵通常是字符串挥下，但也可以是其它的結(jié)構(gòu)揍魂。trie的算法可以很容易地修改為處理其它結(jié)構(gòu)的有序序列，比如一串?dāng)?shù)字或者形狀的排列棚瘟。比如现斋，bitwise trie中的鍵是一串位元，可以用于表示整數(shù)或者內(nèi)存地址
基本性質(zhì)：
1偎蘸，根節(jié)點(diǎn)不包含字符庄蹋，除根節(jié)點(diǎn)意外每個(gè)節(jié)點(diǎn)只包含一個(gè)字符。
2迷雪，從根節(jié)點(diǎn)到某一個(gè)節(jié)點(diǎn)限书，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串章咧。
3倦西，每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符串不相同。
2赁严、有向無(wú)環(huán)圖
DAG扰柠，中文名"有向無(wú)環(huán)圖"粉铐。"有向"指的是有方向，準(zhǔn)確的說(shuō)應(yīng)該是同一個(gè)方向耻矮，"無(wú)環(huán)"則指夠不成閉環(huán)秦躯。
3、動(dòng)態(tài)規(guī)劃查找最大概率路徑
動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支裆装，是求解決策過(guò)程最優(yōu)化的數(shù)學(xué)方法踱承，通常情況下應(yīng)用于最優(yōu)化問(wèn)題，這類問(wèn)題一般有很多個(gè)可行的解哨免，每個(gè)解有一個(gè)值茎活，而我們希望從中找到最優(yōu)的答案。
在計(jì)算機(jī)科學(xué)領(lǐng)域琢唾，應(yīng)用動(dòng)態(tài)規(guī)劃的思想解決的最基本的一個(gè)問(wèn)題就是：尋找有向無(wú)環(huán)圖（籬笆網(wǎng)絡(luò)）當(dāng)中兩個(gè)點(diǎn)之間的最短路徑（實(shí)際應(yīng)用于地圖導(dǎo)航载荔、語(yǔ)音識(shí)別、分詞采桃、機(jī)器翻譯等等）懒熙。
若假設(shè)整個(gè)網(wǎng)格的寬度為D，網(wǎng)格長(zhǎng)度為N普办，那么若使用窮舉法整個(gè)最短路徑的算法復(fù)雜度為O（DN）工扎，而使用這種算法的計(jì)算復(fù)雜度為O（ND2）。試想一下衔蹲，若D與N都非常大肢娘，使用維特比算法的效率將會(huì)提高幾個(gè)數(shù)量級(jí)！
同樣是實(shí)現(xiàn)從S到E的最短路徑舆驶。不過(guò)這次把剛剛的情況簡(jiǎn)化了一下橱健，原理是相同的。
4沙廉、HMM模型
隱馬爾可夫模型（Hidden Markov Model拘荡，HMM）是統(tǒng)計(jì)模型，它用來(lái)描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過(guò)程撬陵。其難點(diǎn)是從可觀察的參數(shù)中確定該過(guò)程的隱含參數(shù)俱病。然后利用這些參數(shù)來(lái)作進(jìn)一步的分析，例如模式識(shí)別袱结。
是在被建模的系統(tǒng)被認(rèn)為是一個(gè)馬爾可夫過(guò)程與未觀測(cè)到的（隱藏的）的狀態(tài)的統(tǒng)計(jì)馬爾可夫模型亮隙。
下面用一個(gè)簡(jiǎn)單的例子來(lái)闡述：
假設(shè)我手里有三個(gè)不同的骰子。第一個(gè)骰子是我們平常見(jiàn)的骰子（稱這個(gè)骰子為D6）垢夹，6個(gè)面溢吻，每個(gè)面（1，2，3促王，4犀盟，5，6）出現(xiàn)的概率是1/6蝇狼。第二個(gè)骰子是個(gè)四面體（稱這個(gè)骰子為D4）阅畴，每個(gè)面（1，2迅耘，3贱枣，4）出現(xiàn)的概率是1/4。第三個(gè)骰子有八個(gè)面（稱這個(gè)骰子為D8）颤专，每個(gè)面（1纽哥，2，3栖秕，4春塌，5，6簇捍，7只壳，8）出現(xiàn)的概率是1/8。
假設(shè)我們開始擲骰子暑塑，我們先從三個(gè)骰子里挑一個(gè)吼句，挑到每一個(gè)骰子的概率都是1/3。然后我們擲骰子梯投，得到一個(gè)數(shù)字命辖，1况毅，2分蓖，3，4尔许，5么鹤，6，7味廊，8中的一個(gè)蒸甜。不停的重復(fù)上述過(guò)程，我們會(huì)得到一串?dāng)?shù)字余佛，每個(gè)數(shù)字都是1柠新，2，3辉巡，4恨憎，5，6，7憔恳，8中的一個(gè)瓤荔。例如我們可能得到這么一串?dāng)?shù)字（擲骰子10次）：1 6 3 5 2 7 3 5 2 4
這串?dāng)?shù)字叫做可見(jiàn)狀態(tài)鏈。但是在隱馬爾可夫模型中钥组，我們不僅僅有這么一串可見(jiàn)狀態(tài)鏈输硝，還有一串隱含狀態(tài)鏈。在這個(gè)例子里程梦，這串隱含狀態(tài)鏈就是你用的骰子的序列点把。比如，隱含狀態(tài)鏈有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8
一般來(lái)說(shuō)作烟，HMM中說(shuō)到的馬爾可夫鏈其實(shí)是指隱含狀態(tài)鏈愉粤，因?yàn)殡[含狀態(tài)（骰子）之間存在轉(zhuǎn)換概率（transition probability）。在我們這個(gè)例子里拿撩，D6的下一個(gè)狀態(tài)是D4衣厘，D6，D8的概率都是1/3压恒。D4影暴，D8的下一個(gè)狀態(tài)是D4，D6探赫，D8的轉(zhuǎn)換概率也都一樣是1/3型宙。這樣設(shè)定是為了最開始容易說(shuō)清楚，但是我們其實(shí)是可以隨意設(shè)定轉(zhuǎn)換概率的伦吠。比如妆兑，我們可以這樣定義，D6后面不能接D4毛仪，D6后面是D6的概率是0.9搁嗓，是D8的概率是0.1。這樣就是一個(gè)新的HMM箱靴。
同樣的腺逛，盡管可見(jiàn)狀態(tài)之間沒(méi)有轉(zhuǎn)換概率，但是隱含狀態(tài)和可見(jiàn)狀態(tài)之間有一個(gè)概率叫做輸出概率（emission probability）衡怀。就我們的例子來(lái)說(shuō)棍矛，六面骰（D6）產(chǎn)生1的輸出概率是1/6。產(chǎn)生2抛杨，3够委，4，5怖现，6的概率也都是1/6茁帽。我們同樣可以對(duì)輸出概率進(jìn)行其他定義。比如，我有一個(gè)被賭場(chǎng)動(dòng)過(guò)手腳的六面骰子脐雪，擲出來(lái)是1的概率更大厌小，是1/2，擲出來(lái)是2战秋，3璧亚，4，5脂信，6的概率是1/10癣蟋。
5、Viterbi算法
為了找出S到E之間的最短路徑狰闪，我們先從S開始從左到右一列一列地來(lái)看疯搅。
首先起點(diǎn)是S，從S到A列的路徑有三種可能：S-A1埋泵、S-A2幔欧、S-A3，如下圖：
? ? 我們不能武斷的說(shuō)S-A1丽声、S-A2礁蔗、S-A3中的哪一段必定是全局最短路徑中的一部分，目前為止任何一段都有可能是全局最短路徑的備選項(xiàng)雁社。
? 我們繼續(xù)往右看浴井，到了B列。B列的B1霉撵、B2磺浙、B3逐個(gè)分析。
先看B1：
如上圖徒坡，經(jīng)過(guò)B1的所有路徑只有3條：
S-A1-B1
S-A2-B1
S-A3-B1
以上這三條路徑撕氧，我們肯定可以知道其中哪一條是最短的（把各路徑每段距離加起來(lái)比較一下就知道哪條最短了）。假設(shè)S-A3-B1是最短的崭参，那么我們就知道了經(jīng)過(guò)B1的所有路徑當(dāng)中S-A3-B1是最短的呵曹，其它兩條路徑路徑S-A1-B1和S-A2-B1都比S-A3-B1長(zhǎng)款咖，絕對(duì)不是目標(biāo)答案何暮，可以大膽地刪掉了。刪掉了不可能是答案的路徑铐殃，就是viterbi算法（維特比算法）的重點(diǎn)海洼，因?yàn)楹竺嫖覀冊(cè)僖膊挥每紤]這些被刪掉的路徑了。現(xiàn)在經(jīng)過(guò)B1的所有路徑只剩一條路徑了富腊，如下圖：
接下來(lái)坏逢，我們繼續(xù)看B2：
如上圖，經(jīng)過(guò)B2的路徑有3條：
S-A1-B2
S-A2-B2
S-A3-B2
這三條路徑中我們肯定也可以知道其中哪一條是最短的，假設(shè)S-A1-B2是最短的是整，那么我們就知道了經(jīng)過(guò)B2的所有路徑當(dāng)中S-A1-B2是最短的肖揣，其它兩條路徑路徑S-A2-B2和S-A3-B1也可以刪掉了。經(jīng)過(guò)B2所有路徑只剩一條浮入，如下圖：
接下來(lái)我們繼續(xù)看B3：
如上圖龙优，經(jīng)過(guò)B3的路徑也有3條：
S-A1-B3
S-A2-B3
S-A3-B3
這三條路徑中我們也肯定可以知道其中哪一條是最短的，假設(shè)S-A2-B3是最短的事秀，那么我們就知道了經(jīng)過(guò)B3的所有路徑當(dāng)中S-A2-B3是最短的彤断，其它兩條路徑路徑S-A1-B3和S-A3-B3也可以刪掉了。經(jīng)過(guò)B3的所有路徑只剩一條易迹，如下圖：
現(xiàn)在對(duì)于B列的所有節(jié)點(diǎn)我們都過(guò)了一遍宰衙，B列的每個(gè)節(jié)點(diǎn)我們都刪除了一些不可能是答案的路徑，看看我們剩下哪些備選的最短路徑睹欲，如下圖：
上圖是我們我們刪掉了其它不可能是最短路徑的情況供炼，留下了三個(gè)有可能是最短的路徑：S-A3-B1、S-A1-B2窘疮、S-A2-B3【Ⅱ撸現(xiàn)在我們將這三條備選的路徑匯總到下圖：
S-A3-B1、S-A1-B2考余、S-A2-B3都有可能是全局的最短路徑的備選路徑先嬉，我們還沒(méi)有足夠的信息判斷哪一條一定是全局最短路徑的子路徑。
? 如果我們你認(rèn)為沒(méi)毛病就繼續(xù)往下看C列楚堤，如果不理解疫蔓，回頭再看一遍，前面的步驟決定你是否能看懂viterbi算法（維特比算法）身冬。
? ? 接下來(lái)講到C列了衅胀，類似上面說(shuō)的B列，我們從C1酥筝、C2滚躯、C3一個(gè)個(gè)節(jié)點(diǎn)分析。
經(jīng)過(guò)C1節(jié)點(diǎn)的路徑有：
S-A3-B1-C1嘿歌、
S-A1-B2-C1掸掏、
S-A2-B3-C1
和B列的做法一樣，從這三條路徑中找到最短的那條（假定是S-A3-B1-C1）宙帝，其它兩條路徑同樣道理可以刪掉了丧凤。那么經(jīng)過(guò)C1的所有路徑只剩一條，如下圖：
同理步脓，我們可以找到經(jīng)過(guò)C2和C3節(jié)點(diǎn)的最短路徑愿待，匯總一下：
到達(dá)C列時(shí)最終也只剩3條備選的最短路徑浩螺，我們?nèi)匀粵](méi)有足夠信息斷定哪條才是全局最短。
最后仍侥，我們繼續(xù)看E節(jié)點(diǎn)要出，才能得出最后的結(jié)論。
到E的路徑也只有3種可能性：
E點(diǎn)已經(jīng)是終點(diǎn)了农渊，我們稍微對(duì)比一下這三條路徑的總長(zhǎng)度就能知道哪條是最短路徑了厨幻。
在效率方面相對(duì)于粗暴地遍歷所有路徑，viterbi 維特比算法到達(dá)每一列的時(shí)候都會(huì)刪除不符合最短路徑要求的路徑腿时，大大降低時(shí)間復(fù)雜度况脆。
三、步驟講解
1批糟、第一條：基于Trie樹結(jié)構(gòu)實(shí)現(xiàn)高效的詞圖掃描格了，生成句子中漢字所有可能成詞情況所構(gòu)成的有向無(wú)環(huán)圖（DAG)
結(jié)巴分詞自帶了一個(gè)叫做dict.txt的詞典, 里面有2萬(wàn)多條詞, 包含了詞條出現(xiàn)的次數(shù)(這個(gè)次數(shù)是于作者自己基于人民日?qǐng)?bào)語(yǔ)料等資源訓(xùn)練得出來(lái)的)和詞性. 這個(gè)第一條的trie樹結(jié)構(gòu)的詞圖掃描, 說(shuō)的就是把這2萬(wàn)多條詞語(yǔ), 放到一個(gè)trie樹中, 而trie樹是有名的前綴樹, 也就是說(shuō)一個(gè)詞語(yǔ)的前面幾個(gè)字一樣, 就表示他們具有相同的前綴, 就可以使用trie樹來(lái)存儲(chǔ), 具有查找速度快的優(yōu)勢(shì).
作者的源碼中記錄的是句子中某個(gè)詞的開始位置, 從0到n-1(n為句子的長(zhǎng)度), 每個(gè)開始位置作為字典的鍵, value是個(gè)list, 其中保存了可能的詞語(yǔ)的結(jié)束位置(通過(guò)查字典得到詞, 開始位置+詞語(yǔ)的長(zhǎng)度得到結(jié)束位置)
例如:{0:[1,2,3]} 這樣一個(gè)簡(jiǎn)單的DAG, 就是表示0位置開始, 在1,2,3位置都是詞, 就是說(shuō)0~1, 0~2,0~3這三個(gè)起始位置之間的字符, 在dict.txt中是詞語(yǔ).
2、第二條:采用了動(dòng)態(tài)規(guī)劃查找最大概率路徑, 找出基于詞頻的最大切分組合
作者的代碼中講字典在生成trie樹的同時(shí), 也把每個(gè)詞的出現(xiàn)次數(shù)轉(zhuǎn)換為了頻率. 關(guān)于頻率和概率, 這里在啰嗦幾句: 按照定義, 頻率其實(shí)也是一個(gè)0~1之間的小數(shù), 是
? ? ? ? ? ? ? ? ? ? 事件出現(xiàn)的次數(shù)/實(shí)驗(yàn)中的總次數(shù)
因此在試驗(yàn)次數(shù)足夠大的情況下, 頻率約等于概率, 或者說(shuō)頻率的極限就是概率. 不過(guò)通常人們混淆的是頻率和次數(shù), 經(jīng)常把頻率等同于事件出現(xiàn)的次數(shù), 比如這里就是某個(gè)詞語(yǔ)出現(xiàn)的次數(shù), 所以, 頻率在引起混淆的時(shí)候, 對(duì)中國(guó)人來(lái)說(shuō), 還是先理解為出現(xiàn)次數(shù), 然后理解發(fā)現(xiàn)有問(wèn)題, 就理解為出現(xiàn)次數(shù)/總數(shù)這個(gè)比率吧.
動(dòng)態(tài)規(guī)劃中, 先查找待分詞句子中已經(jīng)切分好的詞語(yǔ), 對(duì)該詞語(yǔ)查找該詞語(yǔ)出現(xiàn)的頻率(次數(shù)/總數(shù)), 如果沒(méi)有該詞(既然是基于詞典查找, 應(yīng)該是有的), 就把詞典中出現(xiàn)頻率最小的那個(gè)詞語(yǔ)的頻率作為該詞的頻率, 也就是說(shuō)P(某詞語(yǔ))=FREQ.get(‘某詞語(yǔ)’,min_freq), 然后根據(jù)動(dòng)態(tài)規(guī)劃查找最大概率路徑的方法, 對(duì)句子從右往左反向計(jì)算最大概率(一些教科書上可能是從左往右, 這里反向是因?yàn)闈h語(yǔ)句子的重心經(jīng)常落在后面, 就是落在右邊, 因?yàn)橥ǔＧ闆r下形容詞太多, 后面的才是主干, 因此, 從右往左計(jì)算, 正確率要高于從左往右計(jì)算, 這個(gè)類似于逆向最大匹配), P(NodeN)=1.0, P(NodeN-1)=P(NodeN)*Max(P(倒數(shù)第一個(gè)詞))…依次類推, 最后得到最大概率路徑, 得到最大概率的切分組合.
3徽鼎、第三條, 對(duì)于未登錄詞盛末，采用了基于漢字成詞能力的HMM模型，使用了Viterbi算法
未登錄詞, 作者說(shuō)的是什么意思? 其實(shí)就是詞典 dict.txt 中沒(méi)有記錄的詞. 上面說(shuō)了, 把dict.txt中的所有詞語(yǔ)都刪除了, 結(jié)巴分詞一樣可以分詞, 就是說(shuō)的這個(gè).
怎么做到的? 這個(gè)就基于作者采用的HMM模型了, 中文詞匯按照BEMS四個(gè)狀態(tài)來(lái)標(biāo)記, B是開始begin位置, E是end, 是結(jié)束位置, M是middle, 是中間位置, S是singgle, 單獨(dú)成詞的位置, 沒(méi)有前, 也沒(méi)有后. 也就是說(shuō), 他采用了狀態(tài)為(B,E,M,S)這四種狀態(tài)來(lái)標(biāo)記中文詞語(yǔ), 比如北京可以標(biāo)注為 BE, 即 北/B 京/E, 表示北是開始位置, 京是結(jié)束位置, 中華民族可以標(biāo)注為BMME, 就是開始, 中間, 中間, 結(jié)束.
四否淤、結(jié)巴分詞過(guò)程
1. 加載字典, 生成trie樹
2. 給定待分詞的句子, 使用正則獲取連續(xù)的 中文字符和英文字符, 切分成 短語(yǔ)列表, 對(duì)每個(gè)短語(yǔ)使用DAG(查字典)和動(dòng)態(tài)規(guī)劃, 得到最大概率路徑, 對(duì)DAG中那些沒(méi)有在字典中查到的字, 組合成一個(gè)新的片段短語(yǔ), 使用HMM模型進(jìn)行分詞, 也就是作者說(shuō)的識(shí)別新詞, 即識(shí)別字典外的新詞.
3. 使用python的yield 語(yǔ)法生成一個(gè)詞語(yǔ)生成器, 逐詞語(yǔ)返回.
