| 一个快速的字符串模式匹配改进算法 |
| |
| 引用本文： | 张娜,张剑.一个快速的字符串模式匹配改进算法[J].微电子学与计算机,2007,24(4):102-105,110. |
| |
| 作者姓名： | 张娜 张剑 |
| |
| 作者单位： | 合肥工业大学,计算机与信息学院,安徽,合肥,230009 |
| |
| 摘 要： | 在分析了BM算法以及一些重要的改进算法的基础上，提出了一种新的改进算法——BMG算法。该算法结合了BMH算法和BMHS算法的优点，同时考虑了字符串后一位字母的唯一性，提高了最大位移m＋1的出现概率，有效地加快了匹配速度。BMG算法已经通过实验测试，并证明是有效的，测试结果表明该算法比BM、BMH、BMHS算法有更好的性能。
|
| 关 键 词： | 模式匹配 字符串检索 BM算法 BMH算法 BMHS算法 |
| 文章编号： | 1000-7180（2007）04-0102-04 |
| 修稿时间： | 2006-03-20 |
A Fast Improved Algorithm for Pattern Matching in String |
| |
| ZHANG Na,ZHANG Jian.A Fast Improved Algorithm for Pattern Matching in String[J].Microelectronics & Computer,2007,24(4):102-105,110. |
| |
| Authors: | ZHANG Na ZHANG Jian |
| |
| Affiliation: | School of Computer and Information, Hefei University of Technology, Hefei 230009, China |
| |
| Abstract: | On the basis of BM algorithm and some important improvement algorithms, a new improved algorithm- BMG is presented. This algorithm combines the merits of BMH and BMHS.At the same time, the uniqueness of next character is taken into account. This algorithm greatly enhances the probability of occurrence of the largest right Goodsuffix m 1, thus improves the matching speed effectively. BMG algorithm passed test and proves to be valid. The test results shows that the algorithm has better performance than BM, BMH, BMHS algorithm. |
| |
| Keywords: | pattern matching string searching BM algorithm BMH algorithm BMHS algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
