最近做聊天机器人遇到需要自建词库的需求，因为传统的分词工具并不能满足针对不同应用创建个性化词性的词语的需求，例如，在打开应用场景下，我们需要知道所有的应用名，这些应用名有可能是普通名词、也有可能是特殊名词（传统的分词工具无法分出这些词），例如云打印等等，那么我们有必要针对不同的应用、不同的机器人，实现自己的一套分词库，这样，在传统分词的基础上，额外做一次类似实体识别的过程，识别出语句中出现的自定义词性的词语。

为什么用Trie

　　最开始，我想的是直接把所有的自定义词语都存到Mongo库里，这样，每次识别实体的时候，我们都去库里查是否存在这样的实体。这样的方法很简单粗暴，但问题也很多，首先，是效率问题，每次都查库，而且一个句子有很多词语，每个词语都去库里查一遍，效率更低；其次，分完词，有可能某些特殊的名词被分成了多个词，这样拿分词结果去库里查是查不到对应的实体的。

　　后来，睡了一觉，我想起来用Trie树去构造自定义词典，trie树的插入和查询时间复杂度都很低，但是仔细想想也有很多问题，首先传统的trie树实际上是用空间换时间，将来自定义词典数据量大了，应用或租户越来越多的情况下，trie树占用的空间越来越大；另外，我们如果要通过trie树去找到一个句子里可能包含的所有自定义词语，我们需要从每个单词开头的去search trie树，这样如果句子较长，那么时间消耗也会较长。

　　传统的trie树包括、arrayTrie、listTrie、hashTriehttps://segmentfault.com/a/1190000008877595都是在空间、效率上无法达到一个最优的效果

　　而DoubleArrayTrie则可以，正好，hanlp的作者（貌似是）发现将AC自动机（AhoCrasick）与DoubleArrayTrie结合，能完美地解决多模式匹配的问题（正好就是我们的需求），那么下面我就介绍下这个巧妙的算法

AhoCrasick自动机

　　为了了解基于AC DoubleArrayTrie的多模式匹配算法，我们需要先了解AhoCrasick算法，AhoCrasick算法是一个自动机的多模式匹配算法，他能在O(n)的时间复杂度上解决问题。

　　何谓多模式匹配呢，假设我们有字典{he,she,his,hers}，现在给定一个字符串ushers，我们要输出该字符串中匹配字典的所有子串{she、he、hers}

　　首先，我们对词典，构造一颗trie树，如下图

　　我们只看其中的实现，这就是一颗标准的trie树，至于其中的虚线，则是failure跳转，中括号里的则代表命中的模式串（现在也许不太好理解，先看下去）

　　AC算法中有三个核心函数，分别是：

　　success; 成功转移到另一个状态（也称goto表或success表）

　　failure; 不可顺着字符串跳转的话，则跳转到一个特定的节点（也称failure表），从根节点到这个特定的节点的路径恰好是失败前的文本的一部分。

　　emits; 命中一个模式串（也称output表）

　　先不说上面这个图怎么构建的，假设我们已经针对词典构造了这样的状态转换自动机了，我们怎么来进行多模式匹配呢？

　　以上图中ushers为例，自动机首先从根节点0出发：

　　1. 首先尝试按success表转移，因为ushers第一个字母是u，此时根节点并没有u对应的路线，因此转移失败 　　2. 失败了则按照failure表回去，第二个字母是s，根节点的success表是有s对应的路线的，因此转移到状态3 　　3. 就这样，成功了就按success表转移，失败了则跳转到步骤2，或者遇到了output表中标明的可输出状态（图中的红色状态），则输出匹配到的模式传，然后继续转移

　　算法高效之处在于，当自动机接受了“ushe”之后，再接受一个r会导致无法按照success表转移，此时自动机会聪明地按照failure表转移到2号状态，并经过几次转移后输出“hers”。来到2号状态的路不止一条，从根节点一路往下，“h→e”也可以到达。而这个“he”恰好是“ushe”的结尾，状态机就仿佛是压根就没失败过（没有接受r），也没有接受过中间的字符“us”，直接就从初始状态按照“he”的路径走过来一样（到达同一节点，状态完全相同）。

