DAG

关于自然语言处理中常用的DAG（有向无环图）使用的一点微小的理解。

最近又开始做自然语言处理的一些微小的工作。有一次处理的句子中含有“手术”这两个字，我查看了“手”、“术”和“手术”在字典中各自的频率之后发现，“手”字的频率高出“手术”很多，分词算法怎么是决定把“手术”作为一个整体分出来的?
要做到这一点，要做的就是根据字典里收录的词，把所有分词可能都列出来，再从中找一个最可能的组合。比如这句话“一个伸手不见五指的黑夜”。可以分成以下几种：

1.一、个、伸、手、不、见、五、指、的、黑、夜。
2.一个、伸、手、不、见、五、指、的、黑、夜。
3.一个、伸手、不、见、五、指、的、黑、夜。
4......
......

差不多就是这样，那么以什么格式存储这些信息比较合适呢？本着最精简的原则，我们只看最少需要什么。首先，一个字具体是什么我们并不关心，我们只需要知道字的位置在哪，因此肯定是要将具体的字词用他们在句中的index表示。比如“一”字现在就是0，“夜”字现在就是10。其次，我们还需要知道词的位置在哪，每个字都可能是词的首部，所以我们只需要词的尾部。那么需要存储的信息就是一系列二元组，每个二元组的第一项是一个字的index，第二项是该字所有可组成词的词尾的index的集合。就是这样的一个集合。那么现在上面的信息被精炼成如下：

{(0,[0, 1]),(1,[1]),(2,[2, 3, 5, 7]),(3,[3]),(4,[4, 5]),(5,[5]),(6,[6, 7]),(7,[7]),(8,[8]),(9,[9, 10]),(10,[10])}

图像化一点也就是下图所示的信息：

这种格式已经很接近我们要的东西，但是我们最想看到的其实是这些二元组的第二项都只有一个数字，这样从0出发，就只有唯一的一条路线到达10。要做到这一点我们需要额外的信息，也就是每个词的统计频率。知道这些频率之后,我们有很多方式去计算概率最大的一条路线，比如我们可以从头开始将每种可能都单独计算一遍。这样当然行得通，但是不难发现有很多信息被重复计算过不止一遍。因此从头开始算显然不是最聪明的办法，从尾开始才是最好的。
如何计算？首先，为这个DAG中的每个节点维护一个freq值，表示此点作为词头而有后面的句子的概率。这个freq值计算如下：

freq(index) = dfreq(index, tail) + freq(tail + 1)

dfreq(index, tail)指以index为词头，tail为词尾的词在字典中的频率。index遍历DAG获得，tail遍历每个index对应的词尾集合获得。如果一个index对应多个tail，依次按上面公式算，最后选最大的那个即可。每算完一个点，将得到的freq值和tail的值记录下来，直到算到第一个点结束。结果是这样的：

10 [tail=10, freq=-9.635810961320582]
9  [tail=10, freq=-11.362565600239641]
8  [tail=8, freq=-16.62501610127819]
......
0  [tail=1, freq=-36.451496005714255]

最后，从第一个点开始，我们可以得到且仅可以得到一条最大概率的路径，这就是我们对这个句子进行分词的结果。

[0, 1],[2, 7],[8, 8],[9, 10]
[一个],[伸手不见五指],[的],[黑夜]