相似性连接技术在众多应用中是一项基础且重要的操作,即在字符串集合中找出所有符合给定条件的相似对。通常情况下,通过一个相似性度量函数和阈值来判断两个串是否相似,如果度量函数求出两个串的相似值小于阈值,则这两个字符串相似,反之,则不相似。相似性连接技术在许多方面具有广泛的应用,例如数据清洗和整合、模糊匹配、协同过滤、基因匹配、重复对象检测和删除等等。因此,在过去一段时间,业内对相似性连接技术进行了大量研究,并且取得了丰硕的科研成果。现有的相似性连接技术算法主要有两种类型,其中一种为过滤验证框架,另一种为借助于Trie树方法。过滤验证框架主要有两个过程组成,过滤和验证。在过滤阶段,通过某种算法淘汰掉一些非潜在的相似字符串对,并且产生候选相似对,接下来在验证过程,利用某种测量函数来验证候选相似字符串对是否相似。借助于Trie树结构的连接方法主要通过共享前缀以及活跃节点来判断两个串是否匹配。目前,比较主流的相似性连接算法主要有Ed-Join、Trie-Join、Pass-Join等等,在这上述些算法中,Pass-Join算法拥有比较好的整体性能。然而Pass-Join仍然存在不足,即在过滤阶段,过滤不充分,容易将大量非潜在相似字符串纳为候选相似字符串,导致验证阶段计算加重,执行时间长。针对Pass-Join存在的不足,本文提出了 GFSF算法,该算法基于字符频率向量在Pass-Join算法过滤阶段引入两层额外的过滤步骤全局过滤和局部过滤。当Pass-Join算法在过滤阶段每产生一对候选相似字符串对时,通过全局过滤来判断这个候选相似字符串对是否满足全局过滤条件,如果满足,则再进行局部过滤。如果同时满足全局过滤和局部过滤,那么这个候选相似字符串最后进入验证阶段。如果这个候选字符串对不满足全局过滤或者局部过滤任何一个,那么这两个候选相似字符串则不可能相似,即可以直接淘汰。并且,全局和局部过滤的时间复杂度低于Pass-Join的验证过程,因此通过两层过滤淘汰大量的非潜在相似字符串,可以极大提高GFSF算法的整体性能。通过这两层过滤,可以大大减少候选相似字符串的数量,进而大大降低验证阶段所消耗的时间,最终实现性能的提升。最后的实验结果证明了 GFSF算法的性能好于Pass-Join算法。