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

A Word-length Based Wu-manber Multi-pattern Matching Algorithm

作　　者：汪永进[1,2,3] 顾乃杰[1,2,3] 任开新[1,2,3] 

机构地区：[1]中国科学技术大学计算机学院,合肥230027 [2]安徽省计算与通信软件重点实验室,合肥230027 [3]中国科学技术大学中科院沈阳计算所网络与通信联合实验室,合肥230027

出　　处：《小型微型计算机系统》2013年第7期1650-1653,共4页Journal of Chinese Computer Systems

基　　金：国家重大专项(2009ZX01028-002-003-005)资助;国家自然科学基金项目(60833004)资助

摘　　要：多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40%.当最短模式串长度为2和3时,搜索时间缩短了60%以上.Multi-pattern matching is one of the most important operation in the string processing system,while Wu-Manber algorithm performs best on average.To tackle the problem of performance reduction w hen Wu-Manber algorithm deal w ith short patterns,this paper presents a multi-pattern matching algorithm matched by w ord length.Enhanced algorithm runs on 32-bit machine.By changing match unit from one character to one w ord size,the access time is reduced.Taking advantage of the characters of machine w ord storage,w e speed up the calculation of a block hash,and greatly improve matching performance w ith the existence of short patterns.When the shortest string length is less than 6,the improved algorithm＇s search time is reduced by 40% compared to the original Wu-Manber algorithm.When the shortest string length is equal to 2 or 3,the search time is reduced by more than 60%.

关 键 词：多模式串匹配 机器字 短模式串 规则集 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]