BM算法中函数shift的研究  

Research on function shift in Boyer-Moore algorithm

作　　者：韩光辉[1] 曾诚[2,3] 

机构地区：[1]武汉商业服务学院信息工程系,武汉430056 [2]湖北大学数学与计算机科学学院,武汉430062 [3]软件工程国家重点实验室(武汉大学),武汉430072

出　　处：《计算机应用》2013年第8期2379-2382,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60903034;61100018;61100025;61100026);湖北省自然科学基金资助项目(2011CDB069)

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

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

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