一种面向大规模特征集的高效特征匹配算法

A fast string matching algorithm for large-scale pattern sets

针对传统特征匹配(网络和信息安全系统的核心技术)算法的性能随着特征集规模的不断增大而不断下降的问题,提出了一种面向大规模特征集的高效特征匹配算法ALPM。该算法基于传统算法WM的跳跃思想,并结合硬件体系结构的特点,对预处理过程和匹配过程分别采用了不同的优化策略,如采用不同的哈希函数索引Shift表和Hash表,在预处理过程中动态截取特征标志,在匹配过程中结合Cache大小和特征集规模调整哈希函数冲突概率等,以提高匹配的性能。实验结果表明,针对大规模特征集,ALPM算法匹配性能比经典算法提高5～10倍。

In view of the problem that the performance of the classical pattern matching （one of the key technologies for network and information security systems） algorithms degrades seriously when the patterns become large, especially over 50000, this paper proposes a new architectural large-scale pattern matching algorithm （ALPM） for large-scale pattern sets. Based on the shift concept of the classical Wu-Manber （WM） algorithm and combined with its features of hardware architecture, the ALPM adopts several pre-processing and matching strategies, such as utilizing two different Hash functions to access the Shift and hash tables, optimizing pre-processing to choose the best entry signs from patterns for the two tables and ad- justing the Hash confliction dynamically with the Cache size and the pattern quantity, to improve the matching performance. The experimental results show that for the large-scale pattern set, the matching performance of the ALPM is 5 - 10 times higher than that of the classical WM.