algorithm - aho corasick 算法的状态转换表

Question

请帮助我了解 Aho-Corasick 算法中多个模式的状态转换表的构造。

请给出一个简单而详细的解释，以便我理解。

我正在关注这篇论文，这里是动画。

谢谢。

Answer 1

阶段1

创建关键字树：

从根开始，遵循由 P i的字符标记的
        路径 如果路径在 P i之前结束，则通过添加新边和...继续它
                            P 的剩余字符的节点将 P i的
        标识符 i 存储在路径的终端节点处

我通过一个例子来证明它：

假设我们有一组有限的模式 P = {he, she, his, hers}。

阶段2

接下来我们将关键字树扩展为自动机，以支持线性时间匹配，如下所示。

显然，自动机由两部分组成：

• 状态
• 过渡

States：正是关键字树实现的节点；初始状态 = 树的根。

转换：使用goto(q,a)函数如下。

 
     /*这个函数通过匹配目标char a给出从当前状态q进入的状态*/
- 如果树中的边(q,v)由a标记，则g(q,a)=v；
- g(0,a)=0对于每个没有标记根边缘的a
//自动机在扫描不匹配字符时保持初始状态       
- OW g(q,a) ={}

使用自动机：

SearchofTarget T[1..m] //considering the target string T as an 
                     array of chars indexed from 1   to m
q:= 0; // initial state(root)
for i:= 1 to m do
    while g(q,T[i]) == {}  do 
        q:= fail(q); // follow a fail
    q:= goto(q,T[i]); // follow a goto
    if output(q) != {} then print i, out(q);
endfor;

正如你在上面的伪代码中看到的，它调用了两个函数：fail(q)和output(q)

fail(q) : // for q !=0 给出在不匹配时输入的状态

failure(q) is the node labeled by the longest proper suffix  w of L(q) ...
    s.t. w is a prefix of some pattern
//L(q) is the label of node q as the concatenation of edge labels ...
   on the path from the root to q

输出（q）：

gives the set of patterns recognized when entering state q

在计算这两个函数之后，自动机看起来像这样：

现在您可能想知道何时计算这些方法，因此请查看这些以获得更正式的形式：

希望这能有所帮助，如果仍有歧义，请随时提问。