基于匹配区域特征的相似字符串匹配过滤算法孙德才

摘要：

相似字符串匹配过滤算法因其适合大库查找而被广泛应用,为通过提高过滤算法的过滤效率加快匹配速度,提出一种基于匹配区域特征的过滤算法.该算法将模式串和文本串分割成固定长度为kq+1的逻辑块,并从各块中提取了2个新的匹配区域特征:q-gram命中的均匀性和q-gram有效命中的区域性.新算法利用这些新特征优化了传统过滤标准,提高了算法的过滤效率;并改进了QUASAR中基于分块策略的过滤区确定方案.实验结果表明,新算法与改进前相比有效地加快了匹配速度,尤其在误差率较小时改进效果更佳.

关键词：相似字符串匹配、过滤算法、匹配区域特征、过滤效率、q-gram

所属期刊栏目：47

分类号：TP391.3(计算技术、计算机技术)

资助基金：国家"九七三"重点基础研究发展计划基金项目2006CB303000;国家自然科学基金重点项目60736016;国家自然科学基金项目60573045,60873198,60973113,60973128;国家"九七三"重点基础研究发展计划基金前期研究专项项目2009CB326202;高等学校博士学科点专项科研基金项目20050532007

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

页数：共8页

页码：663-670