一种快速的单模式匹配算法  

Faster algorithm for single pattern matching

作　　者：蔡晓妍[1] 戴冠中[1] 杨黎斌[1] 

机构地区：[1]西北工业大学自动化学院,西安710072

出　　处：《计算机应用研究》2008年第1期45-46,81,共3页Application Research of Computers

基　　金：国家"863"计划资助项目(2005AA147030);国防基础科研资助项目(C2720061361)

摘　　要：在对Boyer-Moore(BM)算法及其改进的Tuned Boyer-Moore(TunedBM)算法进行分析的基础上,提出了一种更加快速的单模式匹配算法——NFS。该算法利用当前尝试中匹配失败字符的位置信息进行更大的尝试位置移动,使算法具有更高的效率。实验结果表明,NFS算法的性能优于同类的其他算法,特别是在模式长度较短的情况下,优势更为明显。This paper proposed a more efficient algorithm, NFS algorithm, based on the ideas of Boyer-Moore（BM） algorithm and Tuned Boyer-Moore（TunedBM） algorithm for single pattern matching. NFS used the mismatch information to increase the shift distance so that it was more efficient. The experimental results show that the algorithm is superior to other algorithms for pattern matching. Especially, when the pattern is small, it is more efficient than other algorithms.

关 键 词：模式匹配 BM算法 TunedBM算法 新的快速搜索算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]