串匹配是计算机研究领域的一个经典问题,是众多网络安全系统中的关键技术之一。随着互联网的普及和发展,海量信息的处理和新的应用需求对串匹配技术提出了新的挑战。 本文主要对大规模精确串匹配技术和动态串匹配技术进行研究。在大规模精确串匹配方面,本文分别从压缩存储空间和改善数据结构局部性这两方面出发,提出了基于存储压缩的串匹配算法和对串匹配自动机进行内存布局优化的策略。在动态串匹配方面,本文对经典的串匹配算法进行了扩展,提供动态增删关键词的能力。 具体来说,本文取得的主要成果如下: 1.串匹配算法性能分析:通过实验和理论分析,本文得出串匹配算法的执行时间和二级cache miss之间的线性关系,并对经典算法的时间复杂度进行了分析,提出了从压缩存储空间和改善数据结构局部性这两方面来优化串匹配算法的途径。 2.基于存储压缩的串匹配算法:从压缩存储空间以改善cache命中率的思想出发,本文提出了一种对经典SBOM算法进行空间压缩的策略,并从理论上证明了该方法具有线性的空间复杂度。这种改进策略有效地压缩了自动机的存储空间,大幅度地提高了算法的匹配速度。 3.串匹配算法的内存布局优化:从改善数据结构局部性的思想出发,本文对内存布局优化问题进行了形式化和建模,并提出了利用线性规划方法进行求解的策略。该方法在理论和实际中都具有一定的指导意义。 4.经典算法在动态匹配上的扩展:本文对经典的串匹配算法进行了扩展,动态地维护和更新已经建立的数据结构,提供增加和删除关键词的操作,并保证近似线性的时间复杂度。 5.通用串匹配算法库:基于前人的研究成果和本文的部分工作,本文构建了一个通用串匹配算法库。该算法库具有多线程安全和通用的特点,可以为不同的项目提供二次开发扶持。