有时候可能需要按一个关键字词列表来过滤信息,例如过滤黄色或其他非法信息
调用indexOf方法来查找关键字集合看起来效率不高,Aho-Corasick算法可用用来在文本中搜索多个关键字,当有一个关键字集合时,想发现文本中所有出现关键词的位置,或者检查是否有关键字集合中的任何关键词出现在文本中时,可用使用Aho-Corasick算法。
Aho-Corasick算法是多模式匹配中的经典算法,目前在实际应用中较多。
Aho-Corasick算法对应的数据结构是Aho-Corasick自动机,简称AC自动机。
搞编程的一般都应该知道自动机FA吧,具体细分为:确定性有限状态自动机(DFA)和非确定性有限状态自动机NFA。普通的自动机不能进行多模式匹配,AC自动机增加了失败转移,转移到已经输入成功的文本的后缀,来实现。
1.多模式匹配
多模式匹配就是有多个模式串P1,P2,P3...,Pm,求出所有这些模式串在连续文本T1....n中的所有可能出现的位置。
例如:求出模式集合{"nihao","hao","hs","hsr"}在给定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出现的位置。
2.Aho-Corasick算法
使用Aho-Corasick算法需要三步:
1.建立模式的Trie
2.给Trie添加失败路径
3.根据AC自动机,搜索待处理的文本
下面说明这三步:
2.1建立多模式集合的Trie树
Trie树也是一种自动机。对于多模式集合{"say","she","shr","he","her"},对应的Trie树如下,其中红色标记的圈是表示为接收态:
2.2为多模式集合的Trie树添加失败路径,建立AC自动机
构造失败指针的过程概括起来就一句话:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字母也为C的儿子。如果一直走到了root都没找到,那就把失败指针指向root。
使用广度优先搜索BFS,层次遍历节点来处理,每一个节点的失败路径。
特殊处理:第二层要特殊处理,将这层中的节点的失败路径直接指向父节点(也就是根节点)。
2.3根据AC自动机,搜索待处理的文本
从root节点开始,每次根据读入的字符沿着自动机向下移动。
当读入的字符,在分支中不存在时,递归走失败路径。如果走失败路径走到了root节点,则跳过该字符,处理下一个字符。
因为AC自动机是沿着输入文本的最长后缀移动的,所以在读取完所有输入文本后,最后递归走失败路径,直到到达根节点,这样可以检测出所有的模式。
3.Aho-Corasick算法代码示例
模式串集合:{"nihao","hao","hs","hsr"}
待匹配文本:"sdmfhsgnshejfgnihaofhsrnihao
相关推荐
AC自动机算法(Aho-Corasick 多模式匹配算法)C#实现
1.多模式匹配 2.Aho-Corasick算法 1.建模式的Trie 2.给Trie添加失败路径 3.根据AC动机,搜索待处理的本 3.Aho-Corasic
通过分析模式匹配算法在网络入侵检测中的重要作用和所面临的问题,对Aho-Corasick基于自动机的算法和以Aho-Corasick算法为基础的相关算法进行了分析,并通过实验对多种多模式匹配算法进行综合对比,最后对多模式匹配...
aho-corasick-node 基于DoubleArray Trie的Aho-Corasick字符串匹配算法的Node实现。安装npm install aho-corasick-node --save用法建造const AhoCorasick = require ( 'aho-corasick-node' ) ;const keywords = [ 'b...
简介Aho-Corasick算法简称AC算法,通过将模式串预处理为确定有限状态动机,扫描本遍就能结束。其复杂度为O(n),即与模式串的数量和长度关。思想动机按照
阿霍·科拉西克(Aho-Corasick) 相依性 在您的POM中包括此依赖项。 确保在Maven Central中检查... Aho-Corasick算法在查找多个单词时会发光。 它没有使用所有关键字来构建结构,而不是将搜索文本切碎。 关键的Aho-C
aho-corasick-lua Aho-Corasick字符串匹配算法的Lua实现见
Daachorse 是一个使用Aho-Corasick 算法进行快速多重模式匹配的 crate ,在输入文本的长度上以线性时间运行。对于时间和内存效率,模式匹配自动机是使用紧凑的双数组数据结构实现的。该数据结构不仅支持恒定时间的...
AC自动机-Set Matching and Aho-Corasick Algorithm
php_aho_corasick 实现Aho-Corasick模式匹配算法PHP扩展(更多关于 )。 如果有大量的针头数据库(=要搜索的字符串,例如病毒签名),则特别有效。 另一个优点是,内置搜索结构在搜索之前在单独的调用中被初始化,...
goac --- Aho-Corasick多模式字符串匹配算法Go语言实现 An Aho-Corasick multi-pattern string matching lib written in Golang Author: Inspired by: Usage Example package goac import "goac" func ...
国外网站上找的Aho-Corasick字符串高效搜索算法,学习算法以及字符串搜索值得一看
Go中Aho-Corasick字符串搜索算法的实现。 根据MIT许可获得许可。 细节 从几年前的,此实现就没有使用 。 这大大减少了构建时间,但以更高的内存消耗为代价。 搜索时间仍然很快,并且可以与我在github上发现的...
py-aho-corasick py-aho-corasick 免费软件:MIT许可证原型的灵感来自特征纯Python实现Python2 && Python3支持Unicode && UTF-8编码支持可腌制的序列化背景由于工作需要,我重新发明了该算法。 我已经检查了Python的...
Aho-Corasick 算法, 用于从文本串中识别一组关键字,所需的时间和文本长度和所有关键字总长成正比,见编译原理. KMP搜索算法, 由Knuth, Morris, Pratt 提出的一种在文本串中识别单个关键字的算法. 自己在学习编译有理...
字符串匹配算法。 安装 cabal update cabal install AhoCorasick 例子 最简单的例子 example1 = mapM_ print $ findAll simpleSM " ushers " where simpleSM = makeSimpleStateMachine [ " he " , " she " , " his...
aho-corasick - Aho-Corasick 字符串匹配算法 #安装 $ npm install aho-corasick #例子 ##咖啡 搜索 ac = new AhoCorasick() ac.add word, word:word for word in ['say', 'she', 'shr', 'he', 'her'] ac....
更多关于AC算法和AC自动机的说明,请参见 http://blog.csdn.net/lemon_tree12138/article/details/49335051
Ahocorasick Aho-Corasick字符串匹配算法的Golang实现
该库主要通过Aho-Corasick算法的实现提供多种模式搜索,该算法构建了一个有限状态机,用于在线性时间内执行搜索。 aho-corasick一个库,在某些情况下,可以通过SIMD加速一次发现许多模式。 该库主要通过Aho-Corasick...