有限自动机在模式匹配中的应用与研究

1、有限自动机在模式匹配中的应用与研究    摘 要：有限自动机匹配算法是多模式匹配中的重要算法. 反向有限自动机在一定的条件下能压缩自动机的规模，从而提高模式匹配的速度. 将反向有限自动机算法与 BM 算法相结合，利用当前获取信息进一步增大匹配过程中的跳跃距离，可进一步提高模式匹配的速度.关键词：模式串；有限自动机；模式匹配1 利用有限自动机实现字符串匹配有限自动M通常用一个五元组来表示，MQ，S，A，其中Q是状态的有限集合，即状态自动机中所有可能出现的转移状态；S是有线自动机的起始状态，其满足SQ；A是一个接受状态集合，它是Q的一个子集，通常一个字符串输

2、入完毕后，如果当前的状态是A中的一个元素，则表示该字符串被接受，否则表示被拒绝 所有可能的输入字母表集合，它一定是一个有限集，是构成字符串的基本元素集合 被称为状态转移函数，Q×Q的一个映射函数 有限状态自动机开始于S，每次读入输入的字符串的一个字符 如果当前有限自动机的状态为p，读入字符为a，则它从p变为状态（p，a）的过程就是一次转移 如果（p，a）Q，则表示自动机接受迄今为止输入的所有字符 而没有被接受的输入被称为拒绝的输入 当一个文本字符串被自动机读取过程中存在状态F A，则表示当前字符串被接受，匹配成功，否则匹配失败针对模式串，构造一个有穷自动机，那么，有穷自动机接收的语言

3、就是该模式串匹配的句子 对于每个模式串，都存在一个字符串匹配自动机，必须在预处理阶段，根据模式构造出相应的自动机后，才能利用它来搜索字符串 构造自动机的核心是构造其状态转移函数 这种方法功能比较强大，因为它可以搜索以正则式表达的模式串，而其他算法则不能因此有限自动机是解决模式串匹配问题的一种十分有效的方法，在众多领域有着广泛的应用5，尤其是在多模式匹配中，能仅通过对目标串的一次扫描，把所有的模式串都找出来132反向有限自动机匹配算法的思想有限自动机的构造过程是将模式串集合变换成由转向函数、失效函数和输出函数所组成的有限自动机 在正向有限自动机的构造中，模式串的字符是从前到后依次加到树型有限自动

4、机中的，匹配过程也是按照从前到后的次序 而在反向有限自动机的构造中，每个模式串的字符是从后到前，加到树型自动机中，同时在匹配过程中，目标串的输入也是从后往前的顺序，即逆向扫描例：以模式串集合he，me，re，she，are为例，构造的反向自动机如图 1 所示 由图 1 可知反向有限自动机匹配算法的状态数较少，特别是第一层节点的减少，将使匹配的平均速度大大提高 其中第一层节点是指只与起始节点0 相邻的第一层节点 下面再看利用该集合构造的正向有限自动机，结论就一目了然了（如图2 所示）由图 1、图 2 可以看出正向有限自动机的第一层的分支有 5 个，而反向自动机第一层只有 1 个分支，同时正向有限

5、自动机的转向函数 （0，a）在匹配时要比较 5 个字符，而反向有限自动机的转向函数 （0，a）只要比较 1 个字符，显然反向自动机的 （0，a）的计算速度要快 在匹配过程中转向函数 （p，a）的计算量是最大的部分之一，尤其当模式串在文本串中出现概率较低时，第一层的每一个分支几乎都要计算，因此提高（0，a）的计算速度对整个匹配过程速度的提高是至关重要的3 BM算法与反向有限自动机相结合文献2提出了 BM 算法 该算法在匹配过程中模式串 P0，1，m1由左向右移动，而字符比较由右向左进行比较，即 Pm1，Pm2，P0的次序，当某趟比较中出现不匹配的字符时，BM 采用两条启发式规则计算模式串移动的距

6、离，即 bad character shift rule 坏字符和 good suffix shift rule 好后缀规则31坏字符规则P 中的某个字符与 T 中的某个字符不相同时使用坏字符规则右移模式串 P，P 右移的距离可以通过Skip（x）函数计算出来 Skip（x）函数的定义如下：即如果字符 x 在模式 P 中没有出现，那么从字符 x 开始的 m 个文本显然不可能与 P 匹配成功，直接全部跳过该区域即可 如果 x 在模式 P 中出现，则以该字符进行对齐32 好后缀规则当不匹配发生时，如果 P 串中已有部分字符匹配，即形成后缀 Pj 1m，则可以用到此规则 第一种情况：P 串中的某一子

7、串js 1 ms与已匹配部分 pj1 m相同，可让 P 串右移 s 位距离 第二种情况：P串中已匹配部分 Pj 1 m的后缀s 1 m与 P 的前缀1 m s相同，可让 P 串右移 s位距离 选择上述两种情况的最小值 移动距离如 Shif（tj）函数所示：在 BM 算法匹配的过程中，取 Skip（x）与 Shif（tj）中的较大者作为跳跃的距离进一步提高模式匹配算法效率的主要途径就是利用当前已知信息进一步增大跳跃距离 利用上述 BM算法在匹配过程中跳跃式的优点，结合反向有限自动机的多模式匹配算法；先对模式串进行预处理，把模式串集合转换成一个反向的树型有限自动机，得出转向函数 （p，a）和输出函

8、数 outpu（tp），然后根据当前尝试中匹配失败字符的位置信息，分别计算坏字符规则Skip（x）和好后缀规则 Shif（tj），取 Skip（x）与 Shift（j）中的较大者作为跳跃的距离，就能够尽可能多地跳过待查文本串字符，从而进一步真正提高模式匹配的效率4 结束语有限自动机匹配算法是多模式匹配中的重要算法 ，如何进一步提高匹配的速度 ，如何压缩自动机的规模是大家所关注的问题 本文讨论了反向有限自动机的优点，指出采用反向有限自动机在一定的条件下能压缩自动机的规模，从而提高模式匹配的速度；将反向有限自动机算法与 BM 算法跳跃式匹配的特点相结合，利用当前获取信息进一步增大匹配过程中的跳跃距

9、离，可进一步提高模式匹配的速度 该算法的查找时间对模式串数目的增加不敏感，并且在模式串较长和较短的条件下，该算法都有相当好的性能 在应用中，可对模式串和目标文本串的特点作进一步的分析，使算法的速度能进一步得到提高参考文献1许一震 一种基于反向有限自动机的匹配算法J 高技术通讯，2001（2）：30332Cole R Tight Bounds on Complexity of the BoyerMoore String Matching Algorithm J SIAM Journal on Computing，1994，23（5）：107510913许一震 一种快速的多模式字符串匹配算法J 上海交通大学学报，2002，36（4）：5165204关超