结巴分词原理

{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;重点关注这一部分