一种高速精确单模式串匹配算法

作     者：范洪博 姚念民 Fan Hongbo;Yao Nianmin

作者机构：哈尔滨工程大学计算机科学与技术学院哈尔滨150001 绥化学院计算机科学与技术系黑龙江绥化152000 

基　　金：国家自然科学基金项目(60503055) 黑龙江省博士后启动基金项目(323630217)~~ 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2009年第46卷第8期

页      码：1341-1348页

摘      要：串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法.

主 题 词：串匹配 精确单模式 算法设计 位并行 文本搜索 

学科分类：0810[工学-土木类] 0808[工学-自动化类] 0839[0839] 081203[081203] 08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203856408...