多模匹配算法.ppt

title例如：对应模式集{he,she,his,hers}的树型有限自动机3.转向，失效和输出函数的构建
现在说明如何根据一个关键字集建立正确的转向、失效和输出函数。整个构建包含两个部分，在第一部分确定状态和转向函数，在第二部分我们计算失效函数。输出函数的计算则是穿插在第一部分和第二部分中完成。
为了构建转向函数，我们需要建立一个状态转移图。开始，这个图只包含一个代表状态0。然后，通过添加一条从起始状态出发的路径的方式，依次向图中输入每个关键字p。新的顶点和边被加入到图表中，以致于产生了一条能拼写出关键字p的路径。关键字p会被添加到这条路径的终止状态的输出函数中。当然只有必要时才会在图表中增加新的边。
例如:对关键字集{he,she,his,hers}建立转向函数。
向图表中添加第一个关键字，得到：增加第三个关键字“his”，我们得到了下面这个图。注意到当我们增加关键字“his”时，已经存在一条从状态0到状态1标记着h的边了，所以我们不必另外添加一条同样的边。添加第四个关键字“hers”，可以得到：这样，图已经成为一棵带根的树。为了完成转向函数的构建，我们对除了h和s外的其他每个字符，都增加一个从状态0到状态0的循环。这样，我们得到了如图1a)所示的状态转移图，这个图就代表转向函数。算法1：建立转向函数g。
输入：关键字集P={p1,p2,p3,…,pr}。
输出：转向函数g和部分的output函数。
方法:

失效函数是根据转向函数建立的。首先，我们定义状态转移图中状态s的深度为从状态0到状态s的最短路径。
例如图1a)起始状态的深度是0，状态1和3的深度是1，状态2，4，和6的深度是2，等等。计算思路：先计算所有深度是1的状态的失效函数值，然后计算所有深度为2的状态，以此类推，直到所有状态（除了状态0，因为它的深度没有定义）的失效函数值都被计算出。

计算方法：用于计算某个状态失效函数值的算法在概念上是非常简单的。首先，令所有深度为1的状态s的函数值为f(s)=0。假设所有深度小于d的状态的f值都已经被算出了，那么深度为d的状态的失效函数值将根据深度小于d的状态的失效函数值来计算。
为了计算深度为d状态的失效函数值，我们考虑每个深度为d-1的状态r，执行以下步骤：
Step1：如果对所有状态a的g(r,a)=fail，那么什么都不做

Step2：否则，对每个使得g(r,a)=s存在的状态s，执行以下操作
记state=f(r)。
零次或者多次令state=f(state)，直到出现一个状态使得g(state,a)!=fail（注意到，因为对任意字符a，g(0,a)!=fail，所以这种状态一定能够找到）

Step2：记f(s)=g(state,a)以图1a)为例说明计算的失效函数f；
先令f(1)=f(3)=0，因为1和3是深度为1的状态。
计算深度为2的状态2，6和4的失效函数。计算f(2)，令state=f(1)=0；由于g(0,a)=0，得到f(2)=0。计算f(6)，令state=f(1)=0；由于g(0,i)=0，得到f(6)=0。计算f(4)，令state=f(3)=0；由于g(0,h)=1，得到f(4)=1。
按这种方式继续，最终得到了如图1b)所示的失效函数f。
在计算失效函数的过程中，也更新了输出函数。当求出f(s)=s，时，我们把状态s的输出和状态s，的输出合并到一起。对于上文中的例子，从图1a)我们求出f(5)=2。这时，把状态2的输出集，也就是{he}，增加到状态5的输出集中，这样就得到了新的输出集合{he,she}。最终各状态的非空输出集如图1c)所示。算法2：建立失效函数f。
输入：转向函数g和部分的输出函数output。
输出：失效函数f和完整的输出函数output。
方法:
4.转向函数的构建
图1中树型自动机的状态有0,1,…,9。某个状态（通常是0状态）被指定为起始状态。
转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息。
图1a)的状态图代表转向函数g。比如,从0到1标记着h的边表示g(0,h)=1，如果缺省箭头则表示失败。可见，对除e和i之外的其他输入字符，都有g(1,h)=fail。所有的树型有限自动机都有一个共同的特点，即对任何输入字符a,都有g(0,a)!=fail。我们将看到，转向函数在0状态上的这种性质确保每个输入字符都可以在状态机的一个操作循环内被处理。举个例子，记树型有限自动机为状态机M。状态机M利用图1的函数去处理输入文本“ushers”，图4显示了M在处理文本串时产生的状态转移情况。记s为状态机的当前状态，a为输入文本y的当前输入字符。树型有限自动机的一次操作循环可以定义如下：
如果g(s,a)=s，，那么树型有限自动机将做一