AC自动机+trie树实现高效多模式匹配字典

经常会遇到一类需求,在一段字符串中查找所有能匹配上的模式,比如查找一段文字匹配上字典中哪些短语。这时为了高效处理,就会考虑 AC 自动机,即 Aho-Corasick 自动机算法。它的核心思想是通过有限自动机巧妙地将字符比较转化为了状态转移。

通过 AC 自动机能做到匹配时不需要回溯,而且时间复杂度为 O(n),即时间复杂度与词典的规模无关。

暴力匹配

暴力匹配就是一个一个比较,将模式串从头到尾匹配主串字符串,如下图模式串"ABCE"比较主串,一旦遇到不相同的则往后移以为,重新开始比较,直到比对完主串,接着第二个模式串继续比较。该方法简单暴力,很好理解,但时间复杂度高,O(mn)。

AC自动机+trie树实现高效多模式匹配字典

AC自动机

AC自动机主要是将 n 个模式串构建成一个确定性的树形有限状态机,然后将主串作为该有限状态机的输入,使该状态机进行状态的转换,当到达某些特定的状态时则说明发生模式匹配。

通过例子来理解,以 he、she、his、hers 为模式串, ushers 为主串,构成了如下的状态机。

AC自动机+trie树实现高效多模式匹配字典

在状态机内部,可以看到有实线和虚线箭头,优先以实线标明方向转换状态,当无法实线转换时才使用虚线转换。

另外,当转换到图中红圈位置时说明发生了模式匹配,比如对于 he ,从根节点到1再到2,此时符合 he ,说明发生了模式匹配。

根据上图你可以试试看 ushers 会匹配出哪些模式,并且比划下状态的转换过程。

AC的三个函数

AC自动机包含了三个核心函数,基本上理解了他们就搞懂AC了。

  • goto函数,用来指导状态转换,即在当前状态下,输入一个字符后该转到哪个状态,对应的是上图中的实线部分。
AC自动机+trie树实现高效多模式匹配字典
  • failure函数,用来指导匹配失败时的状态转换,即在当前状态下,输入一个字符后没办法根据实线进行转换了,此时根据虚线进行转换,对应上图虚线部分。
AC自动机+trie树实现高效多模式匹配字典
  • output函数,描述哪些状态下发生了匹配,匹配的模式是什么。
AC自动机+trie树实现高效多模式匹配字典

实现

实现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并发

跟我交流,向我提问

AC自动机+trie树实现高效多模式匹配字典

公众号的菜单已分为“读书总结”、“分布式”、“机器学习”、“深度学习”、“NLP”、“Java深度”、“Java并发核心”、“JDK源码”、“Tomcat内核”等,可能有一款适合你的胃口。

为什么写《Tomcat内核设计剖析》

欢迎关注:

AC自动机+trie树实现高效多模式匹配字典

原文 

https://juejin.im/post/5b42ab4af265da0f8815eded

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » AC自动机+trie树实现高效多模式匹配字典

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址