单模式精确匹配算法研究  

Study of single pattern exact matching algorithms

作　　者：巫喜红[1] 凌捷[2] 

机构地区：[1]嘉应学院计算机科学与技术系,广东梅州514015 [2]广东工业大学计算机学院,广东广州510090

出　　处：《合肥工业大学学报（自然科学版）》2007年第7期840-843,共4页Journal of Hefei University of Technology：Natural Science

基　　金：广东省科技攻关资助项目(2005B10101067);广州市科技攻关资助项目(2005Z3D0291)

摘　　要：模式匹配算法在各领域中有重大的应用价值。文章详细分析了BF、KMP、BM、Tuned BM和QS 5种单模式精确匹配算法;通过上机实验,采用不同的模式串长度对这些算法的匹配次数、比较过的字符个数和所需时间3方面进行测试;结果表明,BM、Tuned BM、QS算法在实际运行性能相对较好;而Tuned BM算法可有效地减少字符比较次数,是其中时间复杂最优的算法。Presented in the paper is a detailed analysis of five single pattern exact matching algorithms including the Brute-Force（BF） algorithm,the Knuth-Morris-Pratt（KMP） algorithm,the Boyer-Moore （BM） algorithm,the Tuned BM algorithm and the Quick Search（QS） algorithm. Some experiments are made in which the attempted times, character comparisons and needed time of these algorithms are tested through using different length of pattern strings. It is concluded that the performance of the BM, Tuned BM and QS algorithms is satisfactory in actual operation. The Tuned BM algorithm is the quickest one among these algorithms because it can reduce character comparisons effectively and shorten the time.

关 键 词：单模式精确匹配 BM算法 Tuned BM算法 QS算法 

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