| 一种串匹配的快速Boyer-Moore算法 |
| |
| 引用本文： | 李雪梅,代六玲,童新海,李莉. 一种串匹配的快速Boyer-Moore算法[J]. 计算机应用研究, 2005, 22(9): 49-51 |
| |
| 作者姓名： | 李雪梅 代六玲 童新海 李莉 |
| |
| 作者单位： | 北京电子科技学院,电子信息工程系,北京,100070;南京理工大学,计算机科学系,江苏,南京,210094 |
| |
| 基金项目： | 国家自然科学基金资助项目（60272088） |
| |
| 摘 要： | 在对经典的Boyer-Moore和Quick Search串匹配算法进行分析的基础上，提出了一种更加快速的串匹配算法Quick Boyer-Moore（QBM）。QBM算法利用当前尝试中的已匹配子串、匹配失败字符信息以及与当前窗口下一个字符的位置信息，以在每一次跳跃中获得更大的跳跃距离，从而使算法具有更高的效率。在真实语料上的实验结果表明，QBM算法的效率较显著地高于原始的BM算法及其改进算法Impmved Boyer-Moore（IBM）。
|
| 关 键 词： | 串匹配 Boyer-Moore算法 Improved Boyer-Moore算法 Quick Boyer-Moore算法 |
| 文章编号： | 1001-3695(2005)09-0049-03 |
| 修稿时间： | 2004-09-04 |
Quick Boyer-Moore Algorithm for String Matching |
| |
| LI Xue-mei,DAI Liu-Ling,TONG Xin-hai,LI Li. Quick Boyer-Moore Algorithm for String Matching[J]. Application Research of Computers, 2005, 22(9): 49-51 |
| |
| Authors: | LI Xue-mei DAI Liu-Ling TONG Xin-hai LI Li |
| |
| Abstract: | This paper suggests a very efficient algorithm for string matching, Quick Boyer-Moore(QBM) algorithm, based on the ideas of the Boyer-Moore(BM) algorithm and the Quick Search(QS) algorithm. Besides the match and mismatch information inside the current window used by the Boyer-Moore algorithm, QBM also uses the information carried by the character immediately after the current window. The good-suffix shift distance of QBM is larger than that of BM algorithm in most circumstances. The tests on actual corpus show that QBM is more efficient than BM and the Improved Boyer-Moore(IBM) algorithm. |
| |
| Keywords: | String Matching Boyer-Moore Algorithm Improved Boyer-Moore Algorithm Quick Boyer-Moore Algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机应用研究》浏览原始摘要信息 |
|
点击此处可从《计算机应用研究》下载全文 |
