自然语言处理学习笔记（七）————字典树效率改进

目录

1. 首字散列其余二分的字典树

2.双数组字典树

3.AC自动机(多模式匹配)

（1）goto表

（2）output表

（3）fail表

4.基于双数组字典树的AC自动机

---

        字典树的数据结构在以上的切分算法中已经很快了，但还有一些基于字典树的算法改进，把分词速度推向了千万字每秒的级别，主要按照以下递进关系优化：

• 首字散列其余二分的字典树
• 双数组字典树
• AC自动机(多模式匹配)
• 基于双数组字典树的AC自动机

1. 首字散列其余二分的字典树

        散列函数用来将对象转换为整数。散列函数必须满足的基本要求是：对象相同，散列值必须相同。散列函数设计不当，则散列表的内存效率和查找效率都不高。Python没有char类型，字符被视作长度为1的字符串，所以实际调用的就是str的散列函数。在64位系统上，str的散列函数返回64位的整数。但Unicode字符总共也才136690个，远远小于2^64。这导致两个字符在字符集中明明相邻，然而散列值却相差万里。

        Java中的字符散列函数则要友好一些，Java中字符的编码为UTF-16。每个字符都可以映射为16位不重复的连续整数，恰好是完美散列。这个完美的散列函数输出的是区间[0,65535]内的正整数，用来索引子节点非常合适。具体做法是创建一个长为65536的数组，将子节点按对应的字符整型值作为下标放入该数组中即可。这样每次状态转移时，只需访问对应下标就行了，这在任何编程语言中都是极快的。然而这种待遇无法让每个节点都享受，如果词典中的词语最长为l,则最坏情况下字典树第l层的数组容量之和为O(65536^l)。内存指数膨胀，不现实。一个变通的方法是仅在根节点实施散列策略。

        字典树其实就是一棵前缀树（指的是前缀相同的词语必然经过同一个节点） 如何加速呢？在扫描"自然语言处理"这句话的时候，朴素实现会依次查询"自"、"自然"、"自然语"、"自然语言"等词语是否在词典中。但事实上，如果"自然"这条路径不存在于前缀树中，则可以断定一切以"自然"开头的词语都不可能存在。

2.双数组字典树

        状态转移复杂度为常数的数据结构。它由base和check两个数组构成，又简称双数组

3.AC自动机(多模式匹配)

        我们已经知道，字典树的本质就是DFA，假设每次状态转移的时间复杂度为常数。那么对文本“123”的扫描一共发生了六次状态转移：1、12、123；2、23；3.对于文本长度为n来说，共发生了 O(n^2) 次状态转移，所以复杂度为  O(n^2) 

        那么可不可以只进行一次扫描就查询出所有出现的单词呢，AC自动机就可以做到，它是一种  O(n) 复杂度的算法。给定多个词语（模式串， pattern），从母文本中匹配他们的问题称为多模式匹配。在中文处理中，汉字就是常见的短模式串，AC自动机在中文自然语言处理中应用更广泛。

        举个例子：我们的模式串为“自然语言”，如果用字典树查询，以“自“为起点， 找到”自然语言“后，起点又退回到”然“继续扫描...如果扫描到”自然语言“的同时知道”然语言“、”语言“、”言”不在字典树中，则可以少查询三次，观察这三个字符串，它们共享递进式的后缀，所以可以引入后缀树。AC自动机在前缀树的基础上为每个节点建立后缀树，节省大量查询。

AC自动机由goto表，fail表和output表组成，分别类似于前缀树和后缀树。

（1）goto表

        goto表也叫success表，其实就是一颗前缀树，用来将每个模式串索引到前缀树上。下面引用经典的ushers作为母文本，模式串集合为{he，she，his，hers}

        它的构建与前缀树一致，唯一不同的是，根节点不光可以按h和s转移，还接受任意其他字符，转移终点都是自己。这样形成了一个圈，使得一棵树变为一幅有向有环图。这个圈的目的在于，扫描时若遇到非h且非s的字符，状态机一直保持初始状态。

