随着信息技术的迅速发展,涌现了大量Web数据,并且这些数据得到广泛的利用,特别是在企业应用中,因此对企业的数据处理能力提出了更高的要求。相似查询成为了在海量数据中获得满足一定条件数据的方式。目前基于refine and filter框架的字符串相似过滤算法主要包含索引建立、相似过滤、相似验证三个步骤,建立索引的空间复杂度和过滤以及验证的时间复杂度一直是相似过滤算法关注的焦点,很多学者都在对此类问题进行深入研究并提出各自的解决方案。本文先从字符串相似查询的研究背景、意义出发,通过介绍基本理论知识,引出字符串相似查询的概念,随后综述了近年来字符串相似查询的相关研究成果,介绍了目前主流的字符串相似查询算法,并进行了一定的分析和比较。针对大多数现有的基于分片的字符串近似匹配算法在集合中字符串长度差异比较大时的效率问题,本文基于字符串的特征模式进行字符串近似匹配。首先提出了字符串的特征模式—MC-Substring的概念;其次改进了求解LCS的并行算法用以求解字符串的特征模式,并基于字符串的特征模式来对整个字符串数据库进行索引的构建;然后根据提出的一系列过滤规则,在构建的索引基础之上对字符串进行过滤,形成候选集;最后通过gapped gram和编辑距离对候选集合进行验证,输出最终结果集。本文实验部分从算法效率,即时间和空间复杂度方面以及算法的可伸缩性方面进行分析和验证。实验证明,本文从文本分片的角度提出的字符串近似匹配算法,利用相关的并行算法,计算字符串的特征模式,在特征模式之上构建索引结构,在一定程度上可以提高字符串相似查询的效率,为从数据挖掘的角度处理字符串相似查询的问题提供了 一定的可能。