王亚南，徐周波，古天龙

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林　541004)



基于OBDD的模式匹配算法硬件实现

王亚南，徐周波，古天龙

(桂林电子科技大学 广西可信软件重点实验室，广西 桂林541004)

针对模式匹配算法硬件实现过程中成本高的问题，提出一种基于OBDD的模式匹配算法。该算法通过OBDD刻画所有模式串，利用OBDD技术的S-删除规则与合并规则简化OBDD规模，并利用FPGA技术对OBDD结构进行硬件实现。实验结果表明，该算法硬件实现较为简单，不消耗CAM资源，并可通过OBDD简化规则减小电路规模。

OBDD；FPGA；模式匹配算法；CAM

模式匹配是数据结构中的一种基本运算，被广泛应用于入侵检测、信息检索等众多领域。根据单次匹配的模式串数量的不同分为单模式和多模式匹配。早期的模式匹配算法多为单模式匹配，如KMP算法[1]、BM算法等。因单模式匹配算法一次只有一个模式串参与匹配，匹配效率较低，虽然实现较为简单，但较低的匹配效率只适合模式集较少的匹配判定，限制了单模式匹配算法的应用[2]。相比单模式匹配算法，AC算法[3]、WM算法[4]等多模式匹配算法在匹配效率上有很大提高，但远不能满足实际需求对模式匹配算法性能的要求。

近年来，针对传统基于软件实现的模式匹配算法，研究人员开始尝试进行硬件实现。Park等[5]提出针对字符串匹配的高效并行硬件算法，利用数据流算法开发脉动阵列结构，并提出特殊用途超大规模集成电路设计方案。李伟男等[6]对传统AC算法与WM算法进行了改进，并通过硬件实例介绍了多模式匹配算法的硬件实现方法及策略，对今后多模式匹配算法的发展趋势进行了展望。……