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

来源：计算机科学与探索杂志2018年第1期北京时间：

作者：刘慧婷，黄厚柱，刘志中，赵鹏

单位：安徽大学 计算机科学与技术学院，合肥 230601

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

关键词：字符串相似性查找,阈值,top-k,分割,编辑距离