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

基金项目:

国家科技支撑计划：新一代可信任互联网实验网;国家科技支撑计划

详细信息

A FAST SINGLE-PATTERN MATCHING ALGORITHM

摘要: 在分析了BM算法以及一些重要的改进算法的基础上，提出一种新的改进算法—Y_BMHS 算法.该算法利用辅助的二维数组，考虑了文本串后间隔的两位字符和模式串首字符的唯一性，使得最大位移提升到m+3，出现概率也显著提高，加快了匹配速度.实验证明Y_BMHS算法比BM、 BMH、BMHS等算法有更好的性能.
- BM算法
Abstract: After analyzing BM algorithm and some important improved algorithms, a new improved algorithm called Y_BMHS is put forward in this paper. 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.
- BM algorithm