（2）output表

         给定一个状态，我们需要知道该状态是否对应某个或某些模式串，以决定是否输出模式串以及对应的值。这时用到的关联结构被称为utput 表。在图2-9所示的例子中，output表中的状态就是图中的深蓝色节点，对应的output 如表所示。

         output 表中的元素有两种，一种是从初始状态到当前状态的路径本身对应的模式串（比如2号状态），另一种是路径的后缀所对应的模式串（比如5号状态）。于是它的构造也分为两步，第一步与字典树类似，就是记录完整路径对应的模式串。第二步则是找出所有路径后缀及其模式串，这一步可以与fai1表的构造同步进行。

        为goto表加上output表

（3）fail表

        fail表保存的是状态间一对一的关系，存储状态转移失败后应当回退的最佳状态。最佳状态指的是能记住已匹配上的字符串的最长后缀的那个状态。比如，匹配she后来到状态5，再来一个字符，goto失败，哪个状态才是fail的最佳选择呢？当前匹配到的字符串为she，最长后缀为he，对应路径0-1-2。因此，状态2就是状态5 fail的最佳选择。fail到状态2之后，自动机记住了he，做好了接受r的准备。再比如，匹配his后来到状态7，再来一个字符，goto失败了。his 的最长后缀为is，可惜没有这条路径；次长后缀为s，对应路径0-3,因此状态7应当fail到3。
        如何构建fail表？定义s为当前状态；S.goto（c）为转移表，返回s按字符c转移后的状态，null表示转移失败；S.fail为fail表，代表转移失败时从状态S回退的状态。fail表的构建方法如下。
      （1）初始状态的goto表是满的，永远不会失败，因此没有fail指针。与初始状态直接相连的所有状态，其fail指针都指向初始状态，如图中的虚线所示。

         (2）从初始状态开始进行广度优先遍历（BFS)，若当前状态S接受字符c直达的状态为T,则沿着S的fail指针回溯，直到找到第一个前驱状态F，使得F.goto(c） ！= null。将T的fail指针设F.goto(c)，也即:

F = S.fail
while F.goto(c) == nullF= F.fail
T.fail = F.goto(c)

       （3）由于F路径是T路径的后缀，也就是说T一定包含F，因而T的output 也应包含F的output。于是更新:

T.output += F.output

        为上图加上完整的fail表后，自动机如图所示。

        算上fail表的虚线，从后往前看，AC自动机由许多后缀树构成。其中一棵如图所示。

         字典树状态转移可能失败，失败时扫描起点往右挪一下，重新扫描。而在AC自动机中，按goto表转移失败时就按fail转移，永远不会失败，因此只需扫描一遍文本。

4.基于双数组字典树的AC自动机

        双数组字典树能在O(1)（1是模式串长度）时间内高速完成单串匹配，并且内存消耗可控，然而软肋在于多模式匹配。如果要匹配多个模式串，必须先实现前缀查询，然后频繁截取文本后缀才可多匹配。比如 ushers、shers、hers…这样一份文本要回退扫描多遍，性能较低。既然 AC 自动机的goto表本身就是一棵字典树，能否利用双数组字典树来实现它呢？如果能用双数组字典树表达 AC自动机，就能集合两者的优点，得到一种近乎完美的数据结构。
        ACDAT的基本原理是替换 AC自动机的goto表，也可看作为一棵双数组字典树的每个状态（下标）附上额外的信息。上节提到，AC自动机的goto表就是字典树，只不过AC自动机比字典树多了output 表和fail表。那么ACDAT的构建原理就是为每个状态（base[i]和check[i]）构建output[i][]和fail[i]。具体说来，分为3步。
（1）构建一棵普通的字典树，让终止节点记住对应模式串的字典序。
（2）构建双数组字典树，在将每个状态映射到双数组时，让它记住自己在双数组中的下标。
  (3)构建AC自动机，此时fail表中存储的就是状态的下标。