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

• 作者: 刘燕兵 刘萍 方滨兴 郭莉
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 串匹配 字符概率分布 字符串相关性
• 年，卷（期）: 2010,（7）
• 页码范围: 1503-1514
• 分类号: TP301
• 字数: 10315字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.03613

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘萍	中国科学院计算技术研究所	35	435	11.0	19.0
3	方滨兴	中国科学院计算技术研究所	45	1371	19.0	36.0
7	郭莉	中国科学院计算技术研究所	64	788	14.0	26.0