模式匹配,是指给定一个或者多个具有某种特定属性的模式,搜索这些模式在一段符号序列中的出现位置。模式匹配是计算机科学的基础性问题,它被广泛研究,又广泛地运用于信息检索、入侵检测、IP路由、数据挖掘、文本压缩、光学字符识别、语义分析等众多涉及符号与字符处理的领域。近些年来,互联网传输量爆发式增长,网络安全形势日益严峻,DNA序列比对技术快速发展,都迫切需要更高性能的模式匹配算法。本文首先介绍了经典的单模式匹配算法和Aho-Corasick算法、AC-BM算法与Wu-Manber算法这三种使用最为广泛的多模式匹配算法,分析了这些算法的优缺点。然后通过实验测试,比较了这些算法的时间与空间性能,分析了模式串长度与数量等因素对性能的影响。Aho-Corasick算法是一种经典的多模式匹配算法,有着良好的匹配速度,在众多的场景得到了广泛的应用。该算法的缺陷是随着模式串集合规模的变大,Aho-Corasick自动机的空间也急剧增大。Aho-Corasick算法空间开销大、存储效率低的问题促使前人做了大量的改进工作,主要的改进工作都着力于研究更为高效的存储结构来保存Aho-Corasick自动机的转移信息。经典的高效存储格式包括Banded-Row格式向量、Sparse-Bands格式向量和位图。为了降低Aho-Corasick算法的空间需求,在深入分析研究前人的改进工作后,本文提出了一种基于分类存储的改进算法——CAC算法。CAC算法不局限于单一的方式存储状态节点,可以灵活选择转移表、Banded-Row格式向量、Sparse-Bands格式向量、位图等方式存储状态结点。在预处理阶段,计算每一个状态的转移信息、失效信息与输出信息,将这些信息与预定义的规则进行比对,为每一个状态结点选择最合适的存储格式,尽可能少地使用空间。在搜索阶段,根据状态结点的标识符识别状态节点的存储类型,用恰当的方式读取转移信息、失效信息与输出信息,以完成搜索。实验表明,CAC算法与经典Aho-Corasick算法、位图Aho-Corasick算法相比,以搜索阶段较小的时间性能为代价,极大幅度地压缩了自动机的存储空间,适用于空间资源昂贵、模式串集合规模较大的场景。