| 单模式精确匹配算法研究 |
| |
| 引用本文： | 巫喜红,凌捷.单模式精确匹配算法研究[J].合肥工业大学学报(自然科学版),2007,30(7):840-843. |
| |
| 作者姓名： | 巫喜红 凌捷 |
| |
| 作者单位： | 1. 嘉应学院,计算机科学与技术系,广东,梅州,514015
2. 广东工业大学,计算机学院,广东,广州,510090 |
| |
| 基金项目： | 广东省科技攻关资助项目(2005B10101067)，广州市科技攻关资助项目(2005Z3D0291) |
| |
| 摘 要： | 模式匹配算法在各领域中有重大的应用价值。文章详细分析了BF、KMP、BM、Tuned BM和QS 5种单模式精确匹配算法;通过上机实验,采用不同的模式串长度对这些算法的匹配次数、比较过的字符个数和所需时间3方面进行测试;结果表明,BM、Tuned BM、QS算法在实际运行性能相对较好;而Tuned BM算法可有效地减少字符比较次数,是其中时间复杂最优的算法。
|
| 关 键 词： | 单模式精确匹配 BM算法 TunedBM算法 QS算法 |
| 文章编号： | 1003-5060(2007)07-0840-04 |
| 修稿时间： | 2006年6月23日 |
Study of single pattern exact matching algorithms |
| |
| WU Xi-hong,LING Jie.Study of single pattern exact matching algorithms[J].Journal of Hefei University of Technology(Natural Science),2007,30(7):840-843. |
| |
| Authors: | WU Xi-hong LING Jie |
| |
| Abstract: | 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. |
| |
| Keywords: | single pattern exact matching BM algorithm Tuned BM algorithm QS algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
