相似字符串查找在现实生活中的应用非常广泛,例如相似网页检测、数据清洗、电商网站的推荐功能、蛋白质功能预测等。相似字符串查找多是用一个给定的相似性函数来判断两个字符串是否相似。相似性函数有多种,例如汉明距离、编辑距离、余弦度量以及杰卡德度量等,其中使用较为广泛的为编辑距离。目前,基于相似性函数的相似字符串查找的研究可分为三类,即基于阈值的相似字符串查找、top-k相似字符串查找和相似字符串连接。然而随着用户需求的不断变化,基于相似性函数的相似字符串查找已不能很好地满足用户需求,于是带通配符的字符串查找逐渐被研究者们重视起来。本文主要研究了三种类型的相似字符串查找问题,即基于阈值的相似字符串查找、top-k相似字符串查找及带通配符的字符串查找。在基于阈值的相似字符串查找问题方面,目前处理该类问题的算法多是基于过滤——验证框架的。本文基于该框架提出了 PBsearch算法,并且分别在过滤和验证阶段对该算法进行了优化。在过滤阶段使用了长度过滤、数量过滤和位置过滤,并且首次加入One-Off条件过滤掉大量的无效匹配;在验证阶段提出了一种新的验证算法——MultiThreshold算法,有效地减少了计算编辑距离的次数。在top-k相似字符串查找问题方面,提出了两种基于分割思想的算法——Pb-topk算法和PbCount-topk算法。其中,Pb-topk算法采用差值递增的策略,减少了需要处理的字符串数目;PbCount-topk算法采用匹配数目划分的策略,进一步缩小了候选集的规模。在带通配符的字符串查找问题方面,研究了带"?"和"*"两种通配符的字符串查找问题。虽然Patricia trie索引结构具有高效的前缀共享性,然而在查询效率上仍有待提高。本文提出了基于Patricia trie结构的改进结构——w-trie结构,提高了 Patriciatrie结构的查询效率。该结构在内节点处多了一个通配符分支,给定一个通配符约束k,w-trie每一个内节点消耗一个通配符,直到从根节点到当前节点的分支上已经满足通配符约束k。最后基于该结构提出了带通配符的字符串查找算法,并在查找过程中加入长度过滤策略过滤掉部分一定不满足通配符约束的字符串,进一步提高了查找效率。最后,通过在三个真实数据集上的实验结果,分别验证了本文提出的算法在解决基于阈值的相似字符串查找、top-k相似字符串查找以及带通配符的字符串查找这三类问题上的高效性。