一种改进的多模式串匹配算法

作     者：代六玲 黄河燕 陈肇雄 DAI Liu-Ling;HUANG He-Yan;CHEN Zhao-Xiong

作者机构：北京理工大学软件学院北京100081 中国科学院计算机语言信息工程研究中心北京100083 

基　　金：国家自然科学基金(No.60272088) 

出 版 物：《模式识别与人工智能》 (Pattern Recognition and Artificial Intelligence)

年 卷 期：2006年第19卷第1期

页      码：47-51页

摘      要：在对著名的 SunWu 多模式串匹配算法进行分析之后,结合 QS 算法的优点,设计了一种较高效的多模式串匹配算法 QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果.

主 题 词：多模式串匹配 Boyer-Moore算法 Quick Search算法 SunWu算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1003-6059.2006.01.009

馆 藏 号：203141776...