支持局部过滤的近似字符串匹配系统

摘要

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

目录

声明

摘要

第1章引言

1．1研究背景

1．2本文的研究内容及面临的挑战

1．3本文的贡献

1．4本文的组织结构

第2章相关工作与背景知识

2．1过滤策略

2．2编辑距离

2．3本章小结

第3章系统设计与拟解决问题

3．1系统拟解决问题

3．2系统总体设计

3．3本章小结

第4章基于局部过滤的索引结构

4．1过滤策略

4．2局部距离的计算算法与实现

4．3索引结构

4．4索引构建算法与实现

4．5本章小结

第5章查询算法

5．1基本查询算法概述

5．2处理不确定阈值的查询算法

5．3处理不确定chunk长度的查询算法

5．4查询算法实现

5．5本章小结

第6章系统实现与实验

6．1系统总体实现

6．2实验设置

6．3查询性能对比分析

6．4过滤能力对比分析

6．5索引结构构建对比分析

6．6参数对查询时间影响

6．6．2qmax参数对查询时间影响

6．7本章小结

7．1总结

7．2工作展望

参考文献

致谢

攻硕期间参加的项目及发表的论文