计算机应用 ›› 2013, Vol. 33 ›› Issue (08): 2379-2382.

• 典型应用 • 上一篇    下一篇

BM算法中函数shift的研究

韩光辉1,曾诚2,3   

  1. 1. 武汉商业服务学院 信息工程系,武汉 430056;
    2. 软件工程国家重点实验室(武汉大学),武汉 430072
    3. 湖北大学 数学与计算机科学学院,武汉 430062;
  • 收稿日期:2013-02-24 修回日期:2013-04-08 出版日期:2013-08-01 发布日期:2013-09-11
  • 通讯作者: 韩光辉
  • 作者简介:韩光辉(1956-),男,湖北武汉人,副教授,硕士,主要研究方向:计算理论、软件形式化;
    曾诚(1976-),男,湖北武汉人,副教授,博士,主要研究方向:网络化软件工程。
  • 基金资助:
    国家自然科学基金资助项目;国家自然科学基金资助项目

Research on function shift in Boyer-Moore algorithm

HAN Guanghui1,ZENG Cheng2,3   

  1. 1. Information Engineering Department, Wuhan Commercial Service College, Wuhan Hubei 430056, China
    2. State Key Laboratory of Software Engineering (Wuhan University), Wuhan Hubei 430072, China
    3. College of Mathematics and Computer Science, Hubei University, Wuhan Hubei 430062, China
  • Received:2013-02-24 Revised:2013-04-08 Online:2013-09-11 Published:2013-08-01
  • Contact: HAN Guanghui

摘要: 建立BM算法中函数shift及其构造算法的严格的形式理论,对于BM算法及其各种变形的研究与改进是十分必要的。给出了shift的一个清晰的形式定义,引入模式串后缀的特征集及其最小值函数,通过特征集描述了shift的构造,从而严格建立了shift及其构造算法的理论基础。根据shift的构造定理与最小值函数的迭代计算方法,给出了shift的一个新的构造算法,证明了该算法具有线性的时间与空间复杂度。理论分析和计算结果表明,该算法比已有算法更简单,计算复杂度更低,因而更适合硬件实现。

关键词: 串匹配, BM算法, 好后缀规则, shift函数, 复杂度分析

Abstract: For the research and improvement of Boyer-Moore (BM) algorithm and its variants, it is very necessary to establish strict formal theory of the function shift in Boyer-Moore's and its construction algorithm. A clear formal definition of shift was given. Then, characteristic sets of the pattern suffixes and its minimum value function were introduced, and the construction of shift was described by the characteristic sets, thus theoretical basis of shift and its construction algorithm were strictly established. Finally, a new construction algorithm of shift was presented based on the construction theorem of shift and iterative computing method of the minimum value function. It is proved that the algorithm has linear time and space complexity. The theoretical analysis and computing results show that the algorithm is simpler, and its complexity of computation is lower, so it is more suitable for hardware implementation compared with several existing algorithms.

Key words: string matching, Boyer-Moore (BM) algorithm, good-suffix rule, function shift, complexity analysis

中图分类号: