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

• 作者: 任开新 汪永进 顾乃杰
• 来源期刊: 小型微型计算机系统
• 学科: 工学
• 关键词: 多模式串匹配 机器字 短模式串 规则集
• 年，卷（期）: 2013,（7）
• 所属期刊栏目: 信息安全与算法研究
• 页码范围: 1650-1653
• 页数: 4页
• 分类号: TP18
• 字数: 4950字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	顾乃杰	中国科学技术大学计算机学院	83	347	9.0	12.0
10	汪永进	中国科学技术大学计算机学院	2	81	2.0	2.0