aho corasick算法的状态转换表

Question

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

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

我跟着this纸和here是这样的动画。

谢谢。用一个例子

Starting at the root, follow the path labeled by chars of Pi 
     If the path ends before Pi, continue it by adding new edges and ... 
          nodes for the remaining characters of P 
     Store identifier i of Pi at the terminal node of the path

我演示一下：

Answer 1

阶段1

创建关键字树

假设我们有一组有限的模式P = {他，她，他的，她的}。

相位2

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

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

• 状态
• 过渡

国：完全按关键词树实现的节点;并且初始状态=树的根。

过渡：使用转到（Q，A）功能如下。

/*This function gives the state entered from current state q 
    by matching target char a*/ 
- If edge (q,v) in the tree is labeled by a, then g(q,a)=v; 
- g(0,a)=0 for each a that does not label an edge out of the root 
//the automton stays at the initial state while scanning non-matching characters  
- O.W. 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; 

正如你在上面的伪代码中看到它调用了两个函数：失败（Q）和输出（Q ）

失败（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 

这两个函数计算后，自动机是这样的：

现在你可能想知道何时计算这些方法，所以请看看这些更多的官方表格：

希望这帮助，如果仍然事情是不明确的，请不要犹豫，问。