随着计算机技术在各个领域的广泛应用,信息量也在呈指数增长,庞大的数据量对查询请求处理也带来了新的挑战。另一方面,用户对查询也有了更高的要求,简单的查询处理已经不能满足用户的需求,复杂模式匹配的重要性日益显著。复杂模式匹配包括正则表达式匹配、近似匹配、模糊匹配等,其中正则表达式匹配与近似匹配在许多领域都有着广泛的应用。例如,在生物信息学方面,正则表达式用来描述具有相同结构的基因序列或者蛋白序列集合,然后利用正则表达式在基因序列库中匹配相应的结果;为了拼接通过测序抽取得到的较短的基因序列,需要通过近似子序列匹配的方法将基因序列与参考序列进行比对。在知识图谱领域,正则表达式用于描述一组实体的公共特征,并用于从大量的文本数据中抽取出匹配的信息。此外,近似子序列匹配还被广泛地应用于数据集成与数据清洗。研究高效的复杂模式匹配方法具有重要的理论价值和实际意义。本文主要研究了正则表达式匹配与近似子序列匹配这两类复杂模式匹配问题,提出了多种基于索引结构的高效复杂模式匹配方法与优化技术。具体来说,本文的主要研究内容和创新成果包括以下几个方面:（1）针对现有利用过滤技术的正则表达式匹配方法过滤能力不高的问题,提出了反向因子的过滤技术。通过分析反向因子与正向因子的相互作用关系,设计了利用反向因子与正向因子的过滤算法。为了利用位并行技术来提升过滤算法的效率,提出了基于位向量的索引结构BITINDEX,并设计了相应的位并行算法。本文分析了不同反向因子对于过滤能力与查询效率的影响。为了求取一组高质量的反向因子,提出了核心反向因子的概念,并设计了多种高效的算法来求取正则表达式查询的核心反向因子。本文还分析了不同的匹配方法对于验证阶段性能的影响,提出了优化技术来自适应的选择正则表达式的匹配方向。（2）针对基于过滤技术的正则表达式匹配方法对于复杂查询匹配效率不高的问题,提出了利用q-gram技术的正则表达式匹配方法。该方法可以通过q-gram倒排索引直接找到所有的匹配结果,从而避免了在原数据文件上的扫描验证。因此,该方法另一个优势在于可以直接被集成到现有的基于q-gram倒排索引的应用中,而不需要对数据集建立新的索引。本文提出了一种q-gram驱动的非确定有限状态自动机（GNFA）来表示一个正则表达式的语义,并且分析了一个正则表达式匹配结果在GNFA上所需满足的q-grams的匹配位置约束。设计了基于GNFA的匹配算法,与传统的使用自动机进行验证的方法不同,该算法通过GNFA查找倒排索引中满足位置约束的q-grams位置来找到所有正则表达式匹配结果。通过考虑q-grams在本文上的选择度的差异,进一步地提出了利用查询计划树的匹配算法,通过优化位置约束的检查顺序来提高算法的匹配性能。（3）分析了现有支持近似子序列匹配的方法特点,针对现有方法的过滤技术会产生出过多的候选位置与生成大量冗余的签名子序列的问题,提出了一种利用混合签名的过滤技术。该技术可以使得签名包含不同数目的子序列,从而避免生成大量的冗余签名。进一步地深入分析了利用混合签名产生候选位置的代价,设计了一个代价-收益模型来生成高质量的混合签名,从而均衡产生候选位置的代价与验证它们的代价。此外,还提出了一种自适应的算法来利用混合签名产生候选位置,并给出了进一步的优化技术来提高产生候选位置的效率。综上,本文针对正则表达式匹配与近似子序列匹配这两种复杂模式匹配问题,提出了新的过滤技术来提高匹配效率,并设计了高效的基于索引结构的匹配方法与优化技术。通过在多组真实数据集上进行的实验验证,本文提出的方法比目前最先进的方法具有更高的匹配效率。