基于Wu-Manber算法的大规模URL模式串匹配算法  

Large-scale URL matching algorithm based on Wu-Manber algorithm

作　　者：贾博威 吴志刚[1] 张树壮[1] 

机构地区：[1]北京邮电大学网络技术研究院

出　　处：《智能计算机与应用》2017年第5期4-9,共6页Intelligent Computer and Applications

基　　金：国家重点研发计划资助项目(2016YFB0801200)

摘　　要：大规模高速URL匹配是许多网络安全系统中的关键技术,经典串匹配算法在大规模URL情况下有许多限制。针对URL数据的特点在经典多模式串匹配算法Wu-Manber基础上提出XWM-Tree算法和XWM-Hash算法。算法应用了模式串窗口选择,两阶段哈希和关联容器组织冲突链表等多种优化手段,大幅度提高了算法的匹配性能。在大规模真实数据集上的测试结果表明本文提出的算法匹配速度可以提高一倍以上,尤其是当最短模式串较长的时候更有优势。Large-scale high-speed URL matching is a key technology in many network security systems. The classical pattern string matching algorithm has many limitations in large-scale URLs. In this paper,based on the Wu-Manber algorithm,the XWM-Tree and XWM-Hash are proposed for URL matching. The algorithm proposed in this paper applies a variety of optimization methods to speed up matching performance,such as optimal window selection,two-phase hash and associative data structure. The test on the real data set shows that the algorithms proposed in this paper has better matching performance than other algorithms,especially when the shortest pattern string is longer and the matching speed is about twice than other algorithms.

关 键 词：多模式串匹配 URL匹配 WU-MANBER算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]