随着计算机技术的发展,互联网已经成为人们生活中不可或缺的重要组成部分。搜索引擎、信息查询和社交网络在人们生活扮演着越来越重要的角色。字符串匹配在这些领域中被广泛地应用。因此,对于字符串匹配算法的研究具有一定的理论研究意义和重要的实际应用价值。近年来,随着近似字符串匹配技术的广泛应用,越来越多的学者参与到近似字符串匹配问题的研究中。近似字符串的匹配问题,不同于精确字符串匹配,允许在匹配中存在一定的误差,其匹配结果集更大,算法的空间复杂度和时间复杂度更高。目前主要的解决方法是利用字符串间的局部相同,然而该方法在查询串与数据串间的差异较大时会变尤为低效。本文基于查询串和数据串间的差异,提出一种算法来实现近似字符串的过滤查询。本文提出了 一个称为局部距离的概念用来量化一个查询串中的子串与数据串间的差异。查询串子串的局部距离和是查询串和数据串间编辑距离的下界,使用这个下界进行过滤。本文设计了一系列索引结构来支持局部过滤,索引中存储了所有可能的查询串子串相对于所有数据串的局部距离值。通过仔细的观察和分析字符串局部距离之间数学关系,本文设计出了不会影响过滤效果但体积很小的索引结构。接着提出了带有位置约束的局部距离的概念。又设计出高效的位并行查询算法。为了处理不确定的查询阈值和不确定的chunk长度,改进了查询算法。实验结果显示局部过滤算法与现有的其它算法相比较,过滤效果、查询时间、索引体积大小方面都有很大优势。