进入二十一世纪,信息技术的快速发展,计算机的普及,互联网的广泛应用,全球信息共享日益加大,信息量爆炸式的增长。在大量的信息面前,如何准确地、快速地找到我们需要的信息。这一直是计算机科学研究的热点问题。字符串的相似连接技术是一种比较有效的解决上述问题的办法,它能从一个被查询字符串集合中找出与给定的查询字符串相似程度满足一定要求的所有字符串。字符串的相似连接技术在信息检索、学术不端检测系统、生物信息学、入侵防御、垃圾邮件过滤等领域有着巨大的应用空间。但随着计算机网络的高速发展,信息量爆炸式的增长,传统方法面临着查询速度慢的挑战。因此,本文研究提高字符串相似连接的查询速度具有一定的意义。本文主要研究字符串在采用编辑距离为相似度函数的相似连接。通过基于q-gram技术的字符串分割,分割后的字符串片段基于trie树实现倒排索引,通过索引归并算法筛选掉不可能是结果的字符串,最后对候选结果进行验证。本文采用了两种办法提高算法的查询速度。一是基于trie树实现倒排索引。trie树是树形结构,可以利用字符串的公共前缀提高索引的查找速度。利用trie树实现的倒排索引不仅能够提高现有算法的查询速度而且在具有较多公共前缀的字符串面前具有更高的效率。二是通过左向填充算法和长度过滤算法相结合的办法对现有算法进行优化。左向填充算法可在一定程度上提高公共字符串片段的数量,使更多的被查询字符串能够使用索引归并算法进行筛选,减少验证阶段需要验证的字符串数量,提高算法的查询速度。长度过滤算法因其过滤条件简单且有效,能过滤掉一些不是结果的字符串,同样减少了验证阶段需要验证的字符串数量。索引归并算法与长度过滤算法相结合可进一步提高算法的查询速度。