AC多模匹配——给失败找个出口

2018-05-19

# AC多模匹配——给失败找个出口

很多时候需要看某个单词是不是在一个句子中出现，我们见到的处理方式是:
Python
```
"word" in "sentence" 
```
Java
```
 "sentence".contains("word");
```
golang
```
strings.Contains("sentence", "word")
```
或者每种语言会有其他的处理方式，但背后到底怎么做到的？最简单的一个个比较word和sentence中的字符是否相等，当不等的时候，从句子的下一个字符再开始。但这样是低效的，为了解决这个效率问题，比较有名的算法[KMP](http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm)其主要想法就是提前算好比较失败的时候该怎么做，而不是从头再来。最终的效果是只需要遍历一次sentence就可以完成匹配。

当我们的词有很很大一个词典的时候，给定一个字符串，看词典里哪些词出现在字符串中。我们可以在循环里使用上面匹配单个词的方式来完成，但这也是低效的，为了解决这个问题，有很多方法，比较常用的叫[Aho-Corasick](https://en.wikipedia.org/wiki/Aho-Corasick)通常被成为AC多模匹配。我简单实现了下，用到了我的分词工具[FoolNLTK](https://github.com/rockyzhengwu/FoolNLTK)里。

如果我们现在只有Trie树，我们可以把词典存在Trie中，从句子开头往后去树种匹配，失败或成功之后，去掉第一个字，再从头开始来一遍，效率还是很低，但Trie树能很好的解决一个问题：当我们有很大一个词典，给定任意一个词判断这个词是否在词典中的问题。

AC多模匹配结合了Trie树和KMP的思想：用Trie树存储词典，当树建好后利用KMP的思想，构造好匹配失败时该跳转的指针，实现只遍历一次字符串，找出所有在词典中的词。所以通常有下面几个步骤：

1, 根据词典构造Trie树
2,对树中每个节点寻找失败
3,遍历字符串找出在词典中出现的词。

关键是怎么构建这个失败后跳转的节点。用文字描述：当匹配失败后从父节点的失败指针往下匹配，一直到根节点。其想法是匹配失败的时候回退，回退的时候充分利用前面已经成功匹配的部分。
下面这个图是构造出的字典树：
![](http://blog-static.midday.me/3fd038564fa5b04d2e3edcdedc57fd740b4afd983782dbd4526e048bab56795a.jpg)
每个几点匹配失败的时候的路径如下：
![](http://blog-static.midday.me/a9a0b8f8c0fe464577736dfad5886058922756134675159300add1a1fc360377.jpg)

这里讲得不是特别详细，推荐读[slides](http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf)，从自动机的角度，形式化的描述了这个算法。
下面是我写的Java代码
```

import java.util.*;

public class Trie {
    private Node root = new Node("", 0);

public Trie() {
    }

public void addWord(String word) {
        int length = word.length();
        Node currentNode = this.root;
        Node nextNode = null;
        for (int i = 0; i < length; i++) {
            String c = String.valueOf(word.charAt(i));
            nextNode = currentNode.getNext(c);
            if (nextNode != null) {
                currentNode = nextNode;
            } else {
                Node tmpNode = new Node(c, currentNode.getDepth() + 1);
                currentNode.addSuccess(tmpNode);
                currentNode = currentNode.getNext(c);
            }
        }
        currentNode.setEmits(word);
    }

public void createFail() {
        this.root.setFail(this.root);
        Queue<Node> queue = new LinkedList<>();
        Node currentNode = this.root;
        for (Map.Entry<String, Node> entry : currentNode.getSuccess().entrySet()) {
            Node node = entry.getValue();
            node.setFail(currentNode);
            queue.add(node);
        }

while (!queue.isEmpty()) {
            currentNode = queue.poll();
            for (Map.Entry<String, Node> entry : currentNode.getSuccess().entrySet()) {
                Node targetNode = entry.getValue();
                String word = entry.getKey();
                queue.add(targetNode);
                Node traceNode = currentNode.getFail();
                while (traceNode.getNext(word) == null && traceNode.getDepth()!=0) {
                    traceNode = traceNode.getFail();
                }

// root
                if (traceNode.getDepth() == 0) {
                    if (traceNode.getNext(word) != null) {
                        targetNode.setFail(traceNode.getNext(word));
                    } else {
                        targetNode.setFail(traceNode);
                    }
                }
                // not root
                else {
                    targetNode.setFail(traceNode.getNext(word));
                }
            }
        }
    }

public List<Match> parseText(String text) {
        Node currentNode = this.root;
        List<Match> matches = new ArrayList<>();
        Node nextNode;
        for (int i = 0; i < text.length(); i++) {
            String w = String.valueOf(text.charAt(i));
            nextNode = currentNode.getNext(w);
            while (nextNode == null && currentNode.getDepth() != 0) {
                currentNode = currentNode.getFail();
                System.out.println(currentNode);
                nextNode = currentNode.getNext(w);
            }
            if (nextNode != null) {
                String emit = nextNode.getEmits();
                if (emit != null) {
                    int start = i - emit.length();
                    Match match = new Match(start, i-1, emit);
                    matches.add(match);
                }
                currentNode = nextNode;
            }
        }
        return matches;
    }

}
```

Node的定义
```

import java.util.HashMap;
import java.util.Map;

public class Node {
    private String content;
    private int depth;
    private Map<String, Node> success = new HashMap<>();
    private Node fail;
    private String emits = null;

public String getEmits() {
        return emits;
    }

public void setEmits(String emits) {
        this.emits = emits;
    }

public Node(){}

public Node(String content){
        this.content = content;
    }

public Node(String content, int depth){
        this.content = content;
        this.depth = depth;
    }
    public Map<String, Node> getSuccess(){
        return this.success;
    }

public void addSuccess(Node node){
        this.success.put(node.content, node);
    }

public String getContent() {
        return content;
    }

public void setContent(String content) {
        this.content = content;
    }

public int getDepth() {
        return depth;
    }

public void setDepth(int depth) {
        this.depth = depth;
    }

public Node getFail() {
        return fail;
    }

public void setFail(Node fail) {
        this.fail = fail;
    }

public Node getNext(Node node){
        String word = node.content;
        return getNext(word);
    }

public Node getNext(String word){
        if (this.success.containsKey(word)){
            return this.success.get(word);
        }
        else{
            return null;
        }
    }
}

```