本篇讨论的是对特定输入句子进行的处理过程。基本思想是对特定输入句子从前往后遍历找出所有词构成有向无环图，然后从最后一个词开始往前找每个词的“最优左近邻词”构成一个完整的词语序列。

DAG

DAG，也就是有向无环图，可以用来记录一个句子的不同的切分状态集合，所谓的“向”就是句子从开始到结束的方向。假定句子的开始符为S，以“他们有意见分歧”这个句子为例，可以得到如下的有向无环图：

有向无环图例子
有向无环图例子

在生成一个句子的有向无环图的过程中，利用 BiGram 模型计算所有的转移概率并进行储存。

之后，从后往前回溯，寻找每个词的最优左近邻词，直到‘S’字符。结束。

从句子生成 DAG

假设开始标识符为‘S’。

对于特定的一条输入句子sentence，原始问题可以理解成：由sentence和其前一个词‘S’构建有向无环图。

对 sentence进行分词操作，假设找到的第一个词为firstWord，输入句子 sentence便可切分为 firstWord + subsentence两部分，其中firstWord作为 subsentence的“前一个词”。原始问题便可归约为由firstWord 和 subsentence构建有向无环图（构建结果作为最终 DAG 的子图）。

根据上面的分析，构建完整DAG 的过程是一个递归求解的过程，完整的算法步骤描述如下（简记为 Alg-1)：

  1. 输入句子 sentence
  2. 以开始标记符“S”和 sentence 开始构建 DAG。（“S”作为整个图的开始结点，“源”点）
  3. 对 sentence从前往后找“第一个词”（firstWord），找到第一个词后，将 sentence划分为 firstWord 和 subsentence两部分。firstWord即可作为最终 DAG 的一个结点。
  4. 对 subsentence重复第三步的切分操作（寻找第一个词和子句），找到的“第一个词”作为最终 DAG 的结点，对子句继续切分（递归）。
  5. 递归结束条件：子句为空。
  6. 结束时，将所有最后一个词放入 endSet（结束词集合）里。

在 Alg-1的步骤3中要寻找“第一个词”，要注意的是，这个寻找过程不是一次性的，因为“第一个词”可能有多种情况，譬如，“有意见分歧”这句话中，对于第一个词，存在着 有/意见分歧 和 有意/见分歧 这两种潜在可能的划分，需要一并进行考虑。因此，寻找词的过程是一个循环的过程，设定上限值为15（汉语中基本不存在长度超过15的词），从第一个字开始向前寻找（切片）：

1
2
for i in range(1,15):
    word = sentence[:k]

如果“切”出来的 word在词典中，则作为一个子问题，这样才能保证最后生成的 DAG 是考虑了所有可能情况的（考虑了所有的歧义）。

不过，这个“粗暴”的切分方式也存在着可见的缺陷。它会大幅度增大了有向无环图的规模（最坏情况下，所有的单字都作为图的一个结点）。对于长句子来说会极大的增大了生成时间，而且，这里用递归来生成子图，因此甚至存在递归过深导致堆栈溢出等问题，即使不是这样，也会显著的增加了程序运行时间。

减少无用递归

经过多次痛苦的测试过程，摸索出减少无用递归的方法可以短暂缓解上面提到的缺陷。

考虑如下句子：

因为他们有意见分歧，会议的时间未能确定下来。

虽然在中文语义上，可以以逗号为分隔直接划分成两个子问题再进行切分生成 DAG，但在计算机中还是视为一个句子进行处理。

在“有意见分歧，”这里，存在至少两种切分：

有/意见分歧 和 有意/见分歧

无论这个子句如何切分，切分之后的两个子句

意见分歧，···

见分歧，···

除了第一个词之外都是重叠的，生成的子图也是一样的，无需重复的递归进行处理。

基于这种分析，在考虑生成 DAG 函数的关键参数：firstWord和 subsentence，将这两个参数构成一个元组（tuple），用一个集合记录下已经进行了“子图生成”的元组，每次要执行递归前，首先判断关键参数组合是否在集合中，如果在集合中则直接跳过，否则再执行递归过程，执行完毕后将关键参数组合添加到集合中。

最优左近邻词（bLAW）

考虑词序列

$$w_1,w_2,w_3,…,w_{i-1},w_i,…,w_n$$

$w_{i-1}$即为$w_i$的左近邻词。

用输入句子生成 DAG 之后，对结束词集合中的每一个词，从后往前回溯，寻找每一个词的最优左近邻词，直到“S”结束，得到潜在的切分序列。如果切分序列不止一个的时候，则计算每个切分句子的概率，取概率较大者作为切分结果序列。

如何寻找最优左近邻词？

考虑累计概率计算公式：

$$P_a(w_i)=P_a (w_{i-1})*P(w_i/w_{i-1})$$

对每一个左近邻词（在 DAG 中表示为一个结点的所有前向相邻结点），计算累积概率，取概率较大者作为最优左近邻词。

潜在问题

以下潜在问题的讨论仅限于本文讨论的 DAG 和寻找左近邻词的算法，并不一定 LAW 这个概念本身可能存在的问题。

  1. “最优”只考虑了局部的情况，在语料库生成的搭配词典规模受到限制的场合，基于语料库训练出来的 BiGram 模型计算出来的累积概率与实际应用场景中“本该有”的概率存在较大差异，这种差异将直接反映在切分结果上。
  2. 生成 DAG 的过程以词本身而不是词在句子中的下标序号作为图的结点，对于一个存在重复词的句子，从后往前找左近邻词时可能进入死循环中。解决办法是每次寻找词的时候将这个词与它“本该”出现在句子中的位置进行比较再决定是不是 LAW

参考资料

  1. jieba中文分词源码分析（三）
  2. 王小捷老师计算语言学课程相关课件资料