面向比特流的分组快速搜索匹配算法  

Grouping Quick Search Matching Algorithm for Bit Steam

作　　者：陶曌 杨建波[1] 张波[1] 张丽云[1] 

机构地区：[1]空军航空大学信息对抗系,长春130022

出　　处：《计算机工程》2017年第6期125-128,135,共5页Computer Engineering

摘　　要：在比特流的模式匹配中,由于目标串和模式串字符集简单,匹配过程中匹配窗口平均跳跃长度短,导致快速搜索(QS)匹配算法效率不高。为此,分析QS算法坏字符启发规则匹配效率与字符集大小的关系,借鉴编码QS算法的编码思想,提出一种对模式串进行分组预处理并使用字符组计算跳跃集的分组QS算法,给出坏字符组启发规则与最佳分组长度的计算方法。实验结果表明,与不分组的算法相比,该算法能够增加比特流模式串匹配中匹配窗口的平均跳跃长度,提高计算效率。In the pattern matching of bit stream,because the character sets of target string and pattern string are simple, the average jumping length of matching window is short during the matching process, making Quick Search （QS） matching not efficient. So this paper analyses the relationship between the matching efficiency of bad character heuristic rules and the character set size of QS algorithm. On the reference of coding QS algorithm,it proposes a grouping QS algorithm for group preprocessing of pattern strings and using the character set to calculate the jump set, and presents a method to calculate the bad character group heuristic rule and the optimal group length. Experimental results show that compared with the non-grouping algorithm, the proposed algorithm can improve the average hop length of the matching window during the matching of bit stream pattern strings, and the computational efficiency is better.

关 键 词：入侵检测 模式串匹配 比特流 快速搜索算法 编码思想 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]