使用有向无环图实现分词
使用有向无环图实现分词
#自然语言处理
结巴分词
如果搜索”Python 分词”，跳出来的前五个除了广告基本都包括“结巴分词”（Jieba）。可以说它是 Python 自然语言中使用最广泛的分词工具。它属于基于概率的模型，其原理主要是利用了显性的中文词库（包含常用词及词性和频率）。形如：
同时也支持隐马尔可夫模型从数据中训练出的发射概率，转移概率等不易理解的数据。
简单地说，分词就是识别句中的词组，然后把句子拆分成尽量大的块。但由于上下文语境不同，拆分时也常常出现规则冲突，比如“研究生命的起源”，既可拆成“研究生 命 的 起源”，也可拆成“研究 生命 的 起源”。因此，需要制定一些规则处理这些冲突。
和当前很多基于深度学习的自然语言模型相比，结巴轻量级，使用简单，原理不复杂，效果也不错的分词工具。利用结巴的原理，不仅能实现分词，还能实现切分短语，判断词性，计算短语在句中成份，提取特定成份等一系列的功能。与复杂模型相比，它更容易运用已知的规则，占用更少的资源，避免了大量的文本标注；与自己直接处理相比，它能处理更复杂的情况。尤其在某些语法相对单一的专门领域效果很好。
本文将分析结巴分词的核心代码，看看它是如何解决冲突，并学习有向无环图的数据结构如何在其中发挥作用。
创建有向无环图
结巴的核心代码在 jieba/init.py 文件中，先以“研究生命的起源”为例，看看它如何分词。
首先，进行 get_DAG() 函数构造一个有向无环图，具体方法是以句子的每一个字为开头（184 行）能组成什么词。
函数返回的结果是字典 DAG，其中每个元素都是位置的索引号：
“研”字可以单独成词，也可以和“研究”，“研究生”组合，这是一个开头三种结尾的情况 0:[0,1,2]；
“究”不能与后面的“生”组合成词，因此第 1 个开始位置只对应一个结束位置 1:[1]；
“生”字可以单独成词，也可以和“生命”组合，一个开头两种结尾 2:[2,3]
后面的其它字以此类推。
我们将其中每个可能出现的词（含一字词和多字词）作为单个元素，组合成图，方向按文字从左到右，既有向且无环（如果同一个词出现在句子的不同位置也认为是不同元素）。可以得到以下图。
目标是找到一条从“开始”到“结束”的路径，且整体路径的权重之和最大，每一个点的权重是该词汇出现的频率（后面详述）。
这是一个非常简单的有向无环图 DAG 应用场景。定义了入口，出口，可用节点，节点权重和节点间可达的方向和关系。通过计算权重选择最佳路径（最佳子图）。
DAG 有向无环图指的是一个无回路的有向图（如果有一个非有向无环图，且 A 点出发向 B 经 C 可回到 A，形成一个环）。DAG 可看作是树结构的扩展，所有的有向树都是有向无环图。
寻找最佳路径
下面来看看如何从多条可达路径中选取最佳路径，在结巴中由 calc 函数实现：
函数运行后，route 内容填充如下：
句子包含七个字“研究生命的起源”，返回字典中的每个元素对应以每个位置为起点的最佳终点和分值，终点 7 也作为一个元素存入字典，其分值为 0。具体实现方法是：
先设置终点 7 的值，加入字典（174 行）；
计算最高频率的 log 值 logtatal，其中 self.total 是将字典中所有词汇的词频值加和（175 行）；
从后向前遍历句中的每个位置（176）;
计算以每个字开头的最佳终点及分值：先遍历以该字开头所有可能的词（for x in DAG[idx]），计算其中分值最高的组，具体方法是用该词频率的 log 值减去一个非常大的词频 logtotal，再加上该词之后路径的最佳分值（177-178 行）；
举个具体例子，对于第一个位置，有三种选择“研”，“研究”，“研究生”，这三词的词频不同，logtotal 相同，其后路径的最佳分值也不同。“研”之后路径的分值是“1:(-32.3…)”，“研究”是“2:(-35.9…)”，“研究生”是“3:-(24.8…)”，而且 log(‘研究’) 又明显大于 log(‘研究生’)，因此将“研究”作为该位置的最佳选项。
划分词段
整体分词逻辑如下：
最终划分时非常简单，代码中使用 yield 实现了迭代器，看起来比较复杂。如果不考虑英文字母处理（代码中 buf 部分），简化后的逻辑是：从起始位置 0 开始，x 为起点，y 为以 x 为起点的最佳终点位置，取出该词作为正确切分，然后将结束点 y 作为新的起点，找下一词的最佳结束点，直至处理完句中所有句。
如本例中，第一次进循环 x=0，y=1+1=2，则切出“研究”，然后赋值 x=y=2；第二次循环时 x=2，y=3+1=4，切出“生命”，然后赋值 x=y=4；以此类推。
注意：此函数不包括隐马尔可夫链的逻辑处理，分词时需要加参数 HMM=False，才能运行到该函数。
图结构就像树结构一样，其本身非常抽象，可以实现多种多样的功能。个人觉得只要了解其原理即可，用时再深入也不迟。