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

摘要

大规模高速URL匹配是许多网络安全系统中的关键技术,经典串匹配算法在大规模URL情况下有许多限制。针对URL数据的特点在经典多模式串匹配算法Wu-Manber基础上提出XWM-Tree算法和XWM-Hash算法。算法应用了模式串窗口选择,两阶段哈希和关联容器组织冲突链表等多种优化手段,大幅度提高了算法的匹配性能。在大规模真实数据集上的测试结果表明本文提出的算法匹配速度可以提高一倍以上,尤其是当最短模式串较长的时候更有优势。