摘要： 在线精确单模式匹配问题在几乎所有涉及文本和符号处理的领域中均有广泛应用。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
中图分类号:
张建，范洪博，黄青松，刘利军. 基于非对齐双字节读机制的单模式串匹配算法[J]. 计算机工程.
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.