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,遍历字符串找出在词典中出现的词。 关键是怎么构建这个失败后跳转的节点。用文字描述:当匹配失败后从父节点的失败指针往下匹配,一直到根节点。其想法是匹配失败的时候回退,回退的时候充分利用前面已经成功匹配的部分。 下面这个图是构造出的字典树:  每个几点匹配失败的时候的路径如下:  这里讲得不是特别详细,推荐读[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; } } } ```