单模跳跃算法的分析与改进  

Single-pattern jumping algorithm

作　　者：李超[1] 林闯[1] 欧阳莹[1] 胡亚达[1] 洪孙安[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《清华大学学报（自然科学版）》2009年第7期1007-1011,共5页Journal of Tsinghua University(Science and Technology)

基　　金：国家自然科学基金资助项目(60373013;60432030);国家"九七三"重点基础研究项目(2006CB708301)

摘　　要：为改进串匹配的效率,通过引入有效载荷,对Horspool算法进行了分析。在字符集较小而模式串长度较大时,跳跃距离受字符集大小限制严重。结合好后缀思想,提出了基于好后缀的Horspool算法GsHor:比较窗口内对应末位字符相同的情况下使用好后缀距离移动窗口;结合Quick Search思想,提出了基于坏字符块的Horspool算法BcbHor。实验表明:字符集大小为4时,GsHor算法的比较次数比Horspool算法减小18%以上,BcbHor算法至少减少42.4%。This paper presents an analysis of the string matching efficiency of the Horspool algorithm by introducing an effective-load analysis. The results show that the matching performance can he greatly improved especially with small data sets and long pattern lengths. This algorithm integrates good-suffix shifting and the Horspool algorithm. Another algorithm was developed by combining a quick search method. Results show that the comparsion times of GsHor and BcbHor are reduced by 18% and 42.4% compared with Horspool when N is 4.

关 键 词：有效载荷 HORSPOOL算法 好后缀 坏字符 

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