改进的多模式字符串匹配算法

被引：10

作者：

蔡晓妍

戴冠中

杨黎斌

机构：

[1] 西北工业大学自动化学院

来源：

计算机应用 | 2007年 / 06期

关键词：

字符串匹配; AC算法; BMH算法; 多模式匹配; 算法复杂度;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

在经典的AC多模式字符串匹配算法的基础上,结合BMH算法的优点,提出了一种快速的多模式字符串匹配算法。一般情况下,该算法不需要匹配目标文本串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配。在模式串较长和较短的情况下,算法都有很好的性能。实验表明,在模式串较短时,本算法所需的时间仅为AC算法的50%～30%;在模式串较长时,所需时间为AC算法的26.7%～15.2%。

引用

页码：1415 / 1417

页数：3

共 7 条

[1]

Fast Multipattern Search Algorithms for Intrusion Detection. KURI J,NAVARRO G,ME L. Fundamenta Informaticae . 2003

[2]

Handbook of Exact String Matching Al-gorithms. CHARRAS C,LECROQTT. . 2004

[3]

Practical fast searching in strings. NIGEL HR. Software Practice and Experience . 1980

[4]

An Efficient Algorithm for Matching Multiple Pat-terns. FAN JJ,SUKH. IEEE Transactions on Knowledge and Data Engineering . 1993

[5]

Efficient string matching:an aid to bib-liographic search. AHO AV,CORASICK MJ. Communications of the ACM . 1975

[6]

Fast pattern matching in strings. KNUTHD,MORRIS J,PRATTV. SIAM Journal on Computing . 1977

[7]

Afast string searching algorithm. BOYER RS,MOORE JS. Communications of the ACM . 1977

← 1 →