Aho Corasick算法

Question

问

Aho Corasick算法

天秤aaaaaaa_150 发布于 2023-02-13 14:01

我无法理解下面使用Aho-Corasick alg进行字符串模式匹配的算法.

Procedure AC(y,n,q0)
INPUT: y<-array of m bytes representing the text input
(SQL Query Statement)
n<-integer representing the text length
(SQL Query Length)
q0<-initial state (first character in pattern)
2: State <-q0
3: For i = 1 to n do
4: While g ( State, y[i] = = fail) do
5: State ? f (State)
6: End While
7: State ? g(State,.y[i])
8: If o(State)  then
9: Output i
10: Else
11: Output
12: End If
13: End for
14: End Procedure

Jim Mischel.. 26

通过阅读一些伪代码,您可能无法很好地理解Aho-Corasick算法.除非您了解状态转换表,否则算法根本没有意义.

在Aho-Corasick的实现和动画中有一个很好的解释和动画.

原始论文" 高效字符串匹配:对书目搜索的帮助"(PDF),写得很好且易于理解,伪代码示例很容易转换为工作代码.这需要一点点研究,但是在阅读完论文之后你应该有一个很好的理解,稍微考虑一下,然后再读一遍.

2 个回答

Aho Corasick算法用于解决集合匹配问题.这意味着我们有一组字符串S,这里有一个长字符串L来检查L是否包含前一组S中的任何一个.

一个基本的解决方案是使用trie树,即前缀树,请参阅维基百科.通常有两个步骤来处理问题.
trie树很容易理解.它存储带有节点的前缀子串从根开始.

Aho-Corasick算法是特里树的扩展,离基本思想不远.Aho-Corasick算法向trie树上的每个节点添加一个失败的指针.

失败时,trie树将从根目录重新启动(将L上的起始索引加1),但Aho-Corasick算法将从失败指针指向的节点D重新启动(在L的深度上添加起始索引)节点D).

下面是Aho-Corasick算法的C++实现.它包含一些错误. http://www.komodia.com/aho-corasick

我修复了我发现的错误.你可以在这里访问我的版本:https: //github.com/elfinhe/KomodiaAhoCorasick
2023-02-13 14:03 回答

Sheen2602906613
通过阅读一些伪代码,您可能无法很好地理解Aho-Corasick算法.除非您了解状态转换表,否则算法根本没有意义.

在Aho-Corasick的实现和动画中有一个很好的解释和动画.

原始论文" 高效字符串匹配:对书目搜索的帮助"(PDF),写得很好且易于理解,伪代码示例很容易转换为工作代码.这需要一点点研究,但是在阅读完论文之后你应该有一个很好的理解,稍微考虑一下,然后再读一遍.

2023-02-13 14:03 回答

海边遗忘的时光_958

撰写答案