结巴中文分词解析

“做最好的 Python 中文分词组件”

[TOC]

1 介绍

1.1 Github地址

Github地址：https://github.com/fxsjy/jieba

image.png

截至2020年，11月，已有24.7K个星，下载6K次。其影响力和活跃度可见一斑。

1.2 功能

分词

添加自定义词典

关键词提取

词性标注

返回词语在原文的起止位置

等等。

2 分词原理分析

image.png

图片来源于：https://blog.csdn.net/qq_17336559/article/details/81147074。图画的非常清晰，所以借来引用，如有侵权，请告知，会立刻删除。

image.png

分词处理流程

2.1 构造前缀词典

****统计词典：****

jieba-master/jieba/dict.txt为已经统计词频的统计词典。统计词典的第一列为被统计词（γ射线）; 第二列为词频（“γ射线” 出现了3次),即词的统计出现次数;第三列为词性。程序初始化的时候会加载统计词典(代码位置：jieba-master/jieba/init.py Tokenizer::initialize)。

行号	词	词频	词性
144481	我	328841	r
216546	然	3720	c
217848	爱	14878	v
269791	自	33152	p
270349	自然	20269	d
270400	自然语言	46	l
287794	言	9691	vg
291367	语	4563	ng
291459	语言	7647	n
	处
	处理

表统计词典中的片段截取

构造前缀词典：

前缀词典构造如下，它是将在统计词典中出现的每一个词的每一个前缀提取出来，统计词频，如果某个前缀词在统计词典中没有出现，词频统计为1。

比如统计字典中有如下单词(根据字典的实际排序调整)：

句子	我	爱	自	然	语	言	处	理
下标	0	1	2	3	4	5	6	7

构造出的前缀字典如下：

关键词	前缀词	存储
0	[我]	[0]
1	[爱]	[1]
2	[自,自然,，自然语言]	[2,3,5]
3	[然]	[3]
4	[语,语言]	[4,5]
5	[言]	[5]
6	[处，处理]	[6,7]
7	[理]	[7]

构成的有向无环图DAG******(******Directed A******cyclic G******raph******)

image.png

2.2 寻找最大路径

从上述的DAG，我们需要找到一条从开始到结束的最大路径。系统实现中采用动态规划从句子末端往前，逐步去寻找每一步的最优解。每一步的处理伪代码如下：

results = []
for x in 前缀词列表:
# 查找当前词/字在FREQ中的对应值(频数)
req = self.FREQ.get(sentence[idx:x + 1])
  log_freq = log(freq or 1)
  # 计算频率对数(log_freq - logtotal = log(freq/total)) 为当前节点的值
  # + route[x+1][0] 为当前节点到句子末尾的总长度
  cur_route = log_freq - logtotal + route[x+1][0]
  results.append((cur_route, x))
# 选择一个cur_route 最大的元素
route[idx] = max(results)

名称	前缀词列表	计算过程（选择一个最大值）	结果（最大值单词的索引）
Route7	[理]	freq(理)/totoal + 0	7 (理)
Route6	[处，处理]	freq(处)/totoal + route7和freq(处理)/totoal + route7
Route5	[言]	freq(言)/totoal + route6
Route4	[语,语言]	freq(语)/totoal + route5和freq(语言)/totoal + route5
Route3	[然]	freq(语)/totoal + Route4
Route2	[自,自然,，自然语言]	freq(自)/totoal + Route3和freq(自然语言)/totoal + Route3
Route1	[爱]	freq(爱)/totoal + Route2
Route0	[我]	freq(我)/totoal + Route1

动态规划的规则：从一个最基本的问题出发，逐步记录每个阶段的解。

引用作者原文的解释：”算法：*****采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合**”

· 采用了动态规划查找最大概率路径, 找出基于词频的最大切分组合

2.3 标记未登陆词

引用作者原文的解释："算法：对于未登录词，采用了基于汉字成词能力的 HMM 模型，使用了 Viterbi 算法"

HMM(Hidden Markov model)隐马马尔可夫模型

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。

随机生成的状态序列，称为状态序列(state sequence)，设Q是所有状态的集合, n是可能的状态数
$Q={ q1,q2,d3,qn }$
每个状态生成一个观测，由此产生的观测的随机序列，称为观测序列(observation sequence).，V是所有可能的观测的集合,m是可能的观测数
$V={v1, v2, ...,vm}$
I是长度为T的实际的状态序列，O是对应的观测序列
$I=(i1,i2,...,iT), O=(o1,o2,...,oT)$

A是状态转移矩阵:
$A=[aij]N*N 其中 aij=p(it+1 = qj|it=qi), i=1,2,...N;j=1,2...N是时刻t处于qi状态，在时刻t+1转移到qj状态的概率$
B是观测矩阵：
$B=[bj(k)]N*M 其中bj(k)=P(ot=vk|it=qj), k=1,2...,M; j=1,2,...,N，在时刻t处于状态qj的条件下生成观测状态VK的概率$