| 单模跳跃算法的分析与改进 |
| |
| 引用本文： | 李超,林闯,欧阳莹,胡亚达,洪孙安.单模跳跃算法的分析与改进[J].清华大学学报(自然科学版),2009(7). |
| |
| 作者姓名： | 李超 林闯 欧阳莹 胡亚达 洪孙安 |
| |
| 作者单位： | 清华大学计算机科学与技术系; |
| |
| 基金项目： | 国家自然科学基金资助项目(60373013,60432030);;国家“九七三”重点基础研究项目(2006CB708301) |
| |
| 摘 要： | 为改进串匹配的效率,通过引入有效载荷,对Horspool算法进行了分析。在字符集较小而模式串长度较大时,跳跃距离受字符集大小限制严重。结合好后缀思想,提出了基于好后缀的Horspool算法GsHor:比较窗口内对应末位字符相同的情况下使用好后缀距离移动窗口;结合Quick Search思想,提出了基于坏字符块的Horspool算法BcbHor。实验表明:字符集大小为4时,GsHor算法的比较次数比Horspool算法减小18%以上,BcbHor算法至少减少42.4%。
|
| 关 键 词： | 有效载荷 Horspool算法 好后缀 坏字符 |
Single-pattern jumping algorithm |
| |
| LI Chao,LIN Chuang,OU Yangying,HU Yada,Peter D.Ungsunan.Single-pattern jumping algorithm[J].Journal of Tsinghua University(Science and Technology),2009(7). |
| |
| Authors: | LI Chao LIN Chuang OU Yangying HU Yada Peter DUngsunan |
| |
| Institution: | Department of Computer Science and Technology;Tsinghua University;Beijing 100084;China |
| |
| Abstract: | 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 be 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 Horspoo... |
| |
| Keywords: | effective-load Horspool algorithm good-suffix bad-character |
| 本文献已被 CNKI 等数据库收录！ |
