一种面向高速网络的模式匹配算法的设计与实现  

A Faster Algorithm for Pattern Matching in High Speed NetWork

作　　者：赵远[1] 秦拯[1] 张大方[1] 武年华[2] 

机构地区：[1]湖南大学软件学院,410082 [2]清华大学软件学院,100084

出　　处：《微计算机信息》2010年第12期167-168,共2页Control & Automation

基　　金：国家自然科学基金项目;基金申请人:秦拯张大方;项目名称:"基于端系统的网络在线测量理论与方法研究"(No.60273070);广东省科技计划项目;基金申请人:秦拯;项目名称:基于P2P分流技术的高速网络入侵检测系统(No.0711020400157);广东省自然基金项目;基金申请人:秦拯;项目名称:面向高速网络入侵检测的基于P2P的分流技术(No.7007730)

摘　　要：本文在对Boyer-Moore(BM)算法及其改进的算法BoyerMoore-Horspool(BMH)算法进行分析的基础上,提出了一种更加快速的模式匹配算法-HPMA(High-Speed-Pattern-Matching-Algorithms,高速模式匹配算法)。该算法采用从模式两端向中间位置交替的匹配顺序,减少了模式的一部分后缀与文本匹配,而模式的前缀却不匹配情况下不必要的比较,同时考虑字符串后一位字母的唯一性,提高最大位移的出现概率。On the basis of BM algorithm and some important improvement algorithms,a new improved algorithm-HPMA is presented. The HPMA algorithm combines the merits of the BMH algorithms and the uniqueness of the next character is taken into considera-tion.The HPMA algorithms greatly enhances the probability of occurrence of the largest right shift,thus improving the matching speed effectively.

关 键 词：模式匹配 KMP算法 BM算法 RK算法 BMH算法 

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