结巴分词算法原理基于前缀词典实现高效的词图扫描

本文讲解口吃分词的分词原理，主要包括分词的具体过程和未注册词的切分。 本文主要参考了////中的内容，感谢原作者！

本文如有不妥之处，敬请读者指出。

口吃分词算法的原理是基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能的构词组成的有向无环图（DAG）。 动态规划用于寻找最大概率路径，并根据词频找到最大切割。 对于未注册词，采用基于汉字构词能力的HMM模型进行分组组合，并采用算法

下面我们一一解释一下。

1、基于前缀词典实现高效的词图扫描，生成句子中汉字所有可能的构词组成的有向无环图（DAG）。

口吃分词自带了一个字典，叫dict.txt，里面有一个单词。 每行包含词条和词条出现的次数（这个数字是结巴作者自己根据人民日报语料库等资源训练出来的）和词性，如下图。

dict.txt 文件列表

在基于词典的中文分词方法中，词典匹配算法是基础。 为了保证分词速度，需要选择好的字典搜索算法。 这里我们介绍一下字典的Tre树组织结构。 基于前缀词典的词图扫描，就是将这34万多个词放入一个trie树数据结构中。 trie树也称为前缀树或字典树，意思是一个单词的前几个单词是相同的。 意味着它们具有相同的前缀，可以使用trie树来存储，这样的优点是搜索速度快。 搜索数字的 trie 树每个节点仅保留一个字符。 如果一个单词长于一个字符，则包含第一个字符的节点有一个指向下一个字符的节点的指针，依此类推。 这形成了分层树，树的第一层包括所有单词的第一个字符，树的第二层包括所有单词的第二个字符，依此类推。 显然，trie树的最大高度就是字典中最长单词的长度。

查询过程从前到后逐个字符地匹配查询词。 对于trie树来说，是一个从根节点向下的匹配过程。

有些人可能会想到把dict.txt中的单词全部删除，然后尝试看看是否可以使用口吃来分词。 结果会显示，口吃依然可以分词，但是大部分分出的词长度为2。这是第三个任务，基于HMM预测分词。 我们稍后再谈。

DAG有向无环图是由后一句生成的句子中汉字所有可能的构词情况组成的有向无环图。 这意味着，给定一个待分词的句子，匹配它的所有单词，单词图就形成一个有向无环图DAG，如下图所示：

DAG单词图，每条边都是一个单词

那么具体是如何完成的呢？ 分为两步：1.根据dict.txt字典生成trie树； 2、根据分词句子的trie树生成DAG。 其实通俗地说，就是对分词句子进行处理，根据给定的字典进行字典查找操作，生成几种可能的分句，形成类似于上图的DAG图。

对于DAG的实现，在源码中，作者记录了一个单词在句子中的起始位置，从0到n-1（n为句子的长度），建立了一个字典，每个起始位置服务于作为字典的键。 value是一个列表，存储了单词可能的结束位置（通过查字典得到单词，然后将单词的起始位置加上单词的长度得到结束位置）。 例如： {0:[1,2,3]} 是一个简单的 DAG，从位置 0 开始，到位置 1,2,3 结束，即 0 ~ 1, 0 ~ 2 ，三个位置之间的字符0~3的范围都是dict.txt中的单词。

2、利用动态规划求最大概率路径，根据词频找到最大分词组合。

在作者的代码中，在根据字典生成trie树的同时，还将每个单词出现的次数转换为频率。 频率实际上是0到1之间的小数，即事件发生的次数/实验中的总次数。 因此，当实验数量足够多时，频率近似等于概率，或者说频率的极限就是概率。

动态规划中，首先搜索待分词句子中已经分词的单词，然后搜索该单词出现的频率（次数/总数）。 如果没有这个词（因为是根据字典查的，所以应该有可能没有这个词）。 ），取字典中出现频率最小的单词作为该单词的频率。 也就是说，P(某词)=FREQ.get('某词', )，然后根据动态规划找到概率最大的路径。 从右到左倒序计算句子的最大概率（也可以从左到右。这里倒过来是因为中文句子的重心经常落在后面，也就是在右边，主要是因为有通常是形容词太多，后者是骨干，所以从右到左计算时，准确率比从左到右计算时要高，类似于反向最大匹配的分词方法），P(NodeN) =1.0，P(NodeN-1)=P(NodeN)*Max(P(倒数第二个词))，以此类推，最终得到最大概率路径，即得到最大概率切分组合。

