改进的多模式匹配算法  

IMPROVED ALGORITHMS FOR MATCHING MULTIPLE PATTERNS

作　　者：王永成[1] 沈州[1] 许一震[1] 

机构地区：[1]上海交通大学计算机科学与工程系,上海200030

出　　处：《计算机研究与发展》2002年第1期55-60,共6页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金资助 (863 -3 0 6-ZD0 3 -0 4-1)

摘　　要：在有限自动机的多模式匹配算法 (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.

关 键 词：算法复杂度 多模式匹配算法 有限自动机 计算机 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]