jieba分词器：揭秘自然语言处理的神秘面纱

大家好，欢迎来到IT知识分享网。

在阿里开源的havenask引擎中涉及到的分词器，包括单字分词器、简单分词器和jieba分词器

• 单字分析器（chn_single）按单字/单词分词，适合非语义的中文搜索场景
• 简单分析器（simple）使用空格“ ”对字段内容（或查询词）进行分隔
• Jieba分析器（jieba_analyzer）基于开源的jieba分词器实现

本文重点介绍jieba分词器

01 开源分词组件对比

组件

VS准确度

VS性能

jieba虽然分词的精确度略逊于其他分词器，但性能上却遥遥领先，故获得了在多个方面的应用

jieba分词器有全模型、精确模型、搜索引擎模式和paddle模式（基于PaddlePaddle深度学习框架）

02 jieba分词器实现步骤

jieba分词器的实现逻辑如下：

第一步：jieba基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能成词情况所构成的有向无环图

第二步：针对产出的有向无环图采用动态规划查找最大概率路径, 找出基于词频的最大切分组合

第三步：对于未登录词，采用基于汉字成词能力的 HMM 模型中的Viterbi 算法将词标注为BMES等序列，然后按序列进行划分

说明：B（开头）、M（中间）、E（结尾）、S（独立成词）

步骤成图如下：

03 基于前缀词典分词

前缀词典使用Trie树实现，Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间为O（n * k），其中n为节点数

以“我喜欢南美洲”这句话为例，调用jieba的get_DAG函数，则会基于前缀树生产有向无环图，见下图的sentence_dag，然后则根据动态规划在该有向图环图中查找最大概率路径，最后根据概率值进行切词。

如上图，0-0的概率大则0单独成词，1-2的概率大则1-2成词，3-5的概率大则3-5成词，即整个句子被分为：我/喜欢/南美洲

这里涉及到动态规划的概念，先简单说下动态规划

动态规划

从一个例子开始：array = [1,5,2,4,3]，需从中找出最长增长序列的长度（如1,2,4或1,2,3，长度则为3）

第一种方法：暴力穷举法

对应的穷举法的代码如下：

算法的时间复杂度是n*2的n次方，进一步优化该算法，在穷举的过程中有大量重复的计算，可采用空间换时间的方法，将中间结果记录下来，让后续再计算的时候可直接读取使用，那么就引入了第二种方法

第二种方法：记忆化搜索

将中间结果存储下来，这样就不需要对这些树节点做重复计算啦，上述的写法是以递归的形式，可将其改为迭代形式

第三种方法：迭代形式

迭代的形式可更加直观的分析算法的复杂度，并且避免了递归时的函数调用开销

时间复杂度为n方

那么，上述的三种不同的算法演进，则是动态规划的一般思路，核心是空间换时间

04 HMM 模型&Viterbi算法

该方法属于由字构词的分词方法，由字构词的分词方法思想并不复杂，它是将分词问题转化为字的分类问题（序列标注问题）。从某些层面讲，由字构词的方法并不依赖于事先编制好的词表，但仍然需要分好词的训练语料。

规定每个字有4个词位：- 词首 B – 词中 M – 词尾 E – 单字成词 S

由于HMM是一个生成式模型，X为观测序列，Y为隐序列。基于HMM的两个假设 – 齐次马尔科夫性假设，即假设隐藏的马尔科夫链在任意时刻t的状态只依赖于其前一时刻的状态，与其它时刻的状态及观测无关，也与时刻t无关；- 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其它观测和状态无关，

HMM模型中的五元组表示：- 观测序列 – 隐藏状态序列 – 状态初始概率 – 状态转移概率 – 状态发射概率

HMM模型有三个基本问题：

• 概率计算问题，HMM的五元组，计算在模型下给定隐藏序列Y，计算观测序列X出现的概率也就是Forward-backward算法；
• 学习问题，已知观测序列{X}，隐藏序列{Y} ，估计模型的状态初始概率，状态转移概率和状态发射概率 ，使得在该模型下观测序列X的概率尽可能的大，即用极大似然估计的方法估计参数；
• 预测问题，也称为解码问题，已知模型状态初始概率，状态转移概率和状态发射概率和观测序列X，求最大概率的隐藏序列Y。

