相似性连接作为数据处理过程的基本操作,在数据清洗、相似网页搜索和生物信息学等领域有广泛的应用,而数据规模和数据类型的不断增长与变化给相似性连接带来了挑战。现有的一些基于过滤验证框架的字符串相似性连接算法虽然可以提升相似连接效率,但是仍存在过滤能力不足以及不能很好地适应长度差异较大的字符串集合等问题。因此,为了满足相似性连接算法高效率、高精度的需求,本文主要对基于过滤验证框架的字符串相似性连接算法进行了研究,主要工作和贡献如下:针对现有算法的过滤能力逐渐满足不了大规模数据集等情况,设计了一种基于划分的双重过滤相似性连接算法(Double Filtering string similarity join algorithm based on Partition,DFP-ssj)。该算法首先将字符串集合划分为若干个子集;然后在对各个子集以及子集间进行相似连接的过程中使用了基于长度过滤方法来减少算法的时间消耗;为了进一步提高过滤能力,算法中利用前缀过滤算法对初始候选对进行删减来得到最终候选对,并对其进行基于编辑距离的验证。最后根据实验结果分析,DFP-ssj算法在过滤能力和相似连接效率上均有提升。针对在类似基因序列长字符串集合的相似性连接结果中存在大量伪正例的问题,本文设计了一种基于局部敏感哈希(Locality Sensitive Hashing,LSH)的字符串相似性连接方法,并利用过滤验证框架实现该方法。考虑到计算长字符串之间编辑距离的复杂性,该方法使用嵌入方法将编辑空间中的所有字符串嵌入到汉明空间中;然后利用LSH来对汉明空间中的数据进行映射,在此过程中利用长度过滤和基于k值的过滤方法对伪正例进行删减。通过实验分析,基于LSH的相似性连接方法能有效的降低伪正例的数量,并具有较好的相似性连接效率。