一种快速的单模式匹配算法  

A Fast Single-Pattern Match Algorithm

作　　者：杨子江[1] 聂瑞华[1,2] 

机构地区：[1]华南师范大学计算机学院,广东广州510631 [2]华南师范大学网络中心,广东广州510631

出　　处：《华南师范大学学报（自然科学版）》2013年第5期31-35,共5页Journal of South China Normal University(Natural Science Edition)

基　　金：国家科技支撑计划项目(2008BAH37B05084);广东省教育科研网优化升级与应用平台建设项目(粤财教2011-16)

摘　　要：在分析了BM算法以及一些重要的改进算法的基础上,提出一种新的改进算法——Y_BMHS算法.利用辅助的二维数组,考虑了文本串后间隔的两位字符和模式串首字符的唯一性,使得最大位移提升到m+3,出现概率也显著提高,加快了匹配速度.证明Y_BMHS算法比BM、BMH、BMHS等算法有更好的性能.After analyzing BM algorithm and some important improved algorithms, a new improved algorithm called Y_BMHS is put forward. With a two-dimensional array, the algorithm considers the uniqueness of text string＇s last two interval characters and pattern string＇s first character. The proposed algorithm makes the maximum displacement enhance to m ＋ 3, and the occurrence probability and match speed are also improved. The experimental results show that the Y_BMHS algorithm performs better than BM, BMH, BMHS and other improved algorithms as well.

关 键 词：BMHS算法 二维数组 出现概率 BMH算法 BM算法 

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