经常会遇到一类需求,在一段字符串中查找所有能匹配上的模式,比如查找一段文字匹配上字典中哪些短语。这时为了高效处理,就会考虑 AC 自动机,即 Aho-Corasick 自动机算法。它的核心思想是通过有限自动机巧妙地将字符比较转化为了状态转移。
通过 AC 自动机能做到匹配时不需要回溯,而且时间复杂度为 O(n),即时间复杂度与词典的规模无关。
暴力匹配就是一个一个比较,将模式串从头到尾匹配主串字符串,如下图模式串"ABCE"比较主串,一旦遇到不相同的则往后移以为,重新开始比较,直到比对完主串,接着第二个模式串继续比较。该方法简单暴力,很好理解,但时间复杂度高,O(mn)。
AC自动机主要是将 n 个模式串构建成一个确定性的树形有限状态机,然后将主串作为该有限状态机的输入,使该状态机进行状态的转换,当到达某些特定的状态时则说明发生模式匹配。
通过例子来理解,以 he、she、his、hers
为模式串, ushers
为主串,构成了如下的状态机。
在状态机内部,可以看到有实线和虚线箭头,优先以实线标明方向转换状态,当无法实线转换时才使用虚线转换。
另外,当转换到图中红圈位置时说明发生了模式匹配,比如对于 he
,从根节点到1再到2,此时符合 he
,说明发生了模式匹配。
根据上图你可以试试看 ushers
会匹配出哪些模式,并且比划下状态的转换过程。
AC自动机包含了三个核心函数,基本上理解了他们就搞懂AC了。
实现AC自动机时一般都会用TRIE树结构,那么就会定义一个 ACTrieNode
类,包含了子节点、值、output、failure节点等等属性。
public class ACTrieNode { private ACTrieNode[] children; private byte[] value; private boolean deleted = false; private int status; private ACArray[] results = null; private ACTrieNode failureNode; private static String encoding = "utf-8"; }
详细实现看github,https://github.com/sea-boat/TextAnalyzer/blob/master/src/main/java/com/seaboat/text/analyzer/segment/ACTrieTree.java。
-------------推荐阅读------------
我的2017文章汇总——机器学习篇
我的2017文章汇总——Java及中间件
我的2017文章汇总——深度学习篇
我的2017文章汇总——JDK源码篇
我的2017文章汇总——自然语言处理篇
我的2017文章汇总——Java并发篇
跟我交流,向我提问:
公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。
为什么写《Tomcat内核设计剖析》
欢迎关注: