admin 管理员组文章数量: 1086019
2024年4月12日发(作者：命令执行漏洞工具)
算法语言
信息与电脑
China Computer & Communication
2020年第10期
中文分词技术研究
韦人予
（广西大学 计算机与电子信息学院，广西 南宁 530004）
摘 要：中文分词是自然语言处理的基础任务。随着文本数据量的增长，对中文分词进行研究具有十分重要的意义。
jieba分词是较为常用的中文分词技术，分词的准确率较高，面向jieba分词技术研究加快分词速度的方法，该方法采
用Cython实现分词技术的核心算法，对中文文本进行分词处理。在ICC中文数据集上进行实验，实验结果表明，该分词
加速方法能够提高63.9%的分词速度。
关键词：中文分词；自然语言处理；jieba分词
中图分类号：TP391.1 文献标识码：A 文章编号：1003-9767（2020）10-026-04
Research on Chinese Word Segmentation Technology
Wei Renyu
Abstract:
Chinese word segmentation is the basic task of natural language processing. With the growth of text data, it is of great
(College of Computer and Electronics Information, Guangxi University, Nanning Guangxi 530004, China)
significance to study Chinese word segmentation. Jieba word segmentation is a commonly used Chinese word segmentation technology,
which has a high accuracy rate. This paper studies the method to speed up word segmentation for Jieba word segmentation technology,
data set show that the method can improve the speed of word segmentation by 63.9%.
Key words:
chinese word segmentation; natural language processing; jieba segmentation
分词速度显得尤为重要。
which uses the core algorithm of the word segmentation technology of Python to segment Chinese text. Experiments on ICC Chinese
０ 引言
在信息时代，信息传播的方式更加丰富，各种信息数量
更是呈指数上升，我国今年的数据总量估计占全球数据总量
的21%
[1]
。中文的使用在全球越来越普及，面对海量的中文
数据，生活中对中文数据处理的技术需求不断增长，中文分
词作为文本处理的基础任务，具有重要的研究意义
[2]
。
与以空格为切分符号的英文分词不同，中文的基础单位
是彼此连在一起的词汇，中文正是通过词的组合来表达不同
的含义，但一样的组合也可能有不同的含义，这就是所谓的
歧义，例如，“他原来是学生”中的“原来”，看作名词时
意为他以前是学生，若看作副词则变为没想到他就是学生的
意思。中文分词是需要把一个个的汉字，以序列形式切分为
可以表达完整语义的词语。中文在语义、语法等方面的复杂
性，导致计算机想要高效理解中文语言更是艰难，所以中文
分词存在一定的难度。中文分词技术的准确性和分词速度都
很重要，面对庞大的数据量，在确保分词准确性的前提下，
１ Ｊｉｅｂａ分词技术
基于Python的jieba分词技术
[3]
是针对中文的概率语言
模型分词，其本身具有一个名为“”的词典，该词典
由人民日报等语料数据训练，拥有2 0000多个中文字词，每
一个字词都有根据训练语料统计的词频和词性。jieba分词的
流程如图1所示。
jieba分词技术涉及前缀树、有向无环图、动态规划、隐
马尔可夫以及维特比等多种算法
[4]
。由自带的词典生
成Trie树实现高效率的词图扫描，将所有可能的切分情况构
建有向无环图DAG，既节省空间又能快速查找；由生成的
DAG计算最大概率，动态规划查找最优路径，得到基于词频
的最优分词组合；对于词典没有登记的词，采用隐马
尔可夫模型来预测分词。
jieba对中文语句进行切分的时候，支持精确模式、全模
作者简介：韦人予(1994—)，女，壮族，广西宜州人，硕士研究生。研究方向：深度学习、多模态学习。
— ２６ —
2020年第10期
信息与电脑
China Computer & Communication
算法语言
中文语句
径、维特比3个分词技术的核心算法，利用Cython自身特性
达到提高分词速度的目的。
标注非汉字字符为未知词性
载入词典
以非汉字字符切分句子
2.1 有向无环图
有向无环图（Directed acyclic graph，DAG）指一个没
有环路的有向图。在对文本语句进行分词阶段，以词典dict.
txt为依据，整理句子中每一个汉字可以组合成词的所有可能
生成Trie树
生成分词的有向无环图DAG
计算全局概率Route找出
基于词频的最大切分组合
未登录词
是
否
按词典标注标识
情况，并生成有向无环图DAG。
句子sentence的长度为N，建立有向无环图DAG字典
{
idx
:[
x
i
]}
，
idx
表示每个汉字在句子sentence中的位置，记作
开始位置，该汉字为sentence[
idx
]，依次向右，将与位置
idx
相连的汉字与其组合成词汇word，若该词汇存在于词典dict.
txt中，则作为一种分词可能，返回该词汇的结束位置
x
i
，构
成有向无环图DAG字典。根据李昆仑等的研究结论，建立
有向无环图的流程的算法可描述如下
[6]
。
（1）输入：句子sentence
（2）输出：有向无环图DAG字典{开始位置
idx
:[结
束位置
x
i
]}
（3）
for
idx
←
0 to
句子sentence的长度
N do
（4）list ← [] ,
i
←
idx
, word ← sentence[
idx
]，DAG ← {}
（5）
while i
＜
N and word in
词典 do
（6）
i
add to list[i
]
（7）
i
←
i+
1
（8）word ← sentence[
idx
:
i+
1]
（9）
end while
（
10
）
if list
为空列表 do
（
11
）
idx add to list
（
12
）
end if
（
13
）字典DAG{
idx
} ← list
（
14
）
end for
（15）返回字典DAG
上述算法的时间复杂度为
O
(
N
2
)
，其中N为句子
sentence的长度。内循环while中，寻找
sentence中的汉字
在字典中的位置并记录下位置下标
i
需要执行N次；外循环
for中，遍历整个句子，需要循环N+1次，因此整个循环
需要执行
O
(
N
×（
N
+
1）
)
=
O
(
N
2
+
N
)
=
O
(
N
2
)
次；下面的
基本语句执行时间均为
O
(
1
)
，因此，整个算法的时间复
杂度为
O
(
N
×（
N
+
1）
)+
O
(
1
)+
O
(
1
)
=
O
(
N
2
+
N
)+2
O
(
1
)
否
中文
是
加载隐马尔可夫HMM模型
识别英文、数字以及时间
形式的组合并给予标注
维特比算法动态规划得
到分词和标注
分词结果
图1 jieba分词流程图
式、搜索引擎模式3种不同的分词模式。3种模式对中文语
句切分的情况如下所示。
例句1：游乐场里一个戴着帽子的女孩行走在旋转木
马旁
精确模式：游乐场/里/一个/戴着/帽子/的/女孩/
行走/在/旋转/木马/旁
全模式：游乐/游乐场/场里/一个/戴/着/帽子/的/
女孩/行走/在/旋转/木马/旁
搜索引擎模式：游乐/游乐场/里/一个/戴着/帽子/
的/女孩/行走/在/旋转/木马/旁
例句2：明亮的T台上一个衣着时尚的女人走在一个人
背后
精确模式：明亮/的/T台/上/一个/衣着/时尚/的/
女人/走/在/一个/人/背后
全模式：明亮/的/T/台上/一个/衣着/时尚/的/女人
/走/在/一个/个人/背后
搜索引擎模式：/明亮/的/T台/上/一个/衣着/时尚/
的/女人/走/在/一个/人/背后
精确模式顾名思义，就是将句子尽可能精确切分，是常
用的分词模式，最适用于文本分析；全模式，将列出所有可
能成词的词汇，分词速度在3种模式中是最快的，但是分词
结果具有歧义性，例如例句中的“一个人”，精确模式只分
为“一个”和“人”，而全模式分为“一个”和“个人”；
搜索引擎模式是以精确模式的分词结果为基础，对3元及以
上的长词再次切分，可以提高召回率
[5]
。
=
O
(
N
2
)
。
例如，句子“我们感到很开心”，生成句子的有向无环
图DAG，其位置字典DAG如下所示。
{0：[0,1]，1：[1]，2：[2，3]，3：[3]，4：[4]，5：[5，
6]，6：[6]}
字典的键值key为句子中的每一个汉字的位置索引，
value为可能组成词汇的结束位置，其中，{0：[0,1]}表示开
始位置
idx
=0时，即对“我”这一个汉字，在词典搜寻后就
有“我”和“我们”这两种分词可能，结束位置
x
i
为别为0
２ 分词的加速方法
面向jieba分词技术，针对中文分词技术存在分词速度
较慢的问题，采用Cython实现有向无环图、计算最大概率路
— ２７ —
算法语言
信息与电脑
China Computer & Communication
2020年第10期
和1。例句生成的有向无环图DAG如图2所示。
我们感到很开心
究结论，计算最大概率路径的流程的算法可描述如下
[7]
。
（1）输入：句子sentence，有向无环图字典DAG
{
idx
:[
x
i
]}
。
（2）输出：最大概率对数路径route{每个汉字位置
idx
:(概率对数最大值
P
，词汇结束位置
x
i
)}。
（3）
N
← 句子sentence长度，route ← {}
（4）句末汉字route{
N
}的值 ← (0,0)
（5）
for
idx
←
N
﹣
1,
N
﹣
2,…,0
do
（6）
for
x
i
←
DAG
{
idx
}
do
（7）概率
P
← ln(
count(word
))
-
ln
(
（8）
end for
（9）route{
idx
} ←
max
(
P
,
x
i
)
（10）
end for
（11）返回字典route
上述算法的时间复杂度为
O
(
N
2
)
，其中N为sentence
的长度。内层循环for倒序遍历最多执行N次；外层循
环for中，遍历整个sentence需要执行N次，基于此，
整个循环需要执行
O
(
N
×
N
)
=
O
(
N
2
)
次。而下面基本语句
的执行时间均为
O
(1)，因此，整个算法的时间复杂度为
O
(
N
2
)+
O
(1)=
O
(
N
2
)
。
例如，句子“我们感到很开心”由算法1得到有向无环
图DAG，位置字典形式为{0：[0,1]，1：[1]，2：[2，3]，3：[3]，
4：[4]，5：[5，6]，6：[6]}，以此计算最大概率路径。首先
设置位置7为句末标志，即(0，0)，概率对数和结束位置都
为0，计算开始位置
idx
为6的汉字“心”的最大概率，结束
位置
x
i
=6.
（2）
0123
图2 有向无环图
456
将所有可能的切分形式构建有向无环图，可知从句子开
始到句末之间存在多条路径，即存在多种分词结果。
2.2 计算最大概率路径
根据多种分词结果，在DAG中生成最短路径，即计算
最大概率路径。采用动态规划查找最大概率路径，从后往前
反向计算最大概率，将每一个汉字作为有向无环图的节点，
每到达一个节点，它前面的节点到终点的最大路径概率已知。
由算法1生成的DAG为
{
idx
:[
x
i
]}
，
idx
是开始位置，表
示每个汉字在句子sentence中的位置，
x
i
表示词汇的结束位
置，从句末倒序遍历句子sentence的每一个汉字，基于词频
计算
idx
的最大概率为：
count
(word)
+
P
(
x
+
1
)
P
(
idx
)
=
max
ln
i
∑
count
(
i
)
dict
.
txt
dict
.
txt
∑
count
(
i
)
)+
P
(
x
i
+1)
（1）
其中，count(word)表示可能的词汇组合word在词典
统计的词频，
dict
.
txt
∑
count
(
i
)
表示词典所有词频的和，
P
(
x
i
+1)是位置
x
i
+1作为开始位置时的最大路径概率，采用对
数值计算，防止下溢问题，最后将最高的概率对数得分以
(P(idx),xi)元组形式返回字典route中。根据Bellman等的研
count
‘
(
心’
)
25236
+
P
(
句末标志
)
=ln
+
0=
−
7.7755263022645185
ln
∑
count
(
i
)
6010196
7
所以“心”最高的概率对数得分在字典route保存{6:(-
7.7755263022645185,6)}。
继续向前计算开始位置
idx
为5的汉字“开”，它有两
个分词组合“开”和“开心”，由公式（1）计算开始位置为“开”
的最大概率路径，此时结束位置
x
i
=6，
x
i
+1=7，计算词汇“开
心”的概率。
（3）
count
‘
(
开心’
)
+
P
(
句末标志
)
=ln
487
+
0
=
−
11.72328900467263
ln
∑
count
(
i
)
60101967
另一种分词可能，结束位置
x
i
=5，计算词汇“开”的概率，结束位置
x
i
+1=6。
（4）
count
‘
(
开心’
)
+
P
(
句末标志
)
=ln
487
+
0
=
−
11.72328900467263
ln
∑
count
(
i
)
60101967
所以开始位置
idx
为5的汉字“开”的两种可能分词概
率为-11.723 289 004 672 63和-15.450 697 462 210 28，选
择概率最大的分词，即“开心”而不是“开”，所以开始
位置为“开”的最高概率对数得分在字典route中保存{5:(-
11.72328900467263,6}；以此类推，反向计算最大概率路径，
由局部最优路径得到全局最优路径，最终得到基于词频的最
大切分组合为[‘我们’,‘感到’,‘很’,‘开心’]。
2.3 维特比算法
无论是生成有向无环图还是查找最短路径，都是处于词
汇在词典中有记录的前提下切分，对于词典未记录的
词，需要识别并调整分词结果，该阶段也称为新词发现。
新词发现采用隐马尔可夫（Hidden Markov model，
HMM）模型，该模型主要解决概率计算问题，参数学习问题，
预测问题这三类问题。例如单个字‘真’‘好’‘啊’存在
— ２８ —
2020年第10期
信息与电脑
China Computer & Communication
算法语言
于词典中，但是组合后的‘真好啊’是未记录在词典中的词
汇，对于连续组合为词汇但是不在词典中的连续单字，就要
由HMM模型进行新词发现。
新词发现是一个HMM的预测问题，给定一个句子视为
观测序列
O=(O
1
,O
2
,…,O
T
)
，句子中的每个汉字看作是一个
观测值，分词结果标记为隐藏状态序列，采用Viterbi算法进
行求解，找到最佳的状态序列，然后再根据状态序列输出分
词结果。
HMM的观测概率矩阵表示为，
B=
[
b
ij
]
n
×
m
其中
现有向无环图DAG、计算DAG的最大概率路径、Viterbi这
三个核心算法，达到加快分词速度的目的。
３ 实验与结果分析
3.1 数据集
本文用于分词实验的数据集是来自于2017年AI
Chanllenger比赛的ICC数据集。该数据集属于规模较大的
图像描述任务数据集，其训练集的中文描述语句数量为105
000 0句。
3.2 结果分析
实验使用分词的加速方法和jieba分词方法分别对ICC
训练集的所有中文描述语句进行分词，分词结果如表1所示。
表1 分词结果
分词技术
jieba
分词的加速方法
分词速度/s
147
53
分词结果/个
17 625
17 621
b
ij
=
P(M
j
|
N
i
)
；转移概率矩阵表示为
A=
[
a
ij
]
n
×
m
，其中
a
ij
=
P(N
j
|
N
i
)
，N表示所有可能出现的隐藏状态集合，M表示
所有可能出现在观测中的表现状态集合，除此之外，HMM
还具有初始状态概率矩阵
π
。
采用Viterbi算法求解实质是一种动态规划最大概率寻找
法，根据动态规划原理，若全局最优路径在t时刻通过节点
i′
t
，
那么从
i′
t
到终点
i′
T
的路径一定是最优的。所以从初始状态开
始，在每个时刻求节点
i
所有局部路径的最大概率，再进行
递推可以求得时刻
t
=
T
状态为
i
的各条路径的最大概率。对
从表1可知，同样处理ICC数据集的中文描述语句，分词的
加速方法比jieba分词速度提高了63.9%，虽然分词结果总数
少了4个词汇，但是在17 625个词汇中减少的4个词汇，其
中3个是只在数据集中出现过一次的词汇，1个是只出现过
2次词汇，都属于低频词，所以分词结果的影响可以忽略不计。
实验结果表明，采用Cython实现分词技术核心算法的方法，
可以提高分词速度并且对分词结果的影响较小。
I=[
i
1
,
i
2
,…,
i
t
]
表示t时刻节点
i
的所有局部路径，最大概率为：
δ
t
(
i
)
=
max
P
(
i
t
=
i
,
i
t
−
1
,...,
i
1
,
o
t
,...,
o
1
|
λ
)
,
i
=
1,2,...,
N
（5）
I
由此可得变量δ的递推公式为：
δ
t
+
1
(
i
)
=
max
P
(
i
t
+
1
=
i
,
i
t
,...,
i
1
,
o
t
+
1
,...,
o
1
|
λ
)
I
=
max[
δ
t
(
j
)
∗
a
ji
]
∗
b
i
(
o
t
+
1
)
1
≤
j
≤
N
（6）
其中
i=1,2,……N
，
t=1,2,……N
。
在t时刻节点
i
的所有单个路径(
i
1
,
i
2
,…,
i
t-1
,
i
)中概率最
大路径的第t-1个节点为：
４ 结 语
本文面向jieba分词技术介绍分词技术的原理，采用
Cython实现有向无环图、计算最大概率路径和维特比3个分
词技术的核心算法，利用其运行速度快的特点达到加快分词
（7）
的目的。实验结果表明了该中文分词加速方法的有效性。
δ
t
−
1
(
j
)
∗
a
ji
ϕ
t
(
i
)
=
argmax
1
≤
j
≤
N
由已知的初始状态概率矩阵、观测概率矩阵和转移概率
矩阵，当
t
=1时初始化：
δ
1
(
i
)=
π
i
*b
i
(o
1
),
i
=1,2,…N
φ
1
(
i
)=0,
i
=1,2,…N
时刻
t
=
T
的最大概率就是最优路径的概率：
（8）
（9）
（10）
周报,2020-03-16(007).
参考文献
[1]梅宏.大数据:发展现状与未来趋势[N].中国信息化
[2]唐琳,郭崇慧,陈静锋.中文分词技术研究综述[J].
数据分析与知识发现,2020,4(1):1-17.
[3]LIN C H,LIU J C,HO C y Detection Using
LibSVM Training Tools[C]//2008 International Conference on
Information Security and Assurance,2008:166-171.
[4]曾小芹.基于Python的中文结巴分词技术实现[J].信
息与电脑:理论版,2019,31(18):38-39,42.
[5]祝永志,荆静.基于Python语言的中文分词技术的研
究[J].通信技术,2019,52(7):1612-1619.
[6]李昆仑,黄厚宽,田盛丰.一种基于有向无环图的多
类SVM分类器[J].模式识别与人工智能,2003(2):38-42.
[7]Bellman,Richard Ernest,Dreyfus,et c
programming[M].New York:Dover Publications,2003.
Pi
T
'
=
max
δ
(
i
)
1
≤
j
≤
N
()
同时也得到了最优路径的终结点：
i
T
=
argmax
δ
T
(
i
)
'
1
≤
i
≤
N
（11）
为了找出最优路径的各个节点，从最终结束位置
i′
T
开始，
由后向前逐步求得结点：
i′
t
=
φ
t
+1
(
i
) （12）
其中，
t
=
T
﹣1,
T
﹣2,…1
。最终获得一个状态序列，即
通过回溯得到最优路径
I
′=(
i′
1,
i′
2,
…,
i′
T
)。
上述算法的时间复杂度为
O
(
N
2
T
)，其中N为句子序列长
度，T为隐藏状态序列长度。
Cython结合了Python的易用、快速开发和C语言运行
速度快的特点。在jieba分词技术的基础上，采用Cython实
— ２９ —
版权声明：本文标题：中文分词技术研究 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1712895836a611308.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论