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

doi:10.3969/j.issn.1000-3428.2013.12.034

计算机工程

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

张建^,2，范洪博^1,2，黄青松^1,2，刘利军¹

(1. 昆明理工大学信息工程与自动化学院，昆明 650000；2. 云南省计算机技术应用重点实验室，昆明 650000)

收稿日期:2012-10-22 出版日期:2013-12-15 发布日期:2013-12-13
作者简介:张建(1987－)，男，硕士研究生，主研方向：智能信息系统；范洪博，讲师、博士；黄青松，教授；刘利军，讲师、硕士
基金资助:
云南省科技厅应用基础研究基金资助面上项目(2012FB131)；昆明理工大学人陪基金资助项目(KKSY201203091)；云南省社会发展科技计划基金资助项目(2010CA016)；科技部科技型中小企业技术创新基金资助项目(10C26215305130)

Single Pattern String Matching Algorithm Based on Unaligned 2-byte Reading Mechanism

ZHANG Jian ^1,2, FAN Hong-bo ^1,2, HUANG Qing-song ^1,2, LIU Li-jun¹

(1. Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650000, China; 2. Yunnan Key Laboratory of Computer Technology Applications, Kunming 650000, China)

Received:2012-10-22 Online:2013-12-15 Published:2013-12-13

摘要/Abstract

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

关键词: 串匹配, 精确单模式, 算法设计, 位并行, 非对齐读, SBNDMq_Shortb算法

Abstract: Online exact single pattern string matching is widely used in almost all of fields involving text and symbol processing. SBNDMq is one of the fastest algorithms in this field. By introducing the unaligned 2-byte reading, SBNDMq is improved and a serial of algorithm named SBNDMq_Shortb is presented. The jump capability of this algorithm is same with SBNDMq, but the memory access reduces 50%. Thus, this algorithm is faster than SBNDMq. Experimental results show that SBNDMq_Shortb is faster than other well- known algorithms in many matching conditions on the platform.

Key words: string matching, exact single pattern, design of algorithms, bit-parallel, unaligned reading, SBNDMq_Shortb algorithm

中图分类号:

TP18

张建，范洪博，黄青松，刘利军. 基于非对齐双字节读机制的单模式串匹配算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.12.034.

