jieba 源码解析
avqz2354
8年前
<h2>jieba 源码解析</h2> <h2>阅读动机</h2> <p><a href="/misc/goto?guid=4958973151014774600" rel="nofollow,noindex">jieba分词</a> 是Python 里面几个比较流行的中文分词工具之一。为了理解分词工具的工作原理，以及实现细节对jieba进行了详细的阅读。</p> <p>读代码之前，我有几个问题是这样的：</p> <ul> <li>分词工具的实现都有哪几个步骤?</li> <li>结巴分词的文档说是使用了 <a href="/misc/goto?guid=4959717070349502537" rel="nofollow,noindex">HMM模型</a> ，但是HMM 模型是如何运用在分词工具中的？，以及模型是如何产生的？</li> <li>几乎所有的分词工具都支持用户添加词库，但是用户词库到底在分词过程中扮演什么角色？</li> </ul> <h2><strong>简介</strong></h2> <pre> <code class="language-python">jieba 分词支持三种分词模式，官方文档给出了如下的Example import jieba seg list = jieba.cut("我来到北京清华大学", cut all=True) print("Full Mode: " + "/ ".join(seg_list)) # 全模式 seg list = jieba.cut("我来到北京清华大学", cut all=False) print("Default Mode: " + "/ ".join(seg_list)) # 精确模式 seg list = jieba.cut("他来到了网易杭研大厦") # 默认是精确模式 print(", ".join(seg list)) seg list = jieba.cut for search("小明硕士毕业于中国科学院计算所，后在日本京都大学深造") # 搜索引擎模式 print(", ".join(seg list))</code></pre> <pre> <code class="language-python">考虑到文章篇幅的限制，我会详细解读默认模式也就是</code></pre> <pre> <code class="language-python">jieba.cut``</code></pre> <p>方法的所有实现。 阅读过程中会涉及一些算法原理，本文不做详细解释。</p> <h2><strong>宏观逻辑</strong></h2> <p style="text-align:center"><img src="https://simg.open-open.com/show/bc820236896efb01f09355379558ad35.png"></p> <p>上面面的流程图很粗糙，但是很好的说明了大概的步骤。 首先使用概率无向图，获得最大概率路径.概率无向图的构建完全依赖于字典，最大概率路径求解也是依赖字典中的词频。 最后使用HMM模型来解决未登录词(Out Of Vocabulary) ，所以在整个过程如果没有模型也是可以的，只要你有一个很好的词典。最大概率路径的求解还有很多方法，记得 <a href="/misc/goto?guid=4959629283739044706" rel="nofollow,noindex">HanLP</a> 的求解就有实现最短路径。</p> <h2><strong>粗分</strong></h2> <p>首先会使用正则将文本切分，正则什么样？就跟现则的是默认模式还是全模式。正则如下：</p> <pre> <code class="language-python">re_han_default = re.compile("([\u4E00-\u9FD5a-zA-Z0-9+#&\._]+)", re.U) re_han_cut_all = re.compile("([\u4E00-\u9FD5]+)", re.U)</code></pre> <pre> <code class="language-python">到底有什么区别： 我写了个测试： ``</code></pre> <p>test <em>str = u'我在重庆abc,他也在重庆? 1234你在重庆吗' print (re</em> han <em>default.split(test</em> str)) print (re <em>han</em> cut <em>all.split(test</em></p> <p>str))</p> <pre> <code class="language-python">输出：</code></pre> <pre> <code class="language-python">['', '我在重庆abc', ',', '他也在重庆', '? ', '1234你在重庆吗', ''] ['', '我在重庆', 'abc,', '他也在重庆', '? 1234', '你在重庆吗', ''] ``</code></pre> <p>上面输出的list 里面每一个被成为block。</p> <h2><strong>细分</strong></h2> <p>对粗分产生的blok ‘abc’这样的不能被</p> <pre> <code class="language-python">re.han</code></pre> <h3><strong>DAG构建</strong></h3> <p>细分的第一步是构建 DAG 即有向无环图。构建的核心代码如下:</p> <pre> <code class="language-python">def get_DAG(self, sentence): self.check_initialized() # 初始化，加载词典 DAG = {} N = len(sentence) for k in xrange(N): tmplist = [] i = k frag = sentence[k] while i < N and frag in self.FREQ: if self.FREQ[frag]: tmplist.append(i) i += 1 frag = sentence[k:i + 1] if not tmplist: tmplist.append(k) DAG[k] = tmplist return DAG</code></pre> <pre> <code class="language-python">怎么个意思呢： 举个例子 *我来到北京清华大学* 产生的DAG 结果如下： ``</code></pre> <p>{0: [0], 1: [1, 2], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]}</p> <pre> <code class="language-python">使用dict 来存储图数据结构。字典中的key 是没个字对应句子的index,后面的value 是一个list就是可达的路径。比如</code></pre> <pre> <code class="language-python">{1：[1,2]}``</code></pre> <p>意思就是“来”和“来到”这两个词在词典中存在。其他的类推。</p> <p>图的产生依赖于</p> <pre> <code class="language-python">self.FREQ</code></pre> <h3><strong>最大概率路径求解</strong></h3> <p>有了上面的DAG 下面求是求解最大概率路径。这个问题有很多中方法，jieba 使用的是动态规划。先不解释动态规划是什么，直接看代码，</p> <pre> <code class="language-python">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): route[idx] = max((log(self.FREQ.get(sentence[idx:x + 1]) or 1) - logtotal + route[x + 1][0], x) for x in DAG[idx])</code></pre> <pre> <code class="language-python">真个过程就上面几行。关键就在max 那一句。这个问题不在这里展开。但是有个小的技巧说下：在对很小的数据进行操作的时候，Python 也是可能向下溢出的，什么意思看下面的例子： ``</code></pre> <p>b = 0.0000001 print b**100</p> <pre> <code class="language-python">结果会打印</code></pre> <pre> <code class="language-python">0.0``</code></pre> <p>所有有个方法就是取log 。这个方法在很多地方都是有用的。 上面还用到了连个</p> <pre> <code class="language-python">tuple</code></pre> <p>求解的结果如果分词时候参数设置的不适用HMM模型，到这里就结束了。求解结果部分如下：key 同样是对应的index.第二个就代表的是 <em>来到</em> 这个词。</p> <pre> <code class="language-python">{0: (-32.587853155857076, 0), 1: (-27.379629658355885, 2),}</code></pre> <h3><strong>未登录词</strong></h3> <p>上面的最大概率在一定程度上解决了歧义问题，但是在分词里面还有另外一个问题未登录词问题也叫OOV(Out Of Vocabulary). jieba 使用HMM来识别未登录词。 比如: “我来到誉存科技” 这句话，产生的最大概率路径是</p> <pre> <code class="language-python">{0: (-42.29693140266269, 0), 1: (-37.0887079051615, 2), 2: (-33.93639839927486, 2), 3: (-28.257272562332492, 3), 4: (-17.872975353951055, 4), 5: (-8.250710549196151, 6), 6: (-10.881580216048834, 6), 7: (0, 0)}</code></pre> <h3><strong>HMM</strong></h3> <p>HMM 隐马模型的定义自己可以去查，就算查完你也不一定能说清楚到底在分词的时候怎么使用的，但是不查绝对不知道。 在分词之前语料会被标注，标注的方式有很多中。其中比较多的是 <strong>BMES</strong> 对应的是B(begin)词的开头,M(Middle)词的中间,E(End)词的结束,S(Single)单个的词 HMM有几个概念，和分词这个具体问题的对应关系如下：</p> <ul> <li>状态序列(state sequence)：BMES 这些状态</li> <li>观测序列(observation sequence)：就是看到的需要分词的句子，所有的字组成一个序列。</li> </ul> <p>现在的问题就是一直观测序列求状态序列。但是第一部我们需要建立HMM模型。 HMM 有三个基本组成： 初始概率状态概率分布A 状态转移矩阵pi 观测概率分布B</p> <p>如果有了上面三个元素一个HMM模型就是定好了。当然还有HMM模型有很多假设，此处省略。 jieba 是如何得到这三个变量的了。这就是HMM的学习问题 了。在标注好的语料之上。可以使用极大似然估计来估计这三个参数。这里也看到，语料是关键因素，语料的质量决定这三个参数。其实估计的过程不管其中的原理就是一些统计计算。jieba 把这三个元素分别存贮在三个py文件中：</p> <pre> <code class="language-python">prob start.py: 初始状态概率 prob trans.py： 状态转移 prob_emit.py： 观测概率分布</code></pre> <p>看看 prob_start:</p> <pre> <code class="language-python">P={'B': -0.26268660809250016, 'E': -3.14e+100, 'M': -3.14e+100, 'S': -1.4652633398537678}</code></pre> <p><code>-3.14e+100</code>表示的是无穷小。意思就是第一个字不可能是E，或者M.只可能是B,S具体是多少，使用语料中的频率做估计。</p> <p>另外两个元素用类似的方法在语料之上很容易得到。</p> <p>有了上面的饮马模型，但是如何通过观测序列求最有可能的状态序列?这时候就到 <a href="/misc/goto?guid=4959717070501780189" rel="nofollow,noindex"> <strong>Viterbi algorithm</strong> </a> 出场了。具体也不展开，反正很简单。</p> <p>到此jieba 分词的真个过程和部分细节和原理都有了，要实现一个自己的分词工具还会远吗？</p> <p> </p> <p> </p> <p>来自：http://midday.me/article/003023dc3f814bc493b37c50b2a9ee71</p> <p> </p>