一种按字长匹配的Wu-Manber多模式匹配算法

作者：汪永进; 顾乃杰; 任开新

来源：小型微型计算机系统, 2013, (07): 1650-1653.

• 多模式串匹配
• 机器字
• 短模式串
• 规则集 multi-pattern matching
• word length
• short patterns
• rule set

多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40%.当最短模式串长度为2和3时,搜索时间缩短了60%以...

• 单位
  中国科学技术大学; 中国科学院