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

Efficient top-k string similarity query algorithms

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

Computing top-k similar strings based on edit distance,i.e.,given a query string σ and string set S,finding k similar strings to σ based on edit distance from S.Firstly,two adaptive filter strategies based on length-skip index are proposed,such that to reduce the times of edit distance computation between two strings.Then the lower bound of edit distance between query string and unmatched string set is proposed,such that to further reduce the times of edit distance computation when processing strings that do not have common signatures with the query string.Finally efficient algorithms to return top-k similar strings are proposed.Experimental results on three real datasets verify the benefits over the state-of-the-art algorithm.