6

我无法理解以下用于使用 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
4

2 回答 2

26

通过阅读一点伪代码，您可能无法很好地理解 Aho-Corasick 算法。除非您了解状态转换表，否则该算法将毫无意义。

在Aho-Corasick implementation and animation有一个不错的解释以及动画。

原始论文Efficient String Matching: An Aid to Bibliographic Search (PDF) 写得很好且易于理解，伪代码示例很容易转换为工作代码。这需要一点学习，但你应该在阅读论文后有一个很好的理解，思考一下，然后再读一遍。

于 2013-12-02T14:42:57.603 回答
7

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

一个基本的解决方案是使用 trie 树，即前缀树，请参阅Wikipedia。通常有两个步骤来处理该问题。

  1. 根据字符串集S预计算trie树；
  2. 扫描字符串 L 进行检查。

trie树很容易理解。它存储具有从根开始的节点的前缀子串。

Aho-Corasick 算法是对 trie 树的扩展，与基本思想相距不远。Aho-Corasick 算法为 trie 树上的每个节点添加一个失败的指针。

失败时，trie树将从根节点重新开始（L上的开始索引加1），但Aho-Corasick算法将从失败指针指向的节点D重新开始（L上的开始索引加1的深度）节点 D)。

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

我修复了我发现的错误。你可以在这里访问我的版本： https ://github.com/elfinhe/KomodiaAhoCorasick

于 2013-12-02T15:51:14.237 回答