阅读动机
jieba分词是Python 里面几个比较流行的中文分词工具之一。为了理解分词工具的工作原理，以及实现细节对jieba进行了详细的阅读。
读代码之前，我有几个问题是这样的：
- 分词工具的实现都有哪几个步骤?
- 结巴分词的文档说是使用了HMM模型，但是HMM 模型是如何运用在分词工具中的？，以及模型是如何产生的？
- 几乎所有的分词工具都支持用户添加词库，但是用户词库到底在分词过程中扮演什么角色？
简介
jieba 分词支持三种分词模式，官方文档给出了如下的Example
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
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)) |
考虑到文章篇幅的限制，我会详细解读默认模式也就是jieba.cut方法的所有实现。 阅读过程中会涉及一些算法原理，本文不做详细解释。
宏观逻辑
上面面的流程图很粗糙，但是很好的说明了大概的步骤。 首先使用概率无向图，获得最大概率路径.概率无向图的构建完全依赖于字典，最大概率路径求解也是依赖字典中的词频。 最后使用HMM模型来解决未登录词(Out Of Vocabulary) ，所以在整个过程如果没有模型也是可以的，只要你有一个很好的词典。最大概率路径的求解还有很多方法，记得HanLP的求解就有实现最短路径。
粗分
首先会使用正则将文本切分，正则什么样？就跟现则的是默认模式还是全模式。正则如下：
|
1 2 |
re_han_default = re.compile("([\u4E00-\u9FD5a-zA-Z0-9+#&\._]+)", re.U) re_han_cut_all = re.compile("([\u4E00-\u9FD5]+)", re.U) |
到底有什么区别： 我写了个测试：
|
1 2 3 |
test_str = u'我在重庆abc,他也在重庆? 1234你在重庆吗' print (re_han_default.split(test_str)) print (re_han_cut_all.split(test_str)) |
输出：
|
1 2 |
['', '我在重庆abc', ',', '他也在重庆', '? ', '1234你在重庆吗', ''] ['', '我在重庆', 'abc,', '他也在重庆', '? 1234', '你在重庆吗', ''] |
上面输出的list 里面每一个被成为block。
细分
对粗分产生的blok ‘abc’这样的不能被re.han匹配的会直接作为结果反回。对于和中文连在一起的会进入下一个阶段细分。
DAG构建
细分的第一步是构建 DAG 即有向无环图。构建的核心代码如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 |
怎么个意思呢： 举个例子 我来到北京清华大学 产生的DAG 结果如下：