其中，jieba分词主要中主要涉及第三个问题，也即预测问题计算方法会涉及到维特比算法。

第一步：初始概率

输入观察序列（带分词句子）首个字符是”B”,”M”, “E”, “S”的概率（这里的概率也进行了对数运算及log(p)）。由这个概率值可以看出，句子首字单字成词（S）和作为词的词首（B）的概率较高，作为词中和词尾概率为0，也比较符合我们的常识。

# 为了直观，将log概率转化为真实概率 {key:math.exp(value) for key, value in prob_start.items()} {'B': 0.54734, 'E': 0.0, 'M': 0.0, 'S': 0.45266}

第二步：状态转移概率

“B”,”M”, “E”, “S”四个状态之间相互转化的概率

{key: {k: math.exp(v) for k, v in value.items()} for key, value in prob_trans.items()} {'B': {'E': 0.00004, 'M': 0.4}, 'E': {'B': 0.64425, 'S': 0.}, 'M': {'E': 0.86911, 'M': 0.13088}, 'S': {'B': 0., 'S': 0.10544}}

第三步：发射概率

即在观测序列是某个字的情况下，被标注为”B”,”M”, “E”, “S”的概率

# 由于这个表比较大，所以随机挑选一些出来看 {key: {k: math.exp(v) for i, (k, v) in enumerate(value.items()) if i < 5} for key, value in prob_emit.items()} {'B': {'一': 0.0, '丁': 0.00059398, '七': 0.00042123, '万': 0.00, '丈': 0.000}, 'E': {'一': 0.0062949, '丁': 0.0006071, '七': 0.000, '万': 0.000, '丈': 0.000052327}, 'M': {'一': 0.012285, '丁': 0.000, '七': 0.0082968, '万': 0.00, '丈': 8.2943e-05}, 'S': {'∶': 1.90163e-07, '一': 0.0059882, '丁': 0.000, '丂': 6.508e-08, '七': 0.000}}

第四步：使用viterbi算法对序列分词

viterbi维特比算法解决的是篱笆型的图的最短路径问题，图的节点按列组织，每列的节点数量可以不一样，每一列的节点只能和相邻列的节点相连，不能跨列相连，节点之间有着不同的距离。

为了找出Start到End之间的最短路径，我们先从Start开始从左到右一列一列地来看。首先起点是Start，从Start到“韩”字对应的状态列的路径有四种可能：Start-B、Start-E、Start-M，Start-S。对应的路径长度即

不能武断地说这四条路径中中的哪一段必定是全局最短路径中的一部分，目前为止任何一段都有可能是全局最优路径的备选项。继续往右看，到了“冰”这一列列。按照四个状态进行逐一分析，先看到达“冰”(B)节点的各个路径长度。

以上这四条路径，各节点距离加起来对比一下，我们就可以知道其中哪一条是最短的。因为Start-B-B是最短的，那么我们就知道了经过“冰”(B)的所有路径当中Start-B-B是最短的，其它三条路径路径都比Start-B-B长，绝对不是目标答案，可以大胆地删掉了。删掉了不可能是答案的路径，就是viterbi算法（维特比算法）的重点，因为后面我们再也不用考虑这些被删掉的路径了。现在经过“冰”(B)的所有路径只剩一条路径了(红色标识)

以此类推，我们可以分别找出到达“冰”字对应列的所有四个状态的最优路径

根据HMM输出的结果，我们可以将”韩“->B，”冰“->E合并成为一个新词”韩冰“。所以”韩冰是个好人“的分词结果就是[‘韩冰’, ‘是’, ‘个’, ‘好人’]

05 经典分词算法概览

jieba分词器使用道了基于规则的最长匹配算法和基于统计机器学习的序列标注相关算法。在搜索引擎中有时也会使用n-gram统计算法进行分词，而chatGPT等则采用transforms等

参考文档

[1] https://zhuanlan.zhihu.com/p/?utm_source=wechat_timeline

[2] https://www.bilibili.com/video/BV17j411z7Um/?spm_id_from=333.337.search-card.all.click