jieba分词代码原理分析

开头

本文只是jieba代码的一个粗略阅读笔记：

1. 由于jieba过于工程化的原因，很多逻辑包在其中必须一层一层拨开，本人在想看分词思路的同时，也突然想看看其工程化的代码，此文档为学习内容记录，所以内容比较琐碎。

2. 本人主要参考jieba注释代码：

   https://github.com/fxsjy/jieba

3. jieba原作者代码网址：( 可以看看其项目issue,里面可以解答很多问题)

   https://github.com/fxsjy/jieba

4. 本人只是看了分词部分，对整体有了大致认识，完整个人实现并没有去做。

5. 许多为了理解代码的测试（print）部分个人没有展示。

数据结构

​ 解释：jieba分词由于版本更迭问题，原先是Trie数据结构构建词典，但是后来改为了前缀词典，本人最开始不清楚，所以还去简单了解了波Trie数据结构。

Trie数据结构视频：

https://www.bilibili.com/video/av58431163?from=search&seid=6738684812450955423

项目讨论

jieba项目问题讨论（里面有很多问题能帮助了解Jieba作者的思路历程）:

https://github.com/fxsjy/jieba/issues

介绍

参考：https://blog.csdn.net/daniel_ustc/article/details/48195287

• 特点

  1.支持三种分词模式：
  ​ a. 精确模式，试图将句子最精确地切开，适合文本分析；
  ​ b. 全模式，把句子中所有的可以成词的词语都扫描出来, 速度非常快，但是不能解决歧义；
  c. 搜索引擎模式，在精确模式的基础上，对长词再次切分，提高召回率，适合用于搜索引擎分词。
  2.支持繁体分词
  3.支持自定义词典

  4.MIT 授权协议

• 功能：

  1.分词；

  2.添加自定义词典(开发者可以指定自己自定义的词典，以便包含 jieba 词库里没有的词)；

  3.关键词提取；

  4.词性标注；

  5.并行分词；

  6.ChineseAnalyzer for Whoosh 搜索引擎等

项目结构

.
├── analyse 提供了TF-IDF算法和textrank算法相关的实现
│ ├── analyzer.py
│ ├── idf.txt
│ ├── init.py
│ ├── textrank.py
│ └── tfidf.py
├── _compat.py 处理python2和python3之间差异的一个文件
├── dict.txt 记录了大约350000个词语的词频和词性
├── finalseg 提供了隐马尔科夫维特比算法相关的代码，用于未登录文本切词
│ ├── init.py HMM解决未登录词主要逻辑代码
│ ├── prob_emit.p 发射概率 参数存储文件
│ ├── prob_emit.py
│ ├── prob_start.p 初始状态分布 参数存储文件
│ ├── prob_start.py
│ ├── prob_trans.p 转移概率 参数存储文件
│ └── prob_trans.py
├── init.py !!!结巴分词提供的功能接口,主要代码都在其中
├── main.py
└── posseg
​ ├── char_state_tab.p
​ ├── char_state_tab.py
​ ├── init.py
​ ├── prob_emit.p
​ ├── prob_emit.py
​ ├── prob_start.p
​ ├── prob_start.py
​ ├── prob_trans.p
​ ├── prob_trans.py
​ └── viterbi.py

3 directories, 26 files

格式：行内空格出现了问题…看着好乱

init 和 mian的区别

https://www.tuicool.com/articles/iYRfe2

​ init.py是 python 解释器将当前文件夹作为 package 处理的必要条件。如果没有读取到init.py ，python 就不会认为当前的文件夹是一个 package，而只是把它当作普通文件夹来处理。

​ 如果你需要 python 讲一个文件夹作为 package 执行，那么这个文件夹中必须包含一个名为 __main__.py 的文件，当执行 python -m hhlb 或者 python hhlb 的时候，这个文件中的代码都会被执行。

个人理解为对应了两种调用模式：

1. 按照包调用，在其他文件内import进来测试，init起作用。

2. 直接运行此工程时，main起作用。

3. 具体测试项目方法参考：

   README_jieba.txt

logging模块

https://blog.csdn.net/liuchunming033/article/details/39080457

​ 对应于日志模块

——name——

https://blog.csdn.net/yjk13703623757/article/details/77918633

__name__是内置变量，可用于表示当前模块的名字

——repr——

https://lotabout.me/2018/QQA-Python-str-vs-repr/

​ Tokenizer类中碰到了这个方法，从没见过，此方法类似与规定输出格式，生成的字符串一般用于 debug。

gen_pfdict()

作用：(比较重要的函数)

1. 输入字典文件,该函数将文件内数据逐行读入（词：词频），存入字典中。
2. 且每读一行都判断，读进来的词，其前缀在不在词典内，不在的话词典内加入该前缀，词频置0,如下代码：

for ch in xrange(len(word)):# 处理word的前缀

	wfrag = word[:ch + 1]  # 词的前缀
    if wfrag not in lfreq: # word前缀不在lfreq则前缀其出现频次置0
        lfreq[wfrag] = 0
1
2
3
4
5

这就是所谓的前缀词典

---

initialize()

1.函数如其名，作用为初始化。

2.不考虑具体细节的话，该函数主要作用是（如果没有则）创建一个缓存词典，存入数据。（如果有）读出缓存词典的内容,不太清楚为什么用一个缓存词典…

---

——init——

是结巴分词的核心，里面提供了分词的接口：cut。它有三种模式：

1. 全模式，把句子中所有在词库中出现的词都找出来
2. 不使用隐马尔科夫模型的精确模式，基于最大概率路径, 找出基于词频的最大切分组合
3. 同时使用最大概率路径和隐马尔科夫模型，对于未登录词也有比较好的切分效果

---

cut函数

