基于分割的字符串相似性查找算法

• 作者: 刘志中 刘慧婷 赵鹏 黄厚柱
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 字符串相似性查找 阈值 top-k 分割 编辑距离
• 年，卷（期）: 2018,（1）
• 所属期刊栏目: 人工智能与模式识别
• 页码范围: 120-133
• 页数: 14页
• 分类号: TP301
• 字数: 12180字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.1609018

摘要

字符串相似性查找问题主要包括两方面,基于阈值的字符串相似性查找以及top-k字符串相似性查找.目前处理基于阈值的字符串相似性查找问题的算法多是基于过滤-验证框架的.基于该框架提出了PB-search算法,算法在过滤阶段首次加入One-Off条件过滤掉大量的无效匹配,并在验证阶段提出了一种新的验证算法MultiThreshold算法,大大减少了计算编辑距离的次数.在top-k字符串相似性查找问题方面,提出了两种基于分割思想的算法,Pb-topk算法和PbCount-topk算法.其中,Pb-topk算法采用差值递增的策略,减少了需处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模.最后,通过在3个真实数据集上的实验结果,验证了提出算法的高效性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵鹏	安徽大学计算机科学与技术学院	61	683	15.0	24.0
2	刘慧婷	安徽大学计算机科学与技术学院	64	1093	15.0	31.0
3	黄厚柱	安徽大学计算机科学与技术学院	1	6	1.0	1.0
4	刘志中	安徽大学计算机科学与技术学院	2	8	2.0	2.0