支持局部最优化匹配的近似子串查询算法

摘要：

基于编辑距离的字符串近似查询算法一般是先给定阈值k,然后计算那些与查询串的编辑距离小于或等于k的结果.但是对于近似子串查询,结果中有很多是交叠的,并且是无意义的,于是提出了一种局部最优化匹配的概念,只计算那些符合阈值条件,并且是局部最优的结果,这样不仅避免了结果的交叠,而且极大节省了时间开销.给出了支持局部最优化匹配的近似子串查询的定义,相应提出了一种基于gram 索引的局部最优化近似子串查询算法,分析了子串近似匹配过程中的规律,研究了基于局部最优化匹配的边界限定和过滤策略,给出了一种过滤优化的局部最优化近似子串查询算法,提高了查询效率.

关键词：子串查询、模糊查询、gram索引、编辑距离

所属期刊栏目：5

分类号：TP311.131(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.60973018,60973020,61173031;theFundamental Research Funds for the Central Universities under Grant No.N090504004,N100704001,N090104001

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

页数：共12页

页码：769-780