双向过滤的字符串相似连接验证方法

来源：计算机工程与应用杂志2017年第9期北京时间：

作者：黄 樱，宋春花，牛保宁

单位：太原理工大学 计算机学院，太原 030024

摘要：字符串相似连接是指在字符串集合中找出相似的字符串对，是许多应用的关键操作，寻找高效的字符串相似连接算法已成为研究热点。基于划分的过滤-验证方法（Pass-Join）与其他方法相比具有较高的效率。它按照字符串长度递增的顺序访问字符串集合，通过查找一个字符串的划分块是否存在于另一个字符串中，快速筛选出可能相似的字符串对（候选集），然后利用编辑距离进行相似性验证。研究发现，按照字符串长度递减的顺序进行过滤（长度递减过滤）的效果优于按照长度递增的顺序过滤（长度递增过滤）的效果，基于此，提出双向过滤-验证机制：在过滤阶段对长度递减过滤的结果再进行一次长度递增过滤，进一步减小候选集大小；在验证阶段利用双向过滤产生的两对划分块和其匹配子串分隔字符串对，从而减小需要验证的字符串的长度，加速验证过程。实验证明，双向过滤-验证算法在真实数据集上优于原算法。

关键词：字符串相似连接,双向过滤-验证机制,过滤-验证框架