结巴分词原理

介绍

结巴分词是一个受大家喜爱的分词库&＃xff0c;源码地址为github&＃xff0c;今天我们就跟进源码&＃xff0c;看一下结巴分词的原理

原理

def cut(self, sentence, cut_all&＃61;False, HMM&＃61;True):&＃39;&＃39;&＃39;The main function that segments an entire sentence that containsChinese characters into separated words.Parameter:- sentence: The str(unicode) to be segmented.- cut_all: Model type. True for full pattern, False for accurate pattern.- HMM: Whether to use the Hidden Markov Model.&＃39;&＃39;&＃39;

使用结巴分词的时候&＃xff0c;有三种模式&＃xff0c;这三种模式的进入条件分别为&＃xff1a;

if cut_all:cut_block &＃61; self.__cut_allelif HMM:cut_block &＃61; self.__cut_DAGelse:cut_block &＃61; self.__cut_DAG_NO_HMM

首先我们看一下这三种模式

__cut_all:
1. 原句&＃xff1a;我来到北京清华大学　结果&＃xff1a;我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学
2. 原句&＃xff1a;他来到了网易杭研大厦　结果&＃xff1a;他/ 来到/ 了/ 网易/ 杭/ 研/ 大厦
__cut_DAG:
1. 原句&＃xff1a;我来到北京清华大学　结果:我/ 来到/ 北京/ 清华大学
2. 原句&＃xff1a;他来到了网易杭研大厦结果&＃xff1a;他/ 来到/ 了/ 网易/ 杭研/ 大厦
__cut_DAG_NO_HMM:
1. 原句&＃xff1a;我来到北京清华大学　结果:我/ 来到/ 北京/ 清华大学
2. 原句&＃xff1a;他来到了网易杭研大厦结果&＃xff1a;他/ 来到/ 了/ 网易/ 杭/ 研/ 大厦

下面我们就来分析一下这三种模式&＃xff1a;
这三种模式有一个共同点&＃xff0c;第一步都是先构造DAG&＃xff0c;也就是构造有向无环图。
源码如下&＃xff1a;

def get_DAG(self, sentence):self.check_initialized()DAG &＃61; {}N &＃61; len(sentence)for k in xrange(N):tmplist &＃61; []i &＃61; kfrag &＃61; sentence[k]while i

如果sentence是&＃39;我来到北京清华大学‘&＃xff0c;那么DAG为

 {0: [0], 1: [1, 2], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]} 
直观上来看&＃xff0c;DAG[5]&＃61;[5,6,8]的意思就是&＃xff0c;以’清‘开头的话&＃xff0c;分别以5、6、8结束时&＃xff0c;可以是一个词语&＃xff0c;即’清‘、’清华‘、’清华大学‘
get_DAG方法中&＃xff0c;最重要的也就是self.FREQ了&＃xff0c;它是怎么来的呢&＃xff1f;
 
其实就是通过jieba目录下&＃xff0c;dict.txt文件来产生的self.FREQ,方法如下&＃xff1a;
dict.txt共有349046行&＃xff0c;每一行格式为&＃xff1a;
 一 217830 m
一一 1670 m
一一二 11 m
一一例 3 m
一一分 8 m
一一列举 34 i 
第一部分为词语&＃xff0c;第二部分为该词出现的频率&＃xff0c;第三部分为该词的词性。
以读取’一一列举‘为例子&＃xff0c;首先执行self.FREQ[&＃39;一一列举&＃39;]&＃61;34&＃xff0c;然后会检查’一‘、’一一‘、’一一列‘、’一一列举‘之前是否在self.FREQ中存储过&＃xff0c;如果之前存储过&＃xff0c;则跳过&＃xff0c;否则执行self.FREQ[&＃39;一&＃39;]&＃61;0&＃xff0c;self.FREQ[&＃39;一一&＃39;]&＃61;0&＃xff0c;self.FREQ[&＃39;一一列&＃39;]&＃61;0
所以self.FREQ中不止存储了正常的词语和它出现的次数&＃xff0c;同时也存储了所有词语的前缀&＃xff0c;并将前缀出现的次数设置为0,以和正常词语区别开。
 好了&＃xff0c;现在DAG这部分我们介绍完了&＃xff0c;然后我们分开来介绍一下这三种模式&＃xff1a;
 __cut_all
 源码如下&＃xff1a;
     def __cut_all(self, sentence):dag &＃61; self.get_DAG(sentence)old_j &＃61; -1for k, L in iteritems(dag):if len(L) &＃61;&＃61; 1 and k > old_j:yield sentence[k:L[0] &＃43; 1]old_j &＃61; L[0]else:for j in L:if j > k:yield sentence[k:j &＃43; 1]old_j &＃61; j 
