DHSWM:一种改进的WM多模式匹配算法

• 作者: 刘卫国 胡勇刚
• 来源期刊: 中南大学学报（自然科学版）
• 学科: 工学
• 关键词: 入侵检测 模式匹配 Wu-Manber算法 双哈希查找
• 年，卷（期）: 2011,（12）
• 所属期刊栏目: 机械工程·控制科学与工程
• 页码范围: 3765-3771
• 分类号: TP393
• 字数: 5667字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘卫国	中南大学信息科学与工程学院	95	1477	16.0	37.0
2	胡勇刚	中南大学信息科学与工程学院	2	19	2.0	2.0