Peiqin Lin's Homepage

jieba 源码阅读笔记（一）

2018/12/12 ArtificialIntelligence

jieba 初始化

jieba 自 0.28 版后就开始采用了延迟加载机制，jieba 在初始化的时候会创建一个Tokenizer实例dt，此实例在创建时不会构建词频字典，它定义了一个描述当前初始化情况的变量self.initialized，并在初始化时，设置其为False。因此当我们导入 jieba 时，词典并不会被加载，只有当我们使用 jieba 的具体功能的，dt实例才会调用check_initialized(self)函数，判断initialized变量是否为True，如果不是，则会调用initialize(self, dictionary=None)函数，实行初始化。

初始化过程主要加载词频文件，返回词频字典self.FREQ（key 为词，value 为词频，可用jieba.get_FREQ(k)搜索对应词的词频）和词频总和self.total。

如果我们要手动初始化 jieba，可以手动调用jieba.initialize()进行初始化。

Trie 树

根据词频字典self.FREQ，jieba 可以将一个句子转换为一个有向无环图（DAG），而这其中利用到的一个重要数据结构就是 Trie 树（原始版本直接实现 Trie 树，现有版本借鉴思想，将前缀树存储在文件中）。

Trie 树，又叫字典树或前缀树，是一棵多叉树。Trie 树一般用来统计、排序和保存字符串，具体的应用包括词频统计、前缀匹配和自动补全。当字符串量级大、字符串过长的时候不适合用 Trie 树。Trie 树的常用操作是查找和插入，时间复杂度为 \(O(m)\)，其中 \(m\) 是待插入/查询的字符串，删除操作很少用。

Trie 树有 3 个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
  3. 每个节点的所有子节点包含的字符都不相同

词频字典self.FREQ实际上就是以 Trie 树的思想存储的，每个词的前缀都保存在文本中，对于没有在分析文本中独立出现的前缀词，词频记为 0。

获取 DAG

jieba 通过调用get_DAG(self, sentence)来获取每个字符基于 Trie 树的有向无环图（DAG），我们以官方样例“我来到北京清华大学”来进行研讨。

get_DAG(self, sentence)返回一个 DAG 字典（key 为每个字符，value 为字符对应的 DAG，{0:[0, 1]} 就是一个简单的例子），对于上面的这个句子，得到的字典为{0: [0], 1: [1, 2], 2: [2], 3: [3, 4], 4: [4], 5: [5, 6, 8], 6: [6, 7], 7: [7, 8], 8: [8]}，其中位置 5（即“清”）的 DAG 是[5, 6, 8]，之所以跳过 7（即“大”），是因为“清华大”出现在字典中（表明拥有其作为前缀的词），但词频为 0（表示前缀没有单独出现在统计文本中）。

全模式

使用 jieba 的全模式（把句子中所有的可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义）的案例代码如下：

import jieba
seg_list = jieba.cut("我来到北京清华大学", cut_all=True)
print("Full Mode: " + "/ ".join(seg_list))  # 全模式

在 jieba 中，全模式实现的函数为__cut_all(self, sentence)，其具体实现思路是：

  1. 遍历每一个字符i
  2. 如果当前字符i的 DAG 中只有自己一个字符，判断其是否已被前面 DAG 包括，如果是跳过，如果不是，则输出
  3. 如果当前字符i的 DAG 包括多个字符，则遍历其后面的每个字符j，将区间[i, j]内的字符合并成词输出

基于词频的最大切分组合

jieba 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合，具体实现函数是calc(self, sentence, DAG, route)。

对于一个句子中的每个字符，根据其 DAG，我们可以得到从其开始进行切分的所有可能，那么到底哪个可能是最大的呢？这与后面的切分情况有关，因此，jieba 采用了自底向上（即从后往前）的动态规划算法，其状态转移方程为： \(r_i = \max_{(i, j) \in E}{r_j+w(i, j)}\) 其中 \(r_i\) 表示当前字符的最大切分对数概率，\(E\) 表示根据 DAG 生成的切分词集合，遍历集合中的每一个元素，计算当前切分词对数概率 \(w(i,j)\) 和下一个字符开始切分的最大对数概率 \(r_j\) 之和（为防止浮点数相乘下溢，通过取对数的方式将相乘转换为相加）的最大值。在calc(self, sentence, DAG, route)函数中，具体的实现如下：

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])

精确模式

使用 jieba 的精确模式（试图将句子最精确地切开，适合文本分析）的案例代码如下：

import jieba
seg_list = jieba.cut("我来到北京清华大学", cut_all=False)
print("Default Mode: " + "/ ".join(seg_list))  # 精确模式
seg_list = jieba.cut("他来到了网易杭研大厦")  # 默认是精确模式

在 jieba 中，精确模式有两种实现方案，分别是运用 HMM （默认方案）和不运用 HMM 的，分别对应的函数为__cut_DAG(self, sentence)和__cut_DAG_NO_HMM(self, sentence)，两种方案的主要区别在于前者运用了 HMM 和 Viterbi 算法来识别新词（即遇到多个单字连续出现）。此部分的代码在finalseg中实现，具体分析将留在之后的 jieba 源码阅读之中。

搜索引擎模式

使用 jieba 的搜索引擎模式（在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词）的案例代码如下：

import jieba
seg_list = jieba.cut_for_search("小明硕士毕业于中国科学院计算所，后在日本京都大学深造")  # 搜索引擎模式
print(", ".join(seg_list))

上述例子在精确模式下的分词结果为：

小明, 硕士, 毕业, 于, 中国科学院, 计算所, ，, 后, 在, 日本京都大学, 深造

在搜索模式下的分词结果为：

小明, 硕士, 毕业, 于, 中国, 科学, 学院, 科学院, 中国科学院, 计算, 计算所, ，, 后, 在, 日本, 京都, 大学, 日本京都大学, 深造

在 jieba 中，全模式实现的函数为__cut_for_search(self, sentence)，在精确模式的基础上，搜索模式主要的操作有：

  1. 对于长度大于 2 的词，以长度为 2 为单位捕获子串，如果子串在词频文件里词频值不为 0，则返回
  2. 对于长度大于 3 的词，以长度为 3 为单位捕获子串，如果子串在词频文件里词频值不为 0，则返回

补充

上述的代码都在jieba.__init__中实现，这个文件中还有一些有趣的内容：

  • lcut()和lcut_for_search()分别与cut()和cut_for_search()对应，只不过前者返回list，后者返回generator。
  • 这部分提供了load_userdict(self, f)来让用户指定自定义词典，也提供了add_word(self, word)和del_word(self, word)来让用户修改词典，还提供了suggest_freq(self, segment)来让用户调整单个词语的词频。
  • 这部分还提供了tokenizer(self, unicode_sentence)来返回分词结果中每个词的起始位置和终止位置，以及并行分词等操作，感兴趣的读者可以自行了解。

Search

    Table of Contents