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

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

作　　者：张建[1,2] 范洪博[1,2] 黄青松[1,2] 刘利军[1] 

机构地区：[1]昆明理工大学信息工程与自动化学院,昆明650000 [2]云南省计算机技术应用重点实验室,昆明650000

出　　处：《计算机工程》2013年第12期157-161,共5页Computer Engineering

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

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]