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

• 作者: 宋春花 牛保宁 黄樱
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 字符串相似连接 双向过滤-验证机制 过滤-验证框架
• 年，卷（期）: 2017,（9）
• 所属期刊栏目: 大数据与云计算
• 页码范围: 72-79
• 页数: 8页
• 分类号: TP391
• 字数: 9526字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1512-0309

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	牛保宁	太原理工大学计算机学院	37	146	5.0	11.0
2	宋春花	太原理工大学计算机学院	11	9	1.0	2.0
3	黄樱	太原理工大学计算机学院	4	3	1.0	1.0