改进的多模式匹配算法

被引：55

作者：

王永成

沈州

许一震

机构：

[1] 上海交通大学计算机科学与工程系,上海交通大学计算机科学与工程系,上海交通大学计算机科学与工程系上海,上海,上海

来源：

计算机研究与发展 | 2002年 / 01期

关键词：

匹配; 字符串; 有限自动机; 多模式匹配; 算法复杂度; 信息检索;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：55 / 60

页数：6