小型微型计算机系统
小型微型計算機繫統
소형미형계산궤계통
MINI-MICRO SYSTEMS
2013年
7期
1650-1653
,共4页
多模式串匹配%机器字%短模式串%规则集
多模式串匹配%機器字%短模式串%規則集
다모식천필배%궤기자%단모식천%규칙집
multi-pattern matching%word length%short patterns%rule set
多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40％.当最短模式串长度为2和3时,搜索时间缩短了60％以上.
多模式匹配是串處理繫統中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能錶現最好的算法.針對Wu-Manber多模式匹配算法在規則集中存在短模式串時性能下降的問題,提齣一種按字長匹配的多模式匹配算法.改進的算法是在32位機器上實現,哈希的字符塊長度取2,每次匹配的單位由原來的一箇字符變為一箇機器字,縮小瞭訪存時間,同時利用機器字長存儲的特點閤理設計哈希函數,加快瞭字符塊哈希值的計算,極大的提高瞭有短模式串存在時模式集的匹配性能.與原Wu-Manber算法對比,噹最短模式串長度小于6時,改進後的算法搜索時間平均縮短瞭40％.噹最短模式串長度為2和3時,搜索時間縮短瞭60％以上.
다모식필배시천처리계통중최중요적조작지일,이Wu-Manber산법시다모식천필배산법중평균성능표현최호적산법.침대Wu-Manber다모식필배산법재규칙집중존재단모식천시성능하강적문제,제출일충안자장필배적다모식필배산법.개진적산법시재32위궤기상실현,합희적자부괴장도취2,매차필배적단위유원래적일개자부변위일개궤기자,축소료방존시간,동시이용궤기자장존저적특점합리설계합희함수,가쾌료자부괴합희치적계산,겁대적제고료유단모식천존재시모식집적필배성능.여원Wu-Manber산법대비,당최단모식천장도소우6시,개진후적산법수색시간평균축단료40％.당최단모식천장도위2화3시,수색시간축단료60％이상.