下面只显示了两种分词结构，另一种其实就是cut_DAG去了HMM,这三种切词结构分别包含于下面函数。

第一步：jieba分词，会先用正则对句子进行粗略分词：

        # 不同模式下的正则
        if cut_all:
            re_han = re_han_cut_all
            re_skip = re_skip_cut_all
        else:
            re_han = re_han_default
            re_skip = re_skip_default
1
2
3
4
5
6
7

（参考：http://midday.me/article/003023dc3f814bc493b37c50b2a9ee71）

---

第二步：对每一个bolock如何分块的方法：

（具体每个函数功能见下文）

# 设置不同模式下的cut_block分词方法
        if cut_all:
            cut_block = self.__cut_all
        elif HMM:
            cut_block = self.__cut_DAG
        else:
            cut_block = self.__cut_DAG_NO_HMM
1
2
3
4
5
6
7

正式切词开始

get_DAG()

这个函数的作用很简单：

​ 一个句子里，每一个字可以和相邻的那些字组合成词（此词在前缀词典中），所有情况都保存下来。

    # DAG中是以{key:list,...}的字典结构存储
    # key是字的开始位置
    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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

这里举例子比较容易懂：

​ 如果sentence是’我来到北京清华大学‘，那么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]}

​ 直观上来看，DAG[5]=[5,6,8]的意思就是，以’清‘开头的话，分别以5、6、8结束时，可以是一个词语，即’清‘、’清华‘、’清华大学‘，而实现这个功能的前提是有一个完备的前缀词典：self.FREQ（构建见上文）。

---

__cut_all

功能：所有可能的词都切出来

    def __cut_all(self, sentence):
        dag = self.get_DAG(sentence)
        old_j = -1
        for k, L in iteritems(dag):
            if len(L) == 1 and k > old_j:
                yield sentence[k:L[0] + 1]
                old_j = L[0]
            else:
                for j in L:
                    if j > k:
                        yield sentence[k:j + 1]
                        old_j = j
1
2
3
4
5
6
7
8
9
10
11
12

调用

import jieba

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

结果

​ Full Mode: 我/ 来到/ 北京/ 清华/ 清华大学/ 华大/ 大学

---

calc（）

最大概率路径求解

     #动态规划，计算最大概率的切分组合
    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([ (概率对数，词语末字位置) for x in DAG[idx] ])
           # 以idx:(概率对数最大值，词语末字位置)键值对形式保存在route中
           # route[x+1][0] 表示 词路径[x+1,N-1]的最大概率对数,
           # [x+1][0]即表示取句子x+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])
1
2
3
4
5
6
7
8
9
10
11
12
13
14

此函数作用展示：（根据结果容易懂函数作用）

输入：我来到北京清华大学

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

route {

0: (-32.587853155857076, 0),

1: (-27.379629658355885, 2),

2: (-24.22732015246924, 2),

3: (-18.548194315526874, 4),

4: (-20.20431518448597, 4),

5: (-11.085007904198626, 8),

6: (-17.53722513662092, 6),

7: (-8.006816355818659, 8),

8: (-8.142626068614787, 8),

9: (0, 0)}

Full Mode: 我/ 来到/ 北京/ 清华大学

__cut_DAG

​ 1. 代码很长，其实到此函数无非是前面那些功能函数的组合实现。复杂点在于代码逻辑，(本人尝试自己用print的方式，把关键变量打印出来理解)。

2 . 这里关键：未登录词的处理，代码利用finalseg来实现

    def __cut_DAG(self, sentence):
        DAG = self.get_DAG(sentence)
        route = {}
        self.calc(sentence, DAG, route)
        x = 0
        buf = ''
        N = len(sentence)
        print("route",route)
        while x < N:
            y = route[x][1] + 1
            l_word = sentence[x:y]

            if y - x == 1:
                buf += l_word  # buf(缓存)收集连续的单个字
            else:
                if buf:
                    # 如果是单个字
                    if len(buf) == 1:
                        yield buf
                        buf = ''

                    # 未登录词
                    else:
                        # 当遇到一些dict.txt中没出现的词的时候，才会进入这个函数
                        if not self.FREQ.get(buf):# 未登录词,利用HMM
                            recognized = finalseg.cut(buf)
                            for t in recognized:
                                yield t
                        else:
                            for elem in buf:
                                yield elem
                        buf = ''

                yield l_word

            # 移动x
            x = y

        if buf:
            if len(buf) == 1:
                yield buf
            elif not self.FREQ.get(buf): # 未登录词,利用HMM
                recognized = finalseg.cut(buf)
                for t in recognized:
                    yield t
            else:
                for elem in buf:
                    yield elem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

finalseg

​ 首先，此文件是利用HMM来解决未登录词的问题。

1. 作者设置其隐状态为：BMES，分别表示这个字在一个词中的位置（开头，中间，结尾，独立）
2. 有了观察序列（句子），有了隐状态（BMES）,再加上作者预训练好的HMM的参数（初始概率,转移概率,发射概率），利用经典的Viterbi算法,求得这个句子中，使得句子概率最大的隐状态序列。（前面说过，每一个隐状态对应一个字，有了这个序列，意味着知道了这个字到底代表什么: “B“ or ”M“ or ”S“ or ”E”）
3. 输入的句子可依据求得的每一个字的隐状态来进行分词分词。

至此，虽然jieba项目里还有很多代码没看，但主要想看的分词代码基本结束

参考

[1] 纯粹解释

http://www.voidcn.com/article/p-bgvtrzjf-rp.html

[2]较为简洁

http://midday.me/article/003023dc3f814bc493b37c50b2a9ee71

[3] 稍微多点的源码

https://segmentfault.com/a/1190000016888700

[4] 项目介绍

https://www.twblogs.net/a/5b7fde122b717767c6b22b6e/zh-cn