西安电子科技大学学报（自然科学版）
西安電子科技大學學報（自然科學版）
서안전자과기대학학보（자연과학판）
JOURNAL OF XIDIAN UNIVERSITY(NATURAL SCIENCE)
2014年
6期
174-180
,共7页
模式匹配%字符串匹配%WM算法%SWM算法%域名过滤
模式匹配%字符串匹配%WM算法%SWM算法%域名過濾
모식필배%자부천필배%WM산법%SWM산법%역명과려
pattern matching%string matching%Wu-Manber algorithm%subest Wu-Manber algorithm%domain name filtering
针对 WM算法在模式集规模大且最短模式长度小的情况下性能较低的问题,分析了 WM算法及其改进的快速 WM(QWM)算法的优缺点,在此基础上提出了模式分集思想,并优化了跳跃和确认机制,设计了子集 WM(SWM)算法；然后针对该算法在域名过滤中的应用,对 hash 函数、匹配顺序等进行进一步优化.针对域名过滤的实验结果表明,当模式数量超过10000条时,SWM算法匹配时间是 WM算法的8.9%~11.6%,说明 SWM算法在模式集规模较大时,匹配速度能显著提高.
針對 WM算法在模式集規模大且最短模式長度小的情況下性能較低的問題,分析瞭 WM算法及其改進的快速 WM(QWM)算法的優缺點,在此基礎上提齣瞭模式分集思想,併優化瞭跳躍和確認機製,設計瞭子集 WM(SWM)算法；然後針對該算法在域名過濾中的應用,對 hash 函數、匹配順序等進行進一步優化.針對域名過濾的實驗結果錶明,噹模式數量超過10000條時,SWM算法匹配時間是 WM算法的8.9%~11.6%,說明 SWM算法在模式集規模較大時,匹配速度能顯著提高.
침대 WM산법재모식집규모대차최단모식장도소적정황하성능교저적문제,분석료 WM산법급기개진적쾌속 WM(QWM)산법적우결점,재차기출상제출료모식분집사상,병우화료도약화학인궤제,설계료자집 WM(SWM)산법；연후침대해산법재역명과려중적응용,대 hash 함수、필배순서등진행진일보우화.침대역명과려적실험결과표명,당모식수량초과10000조시,SWM산법필배시간시 WM산법적8.9%~11.6%,설명 SWM산법재모식집규모교대시,필배속도능현저제고.
To resolve the problem that when the number of rules is large and the length of the shortest rule is short,the performance of the WM algorithm will become less efficient,the paper analyzes the WM algorithm and an improved algorithm named the QWM algorithm,then proposes a new algorithm—the SWM algorithm.The new algorithm uses the idea of the sub pattern set and optimizes the shifting and affirming method.To use the SWM algorithm in domain name filtering,a new hash function and a new matching order are designed specially. The results in domain name filtering indicate that the SWM algorithm’s matching time is about 8.9%~1 1.6%that of the WM algorithm when the number of patterns is more than 10 000.The SWM algorithm can improve the speed of matching when the scale of the pattern is large.
