通信学报 ›› 2014, Vol. 35 ›› Issue (12): 10-20.doi: 10.3969/j.issn.1000-436x.2014.12.002

• 学术论文 • 上一篇    下一篇

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

陈子阳1,2,韩玉俊1,王璿1,2,周军锋1,2   

  1. 1 燕山大学 信息科学与工程学院,河北 秦皇岛 066004
    2 河北省计算机虚拟技术与系统集成重点实验室,河北 秦皇岛 066004
  • 出版日期:2014-12-25 发布日期:2017-06-17
  • 基金资助:
    国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;河北省教育厅研究计划基金资助项目;河北省科学技术研究与发展计划科技支撑计划基金资助项目

Efficient top-k string similarity query algorithms

Zi-yang CHEN1,2,Yu-jun HAN1,Xuan WANG1,2,Jun-feng ZHOU1,2   

  1. 1 School of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China
    2 Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province,Qinhuangdao 066004,China
  • Online:2014-12-25 Published:2017-06-17
  • Supported by:
    The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The Research Funds From Education Department of Hebei Province;The Science and Technology Research and Development Program of Hebei Province

摘要:

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

关键词: 字符串相似性, 非对称特征方案, 长度跳跃索引

Abstract:

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 dis-tance 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.

Key words: string similarity, asymmetric signature scheme, length-skip index