基于非对齐双字节读机制的单模式串匹配算法

作     者：张建 范洪博 黄青松 刘利军 ZHANG Jian;FAN Hong-bo;HUANG Qing-song;LIU Li-jun

作者机构：昆明理工大学信息工程与自动化学院昆明650000 云南省计算机技术应用重点实验室昆明650000 

基　　金：云南省科技厅应用基础研究基金资助面上项目(2012FB131) 昆明理工大学人陪基金资助项目(KKSY201203091) 云南省社会发展科技计划基金资助项目(2010CA016) 科技部科技型中小企业技术创新基金资助项目(10C26215305130) 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2013年第39卷第12期

页      码：157-161页

摘      要：在线精确单模式匹配问题在几乎所有涉及文本和符号处理的领域中均有广泛应用。SBNDMq是目前该领域性能最高的算法之一。通过向其引入非对齐双字节读机制,对SBNDMq算法进行改进,从而提出SBNDMq_Shortb系列算法。该系列算法拥有与SBNDMq算法一致的跳跃能力,但核心循环的内存访问次数降低为原来的50%,算法性能更高。实验结果表明,在大多匹配条件下,SBNDMq_Shortb系列算法性能优于其他已知算法。

主 题 词：串匹配 精确单模式 算法设计 位并行 非对齐读 SBNDMq_Shortb算法 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 081104[081104] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.3969/j.issn.1000-3428.2013.12.034

馆 藏 号：203581393...