作为计算机研究领域的核心技术之一,模式匹配算法被广泛应用于网络安全,搜索引擎以及生物计算等领域,特别是针对网络安全问题,模式匹配算法的性能更是直接影响了网络安全系统的整体性能。随着计算机网络技术的飞速发展,互联网产生的数据量也呈爆炸式增长,从而导致了模式匹配算法的研究面临着诸多新的挑战,其中主要表现为随着模式集的规模迅速增大,模式匹配算法的性能成为系统的瓶颈所在。因此绝大多数经典的模式匹配算法无法直接有效的运用到大规模模式集环境下,所以研究适用于大规模模式集环境下具有高匹配性能的模式匹配算法是当务之急,具有重要的学术研究意义和广阔的应用前景。论文的主要工作如下:1.提出了一种高匹配性能的较大规模多模式匹配算法,简称为ELSM算法。论文首先分析了一种适用于较大规模模式集而且空间复杂度低的多模式匹配算法:MASM算法,以及MASM算法在预处理阶段用于模式串压缩的Leaf-Attaching算法。虽然MASM算法空间复杂度低,但是算法的时间复杂度高,而且算法的时间复杂度和模式集的数量成正比。本论文提出的ELSM算法在保持MASM算法低空间复杂度性质下又有着较低时间复杂度。ELSM算法在预处理阶段使用改进的Leaf-Attaching算法,保证了算法在压缩大规模模式集的时候不会出现内存不足的情况。ELSM算法在模式匹配阶段对MASM算法提出了如下三种改进策略:(1)使用数组的形式来实现完全二叉搜索树,减少了算法的内存占有量并且加快了访问树节点的速度。(2)采用AC算法作为初步匹配算法,过滤掉文本串中大量不会发生模式匹配的位置,减少了算法的匹配时间。(3)使用哈希表将完全二叉搜索树分组,该策略减少了算法需要遍历的完全二叉搜索树的高度,从而减少了算法的匹配时间。最后通过实验验证ELSM算法在保留了MASM算法具有较低空间复杂度优点的基础上,有着更高的匹配性能。2.提出了一种带失效跳转机制的多模式匹配算法,简称为SBT算法。SBT算法主要基于Burst Tries数据结构实现,论文首先详细分析Burst Tries的数据结构,以及Burst Tries的字符串查找以及字符串插入过程。然后提出将Burst Tries数据结构应用于多模式匹配领域的方法,并针对在应用过程中会出现的空间复杂度过高和匹配效率低下的缺点提出了两种改进策略即空间压缩与失效跳转策略,其具体内容为:(1)SBT算法通过空间压缩策略降低了Burst Tries中节点的内存占用量,从而降低了算法的空间复杂度。(2)SBT算法的失效跳转策略充分利用了模式匹配过程中已经匹配的字符串信息,保证算法能跳过文本串中大量不会发生匹配的位置,从而提高了算法的匹配效率。最后通过设计一系列实验验证了SBT算法在匹配性能上的优越性。