随着计算机的发展,社会中各行各业都离不开计算机,同时计算机可以给人们带来很大的方便和创新。字符串在计算机领域中是一种重要且基础的存储结构。现如今大量的数据都是以字符串这种数据结构的形式存放的。如何在给定的大规模字符串集合中高效率地找到与用户输入相匹配的字符串一直是个重要的研究问题。尤其是实现对字符串的近似匹配具有重要的现实意义和技术挑战。文本着重研究基于编辑距离的近似字符串匹配问题,研究高效率的匹配算法。本文首先综述了经典的支持编辑距离的近似字符串匹配技术,并分析出现有的方法都采用公共匹配因子进行过滤的思想。基于此,提出了局部过滤的匹配思想,即两个不相似的字符串一定由若干个不相似的片段组成。为了过滤掉不相似的字符串对,需要找到一些不相似的片段。本文首先定义局部距离的概念以用来度量两个字符串之间的局部不相似这个特性。根据局部距离的定义提出了局部距离的累加定理来进行过滤。提出了带有位置约束的局部过滤以提高算法的过滤能力。本文还设计了一种索引结构BitTree来管理带有位置约束的局部距离。根据这个索引结构设计两种算法对字符串集合中的字符串进行过滤。另外,局部距离同样可以在验证阶段使用。由于BitTree索引结构存储空间很大,本文提出了新的索引结构PBitTree索引和CoreBitmap索引来减少空间复杂度,同时设计出一种局部过滤的估计算法来进行字符串的过滤。本文在三个真实的数据集上和如今三个主流的算法进行实验。实验结果显示局部过滤方法的运行时间,过滤能力和索引大小都要好于其余三个算法。并且本文提出的估计算法也在运行时间和过滤能力有很好的效果。