多模匹配算法.ppt

多模匹配算法
第1页，共28页，2022年，5月20日，14点7分，星期二
title
Aho-Corasick自动机算法（简称AC自动机）1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。
该态s的函数值为f(s) = 0。假设所有深度小于d的状态的f值都已经被算出了，那么深度为d的状态的失效函数值将根据深度小于d的状态的失效函数值来计算。
第12页，共28页，2022年，5月20日，14点7分，星期二
为了计算深度为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)
第13页，共28页，2022年，5月20日，14点7分，星期二
以图1 a)为例说明计算的失效函数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。
按这种方式继续，最终得到了如图1 b) 所示的失效函数f。
在计算失效函数的过程中，也更新了输出函数。当求出f(s) = s，时，我们把状态s的输出和状态s，的输出合并到一起。对于上文中的例子，从图1 a) 我们求出f(5) = 2。这时，把状态2的输出集，也就是{he}，增加到状态5的输出集中，这样就得到了新的输出集合{he, she}。最终各状态的非空输出集如图1 c) 所示。
第14页，共28页，2022年，5月20日，14点7分，星期二
算法2：建立失效函数f。
输入：转向函数g和部分的输出函数output。
输出：失效函数f和完整的输出函数output。
方法:
图3 建立失效函数f的伪代码
第15页，共28页，2022年，5月20日，14点7分，星期二
4. 转向函数的构建
图1中树型自动机的状态有0, 1, …, 9。某个状态（通常是0状态）被指定为起始状态。
转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息。
图1 a) 的状态图代表转向函数g。比如,从0到1标记着h 的边表示g(0, h) = 1，如果缺省箭头则表示失败。可见，对除e和i之外的其他输入字符，都有g(1, h) = fail。所有的树型有限自动机都有一个共同的特点，即对任何输入字符a, 都有g(0, a) != fail。我们将看到，转向函数在0状态上的这种性质确保每个输入字符都可以在状态机的一个操作循环内被处理。
第16页，共28页，2022年，5月20日，14点7分，星期二
举个例子，记树型有限自动机为状态机M。状态机M利用图1的函数去处理输入文本“ushers”，图4显示了M在处理文本串时产生的状态转移情况。
考虑M在状态4，且当前输入字符为e时的操作循环。由于g(4, e) = 5，状态机进入状态5，文本指针将前进到下一个输入字符，并且输出output(5)。这个输出表明状态机已经发现输入文本的第四个位置是“she”和“he”出现的结束位置。在状态5上输入字符r，状态机M在此次操作循环中将产生两次状态转移。由于g(5, r) = fail，M进入状态2 = f(5)。然后因为g(2, r) = 8，M进入状态8，同时前进到下一个输入字符。在这次操作循环中没有输出产生。
图4 扫描“ushers”时的状态转换序列
第17页，共28页，2022年，5月20日，14点7分，星期二
记s为状态机的当前状态，a为输入文本y的当前输入字符。树型有限自动机的一次操作循环可以定义如下：
如果g(s, a) = s，，那么树型有限自动机将做一个转向动作。自动机进入状态s，而且y的下一个字符变成当前的输入字符。另外，如果output( s，)不为空，那么状态机将输出与当前输入字符位置相对应的一组关键字。
如果g