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