郭三川

文章编号： 2095-2163（2018）03-0037-04中图分类号： 文献标志码： A

（国家计算机网络应急技术处理协调中心， 北京 100029）

摘要： 关键词： （CNCERT/CC， Beijing 100029， China）

Abstract： Precise string matching has been studied for many years. In recent years， the performance of mass pattern matching has drawn the attention of scholars. In this paper， a massive parallel pattern matching method based on fingerprint model is proposed. First， the pattern set is divided into subsets according to the length. Secondly， these subsets are merged using dynamic programming algorithm. Finally， the conflict rates of subsets are adjusted， and subsets are scheduled to many-core processors by greedy algorithm. Experiments show that compared with the existing mass pattern matching method and pattern set dividing method， the performance of the proposed method is better.

Key words：

基金项目：

作者简介：

收稿日期： 引言

精确字符串匹配，即给定一个模式集合P={P1，P2，…，Pn}， 其中，Pn为有限字母表∑上的字符串Pn={Pn1，Pn2，…，Pnl}，从输入文本T中，找出模式集合中的模式在文本中出现的所有位置。近年来，随着计算机和互联网的发展，越来越多的场合需要应用到精确字符串匹配，而随着数据量的增加，海量模式精确匹配的技术研究备受关注。基于这样的背景，本文的研究目标是对现有的海量模式精确匹配算法进行优化，提升匹配速度。

1相关工作

精确字符串匹配方法目前已进入应用广泛，发展也比较成熟的时期。最著名的算法是AC和WM算法。AC算法效率高，但是消耗内存大，适合短字符串的匹配；WM算法采用不良字符块的跳转机制加速匹配，基于哈希函数选择匹配阶段可能匹配的模式串，WM算法在长字符串匹配上表现出更好的性能，但是在海量模式集下，哈希的冲突率很大，导致匹配效率低下。AC与WM的比较结果可见表1。

针对WM的深入研究中，文献 1] 提出了一种基于共享位置的并行WM算法，对于同一内存内容，在多核处理器上，操作多个扫描窗口进行并行匹配。文献 2] 利用OpenCL架构在GPU上实现了WM算法的并行化，提高了匹配速度。随着多核性能的提升，WM算法的匹配效率也相应得到提高，但是上述方法并未能有效地解决海量模式的匹配效率低下问题，如入侵檢测系统中，背景流量较大时，海量模式的低效匹配会导致严重的丢包率，漏包严重。……