韦安垒 李开科 张榆

摘 要：基于已有的单模式匹配算法，论文设计了一种改进的快速单模式匹配算法，实现了一个基于DPI技术的下一代防火墙系统，并将改进后的算法应用于该系统。测试发现，新设计的下一代防火墙的性能和功能都得到了优化。

关键词：模式匹配算法；DPI技术；下一代防火墙

中图分类号：TN915.08 文献标识码：C

Design and implementation of a fast single pattern matching algorithm

Abstract： Based on the existing single pattern matching algorithm， a next generation firewall system based on DPI technology is designed and implemented. And the improved algorithm is applied to this system. Tests have found that the performance and functionality of the next generation firewall are optimized.

Key words： pattern matching algorithm； DPI technology； next generation firewall

1 引言

针对KMP算法可保证字符适配后，模式串不回溯，但由于跳转距离较小，算法平均性能较BM算法要低；BMH2C算法具有较大的跳转距离，具有较好的平均性能，但由于不能保证字符适配后模式不回溯，在最坏和较坏的情况下，具有较差的性能，其复杂度为O（mn）。结合二者优点，本文提出一种改进的快速单模式匹配算法——BMH2CKMP算法。通过将该算法应用于下一代防火墙，从而测试该算法的是否有效。

2 BMH2CKMP算法

BMH2CKMP算法结合了KMP算法和BMH2C算法二者的优势，弥补各算法的不足，从而解决既能大幅跳转又无需回溯的问题。

2.1 算法设计思想

KMP算法复杂度为O（n），可保证字符适配后，模式串不回溯，则在最坏情况（模式串位于文本串的末尾处）下，具有较高的性能。但由于跳转距离较小，算法平均性能较BM算法要低。BM算法及其改进算法具有较大的跳转距離，具有较好的平均性能，但由于不能保证字符适配后模式不回溯，在最坏和较坏的情况下，具有较差的性能，其复杂度为O（mn）。本文结合KMP于BMH2C算法各自的优势提出一种新的单模式匹配算法BMH2CKMP算法。BMH2CKMP算法的设计思想是：

第一步：以BMH2C算法为基础，将其修改为正向匹配；……