　　可见，在O(n)的时间复杂度下，可以达到多模式匹配的目的，只要构造了success表、output表、fail表，我们就能轻易第达到这个目的。

　　那么怎么构造这三个表呢？

　　首先来看success表，这个很简单，我们直接构造一颗trie树就行了，这样在一个节点上，给定一个字符，我们就能定位到下一个节点，也就是success表的状态转移目的。

　　output表也很简单，首先trie树里的单词结尾的节点肯定有output，而且节点只有一个output，但是在这里，每个节点的output并不一定只有一个，像上图中的5节点，就有两个output{she、he},那么这是怎么得到的呢，首先，在trie树的构造过程中，词语结尾的节点肯定会有output，另外，在构造fail表的过程中，我们会将fail节点的output加到该节点的output表中，至于为什么，仔细看上图就知道了

　　较复杂点的是failure表的构造，这个表是trie树没有的，加了这个表，AC自动机就看起来不像一棵树，而像一个图了。failure表是状态与状态的一对一关系，别看图中虚线乱糟糟的，不过你仔细看看，就会发现节点只会发出一条虚线，它们严格一对一。

　　这个表的构造方法是：

　　1. 首先规则与状态0距离为1（即深度为1）的所有状态的fail值都为0 　　2. 然后，设当前状态为S1，要求fail(S1)。我们知道S1的前一状态必定是惟一的，设S1的前一状态是S2，S2转换到S1的条件是接受字符C，那么如果goto(fail(S2),C)不为空，等于S3,则fail(S1)=S3 　　3. 如果goto(fail(S2),C)为空，则看goto(fail(fail(S2)),C)是否为空，如此重复，知道转到到某个有效的状态Sn。领fail(S1)=Sn

　　这样我们就把三个表都构造出来了，根据这三个表就能进行多模式匹配了

　　但是，这种单纯的AC自动机算法效率或空间占用率都不是很优，因为在进行状态转移时，大部分实现都是一个Map<Character,State>来解决，无论你这个map是treemap（查找元素是对数复杂度）还是HashMap的巨额空间复杂度以及hash冲突时的性能消耗，都使得整体AC算法的效率低下

DoubleArrayTrie

　　doubleArrayTrie顾名思义是一个双数组的trie结构，靠两个关键的数组base和check来实现。

　　具体介绍可以参考https://segmentfault.com/a/1190000008877595

　　我这里就简单介绍下吧

　　首先，对每个字符，都有一个唯一的code与之对应，在java中，我们将char转换成int即可得到这个字符的code

　　而base数组存的是每个字符的转移基数，check数组则是用来验证状态转移是否合法

　　状态转移的公式为：

1
2
base[i] + code = t
check[t] = i;

　　即从某一个字符，输入一个字符c后，转移到的位置时base[i]加上c的code，得到字符c的位置t，并且令check[t]等于前一个字符的位置i（有些实现中的check数组存的是base[i]而不是i，例如我们马上就要介绍的AhoCrasick DoubleArrayTrie算法，只要check数组能起到验证状态转移合法性的功能即可）

　　所以这样对词典构造完trie结构，得到两个大小一样的数组，base和check，我们就能对字符串进行匹配了。

　　从base[0]出发，遍历字符串的每一个字符，根据字符的code和base数组从位置0一步步第往下寻找下一个状态的位置，并且用check检查是否转移合法，这样就完成了单模式的匹配。

　　可见，双数组Trie树在查询时没有传统trie树的效率问题，因为他都是直接在数组中操作，每次找到下一个状态都是O(1)的时间复杂度，然而，双数组Trie树在多模式匹配时，只能从字符串中每个字符开始去匹配，才能完成多模式匹配，这样一份文本要扫描多遍

基于DoubleArrayTrie的Aho Crasick自动机

　　所以，如果我们能将这两者结合起来，那就能完美解决多模式匹配问题。

　　这部分代码，已经开源了https://github.com/hankcs/AhoCorasickDoubleArrayTrie

