多模式匹配算法及硬件实现

作者：李伟男; 鄂跃鹏; 葛敬国; 钱华林

来源：软件学报, 2006, (12): 2403-2415.

• 多模式匹配
• Aho-Corasick算法
• 有限状态自动机
• Wu-Manber算法
• FPGA(现场可编程门阵列)
• TCAM(三态内容寻址存储器)
• bloom filter multi-pattern matching
• Aho-Corasick algorithm
• finite state automata
• Wu-Manber algorithm
• FPGA (field programmable gate array)
• TCAM (ternary content addressable memory)
• bloom filter

介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.

• 出版日期2006
• 单位中国科学院大学; 中国科学院计算机网络信息中心