3.对于未注册词，采用基于汉字构词能力的HMM模型，并采用算法

这里的未注册单词（Out Of word，OOV word）是指字典dict.txt中没有记录的单词。 如上所述，dict.txt中的所有单词都被删除。 口吃分词也可以分词，就是我说的。 怎么做？ 这是基于作者采用的HMM模型。 中文单词按照BEMS的四种状态进行标注。 B是开始位置，E是结束位置，M是中间位置，S是单独的单词。 地点。 也就是说，他用（B、E、M、S）四种状态来标记中文单词。 例如，北京可以标记为BE，即Bei/B Jing/E，表示北为起始位置，京为结束位置。 中华民族可称为BMME，即始、中、中、终之意。

作者训练大量语料后，得到目录下的三个文件（来自口吃项目）：

主要要统计三个概率表：

1）位置转移概率，即B（开始）、M（中间）、E（结束）、S（独立词）四种状态的转移概率，表格存放在.py中，如下表的内容；

{'B': {'E': 0.8518218565181658, 'M': 0.14817814348183422},
'E': {'B': 0.5544853051164425, 'S': 0.44551469488355755},
'M': {'E': 0.7164487459986911, 'M': 0.2835512540013088},
'S': {'B': 0.48617017333894563, 'S': 0.5138298266610544}}

例如，P(E|B) = 0.851，P(M|B) = 0.149，表示当我们处于一个单词的开头时，下一个单词是结尾的概率。 它比下一个词是中间词的概率要高得多，这与我们的直觉一致，因为二字词比多字词更常见。

2）从位置到单个单词的发射概率，例如P(“和”|M)表示单词“和”出现在单词中间的概率。 该表存储在.py中；

3）以某种状态开始的单词实际上只有两种概率，要么是B，要么是S。该表存储在.py中。这是起始向量，即HMM系统的初始模型状态。

其实BEMS之间的转换有点类似于2元模型，就是两个词之间的转换。 二元模型考虑了一个单词之后出现另一个单词的概率，是N元模型之一。 例如：一般来说，北京出现在中国之后的概率大于北海出现在中国之后的概率。 也就是说：, China 比 , China 出现的可能性更大，而且更可能是一个中文单词。

将要分割的给定句子视为观察序列。 对于HMM（BEMS）四状态模型，为了找到最优的BEMS隐藏状态序列，需要使用算法来得到最优的隐藏状态序列。 利用预先训练好的HMM转移概率和发射概率，并利用基于动态规划的算法，可以找到使概率最大化的BEMS序列。 按照从B开始到E结束的方法，将待分词的句子重新组合，得到分词结果。

例如，对于一个处理分词的句子，全世界都在学习中文，得到一个BEMS序列[S，B，E，S，S，S，B，E，S]。 此顺序只是一个示例，可能不正确。 将连续的BE组合在一起，我们得到一个单词，S是一个单独的单词，我们得到一个分词结果：上面的BE位置对应于句子中单个汉字的位置，我们得到整个/ S世界/BE都是/S中的/S学习/S中文/BE华/S，从而将句子分词。

总结

口吃分词的流程：

加载字典并生成trie树；

给定一个待分词的句子，利用正则性获取连续的汉字和英文字符，将其分割成短语列表，对每个短语使用DAG（字典搜索）和动态规划得到最大概率路径。 对于DAG中字典中没有的单词，将找到的单词组合成新的片段短语，利用HMM模型进行分词，这就是作者所说的识别新词，即识别外面的新词词典;

使用的yield语法生成一个单词生成器，它逐字返回。

为了实现的分词功能，我们首先手动统计一个大语料库中单词的出现频率，然后将分词后的句子形成一个DAG词图，并使用动态规划来找到DAG词图中最短的词图。 路径（概率最高），选择最短路径作为分割方法。 对于OOV词，使用HMM，将BEMS视为隐藏状态，将待分词的句子视为观察状态。 还采用动态规划算法来寻找概率最高的路径，即最佳分割组合。

参考/fxsjy/jieba对中文分词模块中口吃分词算法流程的理解和分析。 中文分词的基本原理以及jieba分词的使用。 jieba中文分词源码解析（一）结巴分词原理讲解/p//wiki/Trie