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

【Abstract】 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%.更多还原