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

被引：14

作者：

范洪博 ^{[1
,2
]}

姚念民 ^{[1
]}

机构：

[1] 哈尔滨工程大学计算机科学与技术学院

[2] 绥化学院计算机科学与技术系

来源：

计算机研究与发展 | 2009年 / 46卷 / 08期

关键词：

串匹配; 精确单模式; 算法设计; 位并行; 文本搜索;

D O I：

暂无

中图分类号：

TP391.4 [模式识别与装置];

学科分类号：

0811 ; 081101 ; 081104 ; 1405 ;

摘要：

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

引用

页码：1341 / 1348

页数：8