ZHANG Jian, FAN Hong-bo, HUANG Qing-song, LIU Li-jun. Single Pattern String Matching Algorithm Based on Unaligned 2-byte Reading Mechanism[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.12.034.

http://www.ecice06.com/CN/Y2013/V39/I12/157

参考文献

参考文献 [1] Faro S, Lecroq T. The Exact String Matching Problem: A Comprehensive Experimental Evaluation[EB/OL]. (2012-10- 06). http://arxiv.org/pdf/1012.2547. [2] Faro S, Lecroq T. The Exact Online String Matching Problem: A Review of the Most Recent Results[EB/OL]. (2012-10-06). http://www-igm.univ-mlv.fr/~lecroq/articles/acmsurv2013. pdf. [3] Durian B, Holub J, Peltola H, et al. Tuning BNDM with q-grams[C]//Proc. of the 11th Workshop on Algorithm Engineering and Experiments. New York, USA: [s. n.], 2009. [4] Navarro G, Raffinot M. A Bit-parallel Approach to Suffix Automata: Fast Extended String Matching[R]. Santiago, Chile: Department of Computer Science, University of Chile, Technical Report: DC-98-1, 1998. [5] 范洪博, 姚念民. 一种高速精确单模式串匹配算法[J]. 计算机研究与发展, 2009, 46(8): 1341-1348. [6] Peltola H. Variations of Forward-SBNDM[C]//Proc. of Prague Stringology Conference. Prague, Czech: [s. n.], 2011. [7] Faro S, Lecroq T. String Matching Research Tool[EB/OL]. (2012-10-06). http://www.dmi.unict.it/~faro/smart/. [8] Fredriksson K, Grabowski S. Practical and Optimal String Matching[C]//Proc. of SPIRE’05. 2005: 376-387. [9] ?urian B, Peltola H, Salmela L. Bit-parallel Search Algorithms for Long Patterns[C]//Proc. of SEA’10. 2010: 129. [10] Fan Hongbo, Yao Nianmin, Ma Haifeng. A Practical and Average Optimal String Matching Algorithm Based on Lecroq[C]//Proc. of Internet Computing for Science and Engineering Conference. Harbin, China; [s. n.], 2011. [11] Faro S. A Fast Suffix Automata Based Algorithm for Exact Online String Matching[C]//Proc. of CIAA’12. 2012: 149-158. [12] Faro S, Lecroq T. A Multiple Sliding Windows Approach to Speed Up String Matching Algorithms[C]//Proc. of TIBS’12. 2012: 172-183. [13] Lecroq T. Fast Exact String Matching Algorithms[J]. Infor- mation Processing Letter, 2007, 102(6): 229-235. [14] Baeza-Yates R A. A New Approach to Text Searching[J]. Communications of the ACM, 1992, 35(10): 74- 82. [15] Faro S, Lecroq T. Efficient Variants of the Backward- Oracle-Matching Algorithm[C]//Proc. of Prague Stringology Conference. Prague, Czech: [s. n.], 2008. [16] Salmela L, Tarhio J, Kyt?joki J. Multi-pattern String Matching with q-grams[J]. ACM Journal of Experimental Algorithmics, 2006, 11(1): 1-19. 编辑索书志

选择文件类型/文献管理软件名称

选择包含的内容

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

Single Pattern String Matching Algorithm Based on Unaligned 2-byte Reading Mechanism

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陶曌,杨建波,张波,张丽云. 面向比特流的分组快速搜索匹配算法[J]. 计算机工程, 2017, 43(6): 125-128,135.
[2]	许家铭，李晓东，金键，马盈. 一种高效的多模式字符串匹配算法[J]. 计算机工程, 2014, 40(3): 315-320.
[3]	王友钊，黄冬. 一种提高系统搜索效率的BM改进算法[J]. 计算机工程, 2014, 40(1): 63-67,71.
[4]	刘志刚, 杜娟, 许少华, 李盼池. 基于过程神经元网络的时间序列预测方法[J]. 计算机工程, 2012, 38(5): 199-201.
[5]	崔文科, 徐克付, 李娜娜, 胡玥. 基于CUDA的位并行近似串匹配算法[J]. 计算机工程, 2012, 38(22): 267-270.
[6]	吴旭, 贡华, 李汪根, 方群. 基于特征串匹配的X射线荧光光谱仪数据采集[J]. 计算机工程, 2012, 38(2): 250-252.
[7]	廖豪, 陈洁, 谭建龙. 大规模语料中频繁模式增量发现算法[J]. 计算机工程, 2011, 37(23): 27-29,32.
[8]	王桐桐. 一种多维并行报文分类算法[J]. 计算机工程, 2011, 37(18): 112-114.
[9]	陈鸿昶, 于洪涛, 冯晓磊. 一种改进的安全传真服务器设计方法[J]. 计算机工程, 2011, 37(17): 282-285.
[10]	赵光南, 吴承荣. 基于GPU的位并行多模式串匹配研究[J]. 计算机工程, 2011, 37(14): 265-267.
[11]	郭牧怡;刘萍;谭建龙;郭莉. 基于文件标题特征的网络视频去重研究[J]. 计算机工程, 2010, 36(9): 227-229,.
[12]	叶福军. MED算法及其在网页搜索中的应用[J]. 计算机工程, 2010, 36(2): 36-38.
[13]	武永超;华蓓;. 基于网络处理器的多模式串匹配研究[J]. 计算机工程, 2009, 35(8): 166-168.
[14]	杨毅夫;刘燕兵;刘萍;郭莉. 串匹配算法中的自动机紧缩存储技术[J]. 计算机工程, 2009, 35(21): 39-41.
[15]	范大娟;钟诚;许莉莉. 异构机群系统上近似串匹配并行算法[J]. 计算机工程, 2008, 34(3): 141-144.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

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

Single Pattern String Matching Algorithm Based on Unaligned 2-byte Reading Mechanism

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价