| 一种高速精确单模式串匹配算法 |
| |
| 引用本文： | 范洪博,姚念民.一种高速精确单模式串匹配算法[J].计算机研究与发展,2009,46(8). |
| |
| 作者姓名： | 范洪博 姚念民 |
| |
| 作者单位： | 1. 哈尔滨工程大学计算机科学与技术学院,哈尔滨,150001;绥化学院计算机科学与技术系,黑龙江绥化,152000
2. 哈尔滨工程大学计算机科学与技术学院,哈尔滨,150001 |
| |
| 基金项目： | 国家自然科学基金项目，黑龙江省博士后启动基金项目 |
| |
| 摘 要： | 串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法.
|
| 关 键 词： | 串匹配 精确单模式 算法设计 位并行 文本搜索 |
A Fast and Exact Single Pattern Matching Algorithm |
| |
| Fan Hongbo,Yao Nianmin.A Fast and Exact Single Pattern Matching Algorithm[J].Journal of Computer Research and Development,2009,46(8). |
| |
| Authors: | Fan Hongbo Yao Nianmin |
| |
| Affiliation: | College of Computer Science and Technology;Harbin Engineering University;Harbin 150001;Department of Computer Science and Technology;Suihua University;Suihua;Heilongjiang 152000 |
| |
| Abstract: | String matching problem is a fundamental problem in computer science.It is the key problem of many important scopes such as network security,information retrieval and filtration,computational biology,etc.And the design of exact single pattern string matching algorithm with high performance is the basis of all string matching problems.In this paper,the authors improve one of the fastest exact single pattern matching algorithms known on English text,which is SBNDM2.The simplest form of the BNDM core loop is o... |
| |
| Keywords: | string matching exact single pattern design of algorithm bit parallelism text searching |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
