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

摘要：

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

关键词：串匹配、字符概率分布、字符串相关性

所属期刊栏目：21

分类号：TP301(计算技术、计算机技术)

资助基金：the National Basic Research Program of China under Grant No.2007CB311100 国家重点基础研究发展计划973

在线出版日期：2010-09-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：1503-1514