这个具体的遍历方式我们就不细说了&＃xff0c;大家自行看源码吧
 __cut_DAG
     def __cut_DAG(self, sentence):DAG &＃61; self.get_DAG(sentence)route &＃61; {}self.calc(sentence, DAG, route)...... 
首先我们先看一下self.calc方法
     def calc(self, sentence, DAG, route):N &＃61; len(sentence)route[N] &＃61; (0, 0)logtotal &＃61; log(self.total)for idx in xrange(N - 1, -1, -1):route[idx] &＃61; max((log(self.FREQ.get(sentence[idx:x &＃43; 1]) or 1) -logtotal &＃43; route[x &＃43; 1][0], x) for x in DAG[idx]) 
这里使用了一个技巧&＃xff0c;也就是log(a) &＃43; log(b) &＃61; log(ab)&＃xff0c;从而巧妙的避过了乘法&＃xff0c;也就避免了溢出的风险。
其实calc函数就是实现了vertibi算法&＃xff0c;不了解vertibi算法的同学自行百度吧。
 然后再贴上整个__cut_DAG的源码&＃xff1a;
     def __cut_DAG(self, sentence):DAG &＃61; self.get_DAG(sentence)route &＃61; {}self.calc(sentence, DAG, route)x &＃61; 0buf &＃61; &＃39;&＃39;N &＃61; len(sentence)while x  
其中&＃xff0c;重点关注这一部分
                         if not self.FREQ.get(buf):recognized &＃61; finalseg.cut(buf)for t in recognized:yield t 
什么时候会进入finalseg.cut(buf)呢&＃xff1f;实际上&＃xff0c;就是当遇到一些dict.txt中没出现的词的时候&＃xff0c;才会进入这个函数&＃xff1a;
在这个函数中&＃xff0c;就是使用HMM的方法&＃xff0c;对这些未识别成功的词进行标注&＃xff0c;然后我们来介绍一下项目中相关的内容&＃xff1a;
 
其中&＃xff0c;prob_start.py存储的是HMM的起始状态相关的信息&＃xff0c;文件中的数字都经过log处理过&＃xff1a;
 P&＃61;{&＃39;B&＃39;: -0.26268660809250016,&＃39;E&＃39;: -3.14e&＃43;100,&＃39;M&＃39;: -3.14e&＃43;100,&＃39;S&＃39;: -1.4652633398537678} 
B代表begin&＃xff0c;E代表end&＃xff0c;M代表middle&＃xff0c;S代表single。所以在开始时&＃xff0c;HMM的状态只可能是S或者B&＃xff0c;而E和M为负无穷
prob_trans.py存储的是状态转移矩阵&＃xff1a;
 P&＃61;{&＃39;B&＃39;: {&＃39;E&＃39;: -0.510825623765990, &＃39;M&＃39;: -0.916290731874155},&＃39;E&＃39;: {&＃39;B&＃39;: -0.5897149736854513, &＃39;S&＃39;: -0.8085250474669937},&＃39;M&＃39;: {&＃39;E&＃39;: -0.33344856811948514, &＃39;M&＃39;: -1.2603623820268226},&＃39;S&＃39;: {&＃39;B&＃39;: -0.7211965654669841, &＃39;S&＃39;: -0.6658631448798212}} 
prob_emit.py中存储的是在该状态下出现该汉字的概率&＃xff0c;例如p(&＃39;刘&＃39;|S)&＃61;-0.916
 P&＃61;{&＃39;B&＃39;: {&＃39;\u4e00&＃39;: -3.6544978750449433,&＃39;\u4e01&＃39;: -8.125041941842026,&＃39;\u4e03&＃39;: -7.817392401429855,&＃39;\u4e07&＃39;: -6.3096425804013165,&＃39;\u4e08&＃39;: -8.866689067453933,&＃39;\u4e09&＃39;: -5.932085850549891,&＃39;\u4e0a&＃39;: -5.739552583325728,&＃39;\u4e0b&＃39;: -5.997089097239644,&＃39;\u4e0d&＃39;: -4.274262055936421,&＃39;\u4e0e&＃39;: -8.355569307500769,...... 
通过这种方式&＃xff0c;也就可以进行分词了。
‘我/ 来到/ 北京/ 清华大学’对应的状态应该为&＃39;SBEBEBMME&＃39;
 __cut_DAG_NO_HMM
 其实__cut_DAG_NO_HMM和__cut_DAG的区别就是&＃xff1a;对vertibi未成功切分的部分&＃xff0c;__cut_DAG_NO_HMM没有使用HMM进行分词。源码如下&＃xff1a;
     def __cut_DAG_NO_HMM(self, sentence):DAG &＃61; self.get_DAG(sentence)route &＃61; {}self.calc(sentence, DAG, route)x &＃61; 0N &＃61; len(sentence)buf &＃61; &＃39;&＃39;while x