高效的top-k相似字符串查询算法

• 作者: 周军锋 王璿 陈子阳 韩玉俊
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 字符串相似性 非对称特征方案 长度跳跃索引
• 年，卷（期）: 2014,（12）
• 所属期刊栏目: 学术论文
• 页码范围: 10-20
• 页数: 11页
• 分类号: TP311
• 字数: 9496字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-436x.2014.12.002

摘要

研究基于编辑距离的top-k相似字符串查询处理方法,即对于给定的字符串集合S和查询串σ,返回S中前k个与σ编辑距离最小的字符串.首先提出了基于长度跳跃索引的2种自适应过滤策略来减少字符串之间编辑距离的计算次数;其次提出了查询字符串与不匹配字符串集合的编辑距离下界,以便在处理和σ无公共特征的字符串时,进一步减少编辑距离的计算次数;最后给出了基于上述过滤策略的高效top-k相似字符串查询算法,并在3个真实的数据集上进行了实验,实验结果验证了所提算法的高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈子阳	燕山大学信息科学与工程学院	27	100	6.0	9.0
3	周军锋	燕山大学信息科学与工程学院	21	167	6.0	12.0
5	王璿	燕山大学信息科学与工程学院	14	49	4.0	6.0
13	韩玉俊	燕山大学信息科学与工程学院	1	4	1.0	1.0