支持带有通配符的字符串匹配算法

论文摘要

带有通配符的字符串匹配问题已成为诸多领域的研究热点,例如生物信息学、数据库系统中的SQL查询、搜索引擎的文本索引、文件名查找、网络入侵检测等领域。然而,带有通配符的查询模式在更好的满足用户查询需求的同时,也使得查询处理过程变得更加复杂,如何高效地支持带有通配符的字符串匹配问题面临着很大的挑战。目前,关于通配符的匹配问题大多都是针对在线数据搜索,基于索引的离线查询方法较少,并且这些算法中索引占用的存储空间较大,对于通配符的定义也有所限制,不具有普遍性。本文主要研究查询模式串中含有可代表任意长度字符串的通配符“*”以及可代表任意一个字符的通配符“?”时的字符串匹配问题,包括精确字符串匹配问题以及近似字符串匹配问题。由于gram索引结构在空间大小以及查询效率上的优势,本文首次将gram索引结构用于带通配符的字符串匹配问题。首先,本文对现有的支持带有通配符的字符串匹配技术进行了概述。通过对现存算法的对比分析,本文提出了基于gram索引结构的支持通配符的精确字符串匹配算法。通过将带有通配符的查询模式串分解为若干不含通配符的查询片段,成功的将带有通配符的复杂查询问题转化为不含通配符的精确子串查询问题,并且在片段查询的过程中运用了长度过滤、位置过滤以及计数过滤等过滤方法,提高了查询速度。然后,本文对精确匹配算法进行了扩展,使其能够适用于近似匹配问题。在查询片段中利用近似匹配常用的鸽巢原理过滤法,可以排除部分不是查询结果的字符串。但是此方法只适用于编辑距离阈值k较小的情况,并且在带有通配符的查询问题中过滤效果不是很理想。因此,本文提出了另一种基于gram索引结构的支持通配符的近似字符串匹配算法,通过计算与查询模式串相匹配的字符串的公共gram数的下限值进行过滤,排除了大量不可能是查询结果的字符串,提高了查询速度。最后,基于真实数据集上的大量实验结果与分析显示了本文提出的基于q-gram索引结构的带通配符字符串匹配算法在减少空间开销的同时具有良好的过滤能力和查询效率。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 研究背景
• 1.2 本文的研究内容及面临的挑战
• 1.3 本文的贡献
• 1.4 本文的组织结构
• 第2章 相关工作
• 2.1 支持带有通配符的精确查询算法
• 2.1.1 在线精确查询算法
• 2.1.2 离线精确查询算法
• 2.2 支持带有通配符的近似查询算法
• 2.3 本章小结
• 第3章 背景知识与问题定义
• 3.1 编辑距离
• 3.2 Q-GRAM倒排索引结构
• 3.3 问题定义
• 3.4 本章小结
• 第4章 基于GRAM索引的精确通配符匹配算法
• 4.1 支持带有通配符的精确字符串匹配算法框架
• 4.1.1 索引的选择及q-gram索引存储方式
• 4.1.2 精确通配符匹配算法原理
• 4.1.3 精确通配符匹配算法基本框架
• 4.2 基于过滤策略的片段查询技术
• 4.2.1 过滤策略的优势
• 4.2.2 过滤特征的选择
• 4.2.3 基于过滤策略的片段查询算法
• 4.3 合并片段查询的优化算法
• 4.4 验证过程算法及优化技术
• 4.5 Q值对片段查询的影响
• 4.6 本章小结
• 第5章 基于GRAM索引的近似通配符匹配算法
• 5.1 利用片段查询过滤的近似匹配算法
• 5.1.1 片段过滤原理
• 5.1.2 基于片段查询的近似匹配算法
• 5.2 利用GRAM过滤的近似匹配算法
• 5.2.1 Gram过滤原理
• 5.2.2 基于gram过滤法的近似匹配算法
• 5.2.3 Q值对近似查询的影响
• 5.3 本章小结
• 第6章 实验与分析
• 6.1 实验设置
• 6.2 带通配符精确字符串匹配算法实验与分析
• 6.2.1 后缀树和q-gram索引的性能比较
• 6.2.2 字符串长度的影响
• 6.2.3 Gram长度q的影响
• 6.2.4 查询串中通配符比例的影响
• 6.3 带通配符近似字符串匹配算法实验与分析
• 6.3.1 基于q-gram索引的查询算法与在线查询算法性能比较
• 6.3.2 Gram长度q的影响
• 6.3.3 编辑距离阈值k的影响
• 6.4 本章小结
• 第7章 结束语
• 参考文献
• 致谢
• 攻硕期间参加的项目及发表的论文