通信学报 ›› 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

[1] 陆 璐,周 维. 适用于H.264的快速模式选择算法[J]. 通信学报, 2006, 27(7): 19 -121 .
[2] 李 晖,顾学迈. 多层卫星通信网络自适应路由策略[J]. 通信学报, 2006, 27(8): 22 -128 .
[3] 刘 军,廖建新,朱晓民,王 纯. 用于移动计算环境的口令认证协议研究[J]. 通信学报, 2007, 28(5): 6 -42 .
[4] 冯明君,何明星. 新的基于双线性对的门限代理签名方案[J]. 通信学报, 2007, 0(08A): 9 -47 .
[5] 孙 岳,李 颖,王新梅. 基于重叠调制的自适应编码协作通信[J]. 通信学报, 2008, 29(11A): 12 -65 .
[6] 金 明,李有明,高 洋. 基于广义特征值的合作频谱感知方法[J]. 通信学报, 2013, 34(1): 12 -110 .
[7] 达 婷,李芝棠. 基于带权值无向图的视频隐写分析[J]. 通信学报, 2014, 35(Z1): 6 -30 .
[8] 来天平,王素美,彭一明,沈 苗,高志同. 高校学生全信息查询通用信息模型的研究与实现[J]. 通信学报, 2014, 35(Z1): 32 -169 .
[9] 罗玎玎,赵 海,孙佩刚,张希元,尹震宇. RM算法的运行时开销研究与算法改进[J]. 通信学报, 2008, 29(2): 12 -86 .
[10] 马世聪,卢泽新,张晓哲,王 尚. 链路虚拟化关键技术研究[J]. 通信学报, 2011, 32(9A): 39 -282 .