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

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