Horspool扩展算法在方块苗文模式匹配中的应用*
曾 磊，莫礼平，刘笔余，唐澳斌，莫春望，尹 娟
【摘 要】分析了Horspool算法的原理及特点，提出了一种适用于方块苗文环境的字符串模式匹配算法.该算法结合方块苗文的编码方式及字符串查找的特点，通过对Horspool算法中的字符处理单位进行扩展来适应方块苗文的字符串匹配.实验结果表明，在单字词、双字词和多字词的方块苗文字符串匹配过程中，该算法均呈现出较好的性能，能够用于解决方块苗文的快速检索问题.【期刊名称】吉首大学学报（自然科学版）【年(卷),期】2018(039)004【总页数】6
【关键词】模式匹配；字符串；Horspool算法；方块苗文
基金项目：国家自然科学基金资助项目(61462029，61741205)；湖南省教育厅科学研究项目(16C1314)；湖南省校企合作创新创业教育基地创新性项目(JDXC1702)
模式匹配用于解决从目标文本中查找给定模式串的问题，目前广泛应用于信息检索、模式识别、事件检测、生物计算等领域.假设待处理文本为T[0:n-1](长度为n的目标文本)，给定子串为P[0:m-1](长度为m的模式)，那么从T中找出与P相同的所有子串的问题就是模式匹配问题[1-2].模式匹配可以分为单模式匹配和多模式匹配.单模式匹配是从文本T中查找一个模式P，多模式匹配则是从文本T中一次性查找多个模式串P1，P2 …，Pq.英文字符串的单模式匹配是最常见的字符串匹配问题，可用线性或亚线性的KMP，BM和Horspool算法等高效的模式匹配算法来解决.KMP算法[3]是一种消除了朴素模式匹配算法中的回溯问题的前缀匹配算法，该算法属于稳定算法，即使在最坏情况下也能保持线性查找过程，其时间复杂度为O(n+m) [3-4].BM算法[5]是一种后缀匹配算法，采用从右向左比较字符和从左向右“跳跃式”移动模式串的方法，同时应用2种启发式规则(坏字符规则和好后缀规则)计算移动量，并从中选择最大值来决定模式串向右跳跃的距离[5].该算法又属于贪心算法，其时间复杂度在平均、最坏和最优3种情况下分别为O(n)，O(m×n)和O(n/m).在实际应用中，其性能优于KMP算法3～5倍[6].BM算法被提出以后，中外学者针对此算法进行了优化，提出了许多基于BM的改进算法[7-13]，Horspool算法便是其中最有效的算法之一.Horspool算法以BM算法为基础，但仅利用BM算法的坏字符规则来计算模式串的移动量，固定将匹配窗口的最后1个字符作为坏字符.笔者以Horspool算法为基础，对Horspool算法所处理的字符单位进行扩展，设计了一种适用于方块苗文信息检索的字符串模式匹配算法.
1 Horspool算法
1.1 算法原理
Horspool扩展算法在方块苗文模式匹配中的应用
