DHSWM：改进的WM 多模式匹配算法

摘要：

针对WM 算法的查找效率随着模式集规模的增大而降低的问题，提出一种改进算法。在预处理阶段，改变原有Hash 表中的链表结构，采用双哈希法将模式串存放在Hash1 表中指定的区间，Hash 表中存放该存储区间的起始位置与区间大小；Prefix 表用于判断模式集中是否存在与当前匹配窗口中文本前缀相同的模式；当Shift 表中出现移动值为0 时，根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离值并存于Shift1 表中。在查找阶段，采用双哈希法在Hash1 表的某一区间中查找模式串，避免了在大规模模式集情况下查找过长的模式链表，扩大了匹配操作后匹配窗口滑动的距离，减少了冗余的匹配操作，缩短了查找时间。实验表明，在模式集规模较大时，改进后的算法能显著地提高匹配速度，当模式串数目超过5000 条时，改进算法的查找时间要比WM算法缩短40％~47％。

关键词： intrusion detection pattern matching Wu-Manber algorithm double hash searching

作者: 胡勇刚 刘卫国

会议类型: 国内会议

会议名称: 湖南省第三届研究生创新论坛——信息与控制工程的新理论和新技术分论坛

会议地点: 长沙

会议语种:中文

页码: 449-450

在线出版日期: 2010-11-01（万方平台首次上网日期，不代表论文的发表时间）