作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2006, Vol. 32 ›› Issue (23): 78-81. doi: 10.3969/j.issn.1000-3428.2006.23.028

• 软件技术与数据库 • 上一篇    下一篇

对BM模式匹配算法的一个改进

渠 瑜,王亚弟,韩继红,赵 宇   

  1. (解放军信息工程大学电子技术学院,郑州 450004)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2006-12-05 发布日期:2006-12-05

Improvement of BM Algorithm for Pattern-matching

QU Yu, WANG Yadi, HAN Jihong, ZHAO Yu   

  1. (Institute of Electronic Technology, PLA Information Engineering University, Zhengzhou 450004)
  • Received:1900-01-01 Revised:1900-01-01 Online:2006-12-05 Published:2006-12-05

摘要: 在分析BM算法的基础上,提出了一个改进的模式匹配算法QBM算法。该算法采用最长前缀的思想,在匹配后缀的时候采用一个位置移动表shift表代替BM算法中的两个移动表,提高了算法的运行效率。从理论和实践两个方面证明了该算法要优于BM算法。

关键词: 模式匹配, 最长前缀, 移动表

Abstract: Based on the analysis of BM algorithm, this article represents a new pattern-matching algorithm, namely QBM algorithm. This algorithm uses the concept of max-length prefix, and applies only one shift table to calculate the movement distance of pattern strand. The article proves that QBM algorithm is superior to BM algorithm from the aspects of theory and practice.

Key words: Pattern-matching, Max-length prefix, Shift table