　　下面我们来通过源码学习下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public void build(Map<String, V> map)
    {
        // 把值保存下来
        v = (V[]) map.values().toArray();
        l = new int[v.length];
        Set<String> keySet = map.keySet();
        // 构建二分trie树
        addAllKeyword(keySet);
        // 在二分trie树的基础上构建双数组trie树
        buildDoubleArrayTrie(keySet.size());
        used = null;
        // 构建failure表并且合并output表
        constructFailureStates();
        rootState = null;
        loseWeight();
    }

　　build方法是构建自动机的过程，传入的参数是Map类型，map的key就是词典中的词语，而value可以是任何类型，这样，在匹配得到字符后，我们也能得到其value，这对于我们标注词语的自定义词性是正好完美契合的~

　　首先，通过addAllKeyword(keySet);来构建传统的trie树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    private void addAllKeyword(Collection<String> keywordSet)
    {
        int i = 0;
        for (String keyword : keywordSet)
        {
            addKeyword(keyword, i++);
        }
    }

	private void addKeyword(String keyword, int index)
    {
        State currentState = this.rootState;
        for (Character character : keyword.toCharArray())
        {
            currentState = currentState.addState(character);
        }
        currentState.addEmit(index);
        l[index] = keyword.length();
    }

　　rootState是trie树的根节点，可见对于每一个字符串，我们从根节点开始构建其子节点，直到到字符串的结尾，最后将该字符串在map中的位置存储到结尾节点（节点即程序里的state，每一个state的子节点就是我们之前提到的success表里的所有状态）

　　创建完传统的trie树后，就开始构建DoubleArrayTrie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    private void buildDoubleArrayTrie(int keySize)
    {
        progress = 0;
        this.keySize = keySize;
        resize(65536 * 32); // 32个双字节

        base[0] = 1;
        nextCheckPos = 0;

        State root_node = this.rootState;

        List<Map.Entry<Integer, State>> siblings = new ArrayList<Map.Entry<Integer, State>>(root_node.getSuccess().entrySet().size());
        fetch(root_node, siblings);
        insert(siblings);
    }

　　这里有两个关键的方法，fetch和insert

　　fetch方法用来将节点的所有子节点抓取到slblings集合中，然后通过insert方法来将这些子节点插入到base和check数组中相应的位置。这个找位置的过程是最复杂的。具体代码我就不放，自己去看好好体会 = =

　　base和check数组构造完后，相当于我们的success表已经建立好，那么接下来就通过constructFailureStates();来构建fail表和output表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 private void constructFailureStates()
    {
        fail = new int[size + 1];
        fail[1] = base[0];
        output = new int[size + 1][];
        Queue<State> queue = new ArrayDeque<State>();

        // 第一步，将深度为1的节点的failure设为根节点
        for (State depthOneState : this.rootState.getStates())
        {
            depthOneState.setFailure(this.rootState, fail);
            queue.add(depthOneState);
            constructOutput(depthOneState);
        }

        // 第二步，为深度 > 1 的节点建立failure表，这是一个bfs
        while (!queue.isEmpty())
        {
            State currentState = queue.remove();

            for (Character transition : currentState.getTransitions())
            {
                State targetState = currentState.nextState(transition);
                queue.add(targetState);

                State traceFailureState = currentState.failure();
                while (traceFailureState.nextState(transition) == null)
                {
                    traceFailureState = traceFailureState.failure();
                }
                State newFailureState = traceFailureState.nextState(transition);
                targetState.setFailure(newFailureState, fail);
                targetState.addEmit(newFailureState.emit());
                constructOutput(targetState);
            }
        }
    }

　　在这方法中，我们完成了fail表和output表的构建，首先，对所有深度为1的节点，将其fail设为根节点

　　然后对于深度大于1的节点的fail表的建立，是用bfs来做的

　　从queue中取一个节点，该节点肯定是已经计算过fail和output了的，然后遍历其子节点，计算其子节点的fail表和output表。

　　对于通过字符C到达的子节点的fail表，我们需要看看其父节点的fail通过字符C能否转移到下一个节点，若可以，则子节点的fail节点为父节点的fail节点通过C转移到的那个节点，若不可以，则再往上找一层，直到找到（根节点是肯定可以的作为fail节点的）

　　找到之后，就将其设为该子节点的fail节点，并将fail节点的所有output表合并到子节点中来。

　　至此，一个基于DoubleArrayTrie的AC自动机就构造完了