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

• 作者: 刘洪磊 杨晓春 王斌 金蓉
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 子串查询 模糊查询 gram索引 编辑距离
• 年，卷（期）: 2011,（9）
• 所属期刊栏目: 学术研究
• 页码范围: 769-780
• 分类号: TP311.131
• 字数: 8626字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2011.09.001

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘洪磊	东北大学信息科学与工程学院	32	458	13.0	20.0
2	杨晓春	东北大学信息科学与工程学院	65	1090	16.0	32.0
3	王斌	东北大学信息科学与工程学院	101	945	14.0	28.0
4	金蓉	东北大学信息科学与工程学院	1	1	1.0	1.0