基于存储优化的多模式串匹配算法

被引：6

作者：

刘燕兵 ^{[1
,2
]}

刘萍 ^{[1
]}

谭建龙 ^{[1
]}

郭莉 ^{[1
]}

机构：

[1] 中国科学院计算技术研究所

[2] 中国科学院研究生院

来源：

计算机研究与发展 | 2009年 / 46卷 / 10期

关键词：

网络内容过滤; 多模式串匹配; 后缀树; 双数组结构; 自动机压缩;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

多模式串匹配算法是网络内容过滤系统的核心技术之一.自动机的存储空间大小和Cache性能是影响多模式串匹配算法速度的关键因素.随着模式串规模的扩大,自动机的巨大存储开销导致现有的串匹配算法性能大幅度下降.从压缩存储空间以提高Cache命中率的思想出发,提出了一种对经典SBOM算法的优化策略,它用Suffix Tree代替SBOM算法中的Factor Oracle结构,同时用剪枝的方法将Suffix Tree降低为近似线性的空间复杂度,然后用双数组Trie表示之,以压缩存储空间.与SBOM算法相比,改进算法不仅能够有效地节省存储空间,而且显著地提高了串匹配的速度,非常适合于在线高速匹配的应用环境.

引用

页码：1768 / 1776

页数：9

共 10 条

[1] 一种时间复杂度最优的精确串匹配算法
贺龙涛
方滨兴
余翔湛
[J]. 软件学报, 2005, (05) : 676 - 683
[2] Tetris–Hashing or optimal table compression[J] . Nicola Galli,Bernhard Seybold,Klaus Simon.Discrete Applied Mathematics . 2001 (1)
[3] An efficient representation for implementing finite state machines based on the double-array[J] . Shoji Mizobuchi,Toru Sumitomo,Masao Fuketa,Jun-ichi Aoe.Information Sciences . 2000 (1)
[4] A NEW APPROACH TO TEXT SEARCHING
BAEZAYATES, R
GONNET, GH
[J]. COMMUNICATIONS OF THE ACM, 1992, 35 (10) : 74 - 82
[5] OPTIMIZATION OF PARSER TABLES FOR PORTABLE COMPILERS
DENCKER, P
DURRE, K
HEUFT, J
[J]. ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1984, 6 (04): : 546 - 572
[6] Storing a Sparse Table with 0 （1） Worst Case Access Time[J] . Michael L. Fredman,János Komlós,Endre Szemerédi.Journal of the ACM （JACM） . 1984 (3)
[7] STORING A SPARSE TABLE
TARJAN, RE
YAO, ACC
[J]. COMMUNICATIONS OF THE ACM, 1979, 22 (11) : 606 - 611
[8] A fast string searching algorithm[J] . Robert S. Boyer,J. Strother Moore.Communications of the ACM . 1977 (10)
[9] Efficient string matching[J] . Alfred V. Aho,Margaret J. Corasick.Communications of the ACM . 1975 (6)
[10] Flexible pattern matching in strings: practical on-linesearch algorithms for texts and biological sequences. Navarro G,Raffinot M. Cambridge UniversityPress . 2002

← 1 →