改进的多模式匹配算法

IMPROVED ALGORITHMS FOR MATCHING MULTIPLE PATTERNS

在有限自动机的多模式匹配算法 (DFSA算法 )的基础上 ,结合 Quick Search算法的优点 ,提出了一个快速的多模式字符串匹配算法 .之后在算法中以连续跳跃的思想 ,给出了另一个更加有效的改进 .在一般情况下 ,这两个算法不需要匹配目标文本串中的每个字符 ,并充分利用了匹配过程中本次匹配不成功的信息 ,跳过尽可能多的字符 .在模式串较长和较短的情况下 ,算法都有很好的性能 .实验表明 ,在模式串较短时 ,所提出的算法需要的匹配时间仅为 DFSA算法的 1/2到 1/5 ,在模式串较长时 ,所需时间为 DFSA算法的 1/3至

Combined with the advantages of the Quick Search algorithm, a faster algorithm to perform multiple patterns match in a string is put forward on the basis of deterministic finite state automata (DFSA). Another algorithm is presented with the improvement of the idea of the QS algorithm, and it can match more efficiently. Generally, the two algorithms do not need inspect every character of the string. They skip as many characters as possible by making full use of information in matching failure. The proposed algorithms achieve excellent performance in the cases of both short patterns and long patterns. The actual experiments show that in case of short patterns the time it takes for a proposed algorithm to search a string is only 1/2~1/5 that of the DFSA, while in case of long patterns the ratio is 1/3~1/7.