jieba分词是Python 里面几个比较流行的中文分词工具之一。为了理解分词工具的工作原理，以及实现细节对jieba进行了详细的阅读。

读代码之前，我有几个问题是这样的：

分词工具的实现都有哪几个步骤?

结巴分词的文档说是使用了HMM模型，但是HMM 模型是如何运用在分词工具中的？，以及模型是如何产生的？

几乎所有的分词工具都支持用户添加词库，但是用户词库到底在分词过程中扮演什么角色？

简介

jieba 分词支持三种分词模式，官方文档给出了如下的Example

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

importjieba

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) ，所以在整个过程如果没有模型也是可以的，只要你有一个很好的词典。最大概率路径的求解还有很多方法，记得的求解就有实现最短路径。

粗分

首先会使用正则将文本切分，正则什么样？就跟现则的是默认模式还是全模式。正则如下：

Python

1

2

re_han_default=re.compile("([\u4E00-\u9FD5a-zA-Z0-9+#&\._]+)",re.U)

re_han_cut_all=re.compile("([\u4E00-\u9FD5]+)",re.U)

到底有什么区别： 我写了个测试：

Python

1

2

3

test_str=u'我在重庆abc,他也在重庆? 1234你在重庆吗'

print(re_han_default.split(test_str))

print(re_han_cut_all.split(test_str))

输出：

Python

1

2

['','我在重庆abc',',','他也在重庆','? ','1234你在重庆吗','']

['','我在重庆','abc,','他也在重庆','? 1234','你在重庆吗','']

上面输出的list 里面每一个被成为block。

细分

对粗分产生的blok ‘abc’这样的不能被re.han匹配的会直接作为结果反回。对于和中文连在一起的会进入下一个阶段细分。

DAG构建

细分的第一步是构建 DAG 即有向无环图。构建的核心代码如下:

Python

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

defget_DAG(self,sentence):

self.check_initialized()# 初始化，加载词典

DAG={}

N=len(sentence)

forkinxrange(N):

tmplist=[]

i=k

frag=sentence[k]

whilei

ifself.FREQ[frag]:

tmplist.append(i)

i+=1

frag=sentence[k:i+1]

ifnottmplist:

tmplist.append(k)

DAG[k]=tmplist

returnDAG

怎么个意思呢： 举个例子 我来到北京清华大学 产生的DAG 结果如下：

Python

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

使用dict 来存储图数据结构。字典中的key 是没个字对应句子的index,后面的value 是一个list就是可达的路径。比如{1：[1,2]}意思就是“来”和“来到”这两个词在词典中存在。其他的类推。

图的产生依赖于self.FREQ这个变量，这是存储字典的，其结构是词做key ,词出现次数做value 的dict. 所以词典的好坏对分词结果会有很大的影响。如果根本不存在的路径给连上了，应该连上的没有连上。后面的HMM模型也是没办法解决的后者，当然最大概率路径会解决部分第一个问题，但是都是有限的。所以词典是相当关键的。

最大概率路径求解

有了上面的DAG 下面求是求解最大概率路径。这个问题有很多中方法，jieba 使用的是动态规划。先不解释动态规划是什么，直接看代码，

Python

1

2

3

4

5

6

7

defcalc(self,sentence,DAG,route):

N=len(sentence)

route[N]=(0,0)

logtotal=log(self.total)

foridxinxrange(N-1,-1,-1):

route[idx]=max((log(self.FREQ.get(sentence[idx:x+1])or1)-

logtotal+route[x+1][0],x)forxinDAG[idx])

真个过程就上面几行。关键就在max 那一句。这个问题不在这里展开。但是有个小的技巧说下：在对很小的数据进行操作的时候，Python 也是可能向下溢出的，什么意思看下面的例子：

Python

1

2

b=0.0000001

printb**100

结果会打印0.0 所有有个方法就是取log 。这个方法在很多地方都是有用的。 上面还用到了连个tuple比较这一技巧。

求解的结果如果分词时候参数设置的不适用HMM模型，到这里就结束了。求解结果部分如下：key 同样是对应的index.第二个就代表的是来到这个词。

Python

1

{0:(-32.587853155857076,0),1:(-27.379629658355885,2),}

未登录词

上面的最大概率在一定程度上解决了歧义问题，但是在分词里面还有另外一个问题未登录词问题也叫OOV(Out Of Vocabulary). jieba 使用HMM来识别未登录词。 比如: “我来到誉存科技” 这句话，产生的最大概率路径是

Python

1

{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)}

看到3,和4 都是独立的词，如果不使用HMM 这个词就会被分成两个字。其逻辑就是把多个连续的单字组合成新的blok 使用HMM来切分。HMM到底怎么切分呢？

HMM

HMM 隐马模型的定义自己可以去查，就算查完你也不一定能说清楚到底在分词的时候怎么使用的，但是不查绝对不知道。 在分词之前语料会被标注，标注的方式有很多中。其中比较多的是BMES对应的是B(begin)词的开头,M(Middle)词的中间,E(End)词的结束,S(Single)单个的词 HMM有几个概念，和分词这个具体问题的对应关系如下：

状态序列(state sequence)：BMES 这些状态

观测序列(observation sequence)：就是看到的需要分词的句子，所有的字组成一个序列。

现在的问题就是一直观测序列求状态序列。但是第一部我们需要建立HMM模型。 HMM 有三个基本组成： 初始概率状态概率分布A 状态转移矩阵pi 观测概率分布B

如果有了上面三个元素一个HMM模型就是定好了。当然还有HMM模型有很多假设，此处省略。 jieba 是如何得到这三个变量的了。这就是HMM的学习问题 了。在标注好的语料之上。可以使用极大似然估计来估计这三个参数。这里也看到，语料是关键因素，语料的质量决定这三个参数。其实估计的过程不管其中的原理就是一些统计计算。jieba 把这三个元素分别存贮在三个py文件中：

prob_start.py: 初始状态概率 prob_trans.py： 状态转移 prob_emit.py： 观测概率分布

看看 prob_start:

Python

1

2

3

4

P={'B':-0.26268660809250016,

'E':-3.14e+100,

'M':-3.14e+100,

'S':-1.4652633398537678}

-3.14e+100表示的是无穷小。意思就是第一个字不可能是E，或者M.只可能是B,S具体是多少，使用语料中的频率做估计。

另外两个元素用类似的方法在语料之上很容易得到。

有了上面的饮马模型，但是如何通过观测序列求最有可能的状态序列?这时候就到Viterbi algorithm出场了。具体也不展开，反正很简单。