串匹配算法中模式串与文本之间关系的研究

被引：29

作者：

刘萍 ^{[1
,2
]}

刘燕兵 ^{[1
,3
,2
]}

郭莉 ^{[1
,2
]}

方滨兴 ^{[1
,2
]}

机构：

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

[2] 信息内容安全技术国家工程实验室

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

来源：

软件学报 | 2010年 / 21卷 / 07期

关键词：

串匹配; 字符概率分布; 字符串相关性;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

080201 [机械制造及其自动化];

摘要：

经典的串匹配算法设计和分析中假设"字符互相独立并且等概率出现",这与实际应用环境差异很大,导致出现很多问题.考虑了字符的概率分布和上下文的关联,同时兼顾应用的方便,提出了命中密度的概念.在给出基本定义和扩展定义后,通过对4种类型的代表性算法的理论和实验分析,给出了命中密度与算法性能之间的关系.同时,在对命中密度的分析中得出一些极具价值的结论.对命中密度概念的多角度理解以及对它与算法性能关系的深入剖析都说明,命中密度作为一个特征量,可以从一个侧面刻画模式串和文本之间的相关性,它对算法的设计和分析以及串匹配领域研究工作的扩展都具有指导意义.

引用

页码：1503 / 1514

页数：12

共 8 条

[1]

Average complexity of exact and approximate multiple string matching.[J].Gonzalo Navarro;Kimmo Fredriksson.Theoretical Computer Science.2004, 2

[2]

A fast string searching algorithm.[J].Robert S. Boyer;J. Strother Moore.Communications of the ACM.1977, 10

[3]

Efficient string matching.[J].Alfred V. Aho;Margaret J. Corasick.Communications of the ACM.1975, 6

[4]

多模式匹配算法及硬件实现 [J].