| 一种快速单模式准确匹配算法 |
| |
| 引用本文： | 王永成,陈桂林,韩客松.一种快速单模式准确匹配算法[J].上海交通大学学报,2001,35(2):192-196. |
| |
| 作者姓名： | 王永成 陈桂林 韩客松 |
| |
| 作者单位： | 上海交通大学电子信息学院, |
| |
| 基金项目： | 国家"863"计划资助项目(863-306-ZD03-04-1) |
| |
| 摘 要： | 引入连续跳跃查找文本的思想，提出了一种新的单模式精确匹配算法，其最优条件下的时间复杂度为On/(m 1)]，新算法的平均时间复杂度分析表明其具有优越的查找性能，对比实验结果显示，新算法的性能优于目前所见的同类算法，特别是在模式较短的情况下，优势更为明显，这一特点非常适合于自然语言文本的检索。
|
| 关 键 词： | 模式匹配 波艺尔－默尔算法 快速搜索算法 时间复杂度 算法 |
| 文章编号： | 1006-2467(2001)02-0192-05 |
| 修稿时间： | 2000年3月17日 |
Faster Algorithm for
Single Pattern Matching |
| |
| WANG Yong-cheng,CHEN Gui-lin,HAN Ke-song.Faster Algorithm for
Single Pattern Matching[J].Journal of Shanghai Jiaotong University,2001,35(2):192-196. |
| |
| Authors: | WANG Yong-cheng CHEN Gui-lin HAN Ke-song |
| |
| Abstract: | A faster algorithm was suggested for single pattern matching by utilizing a continuous skip over the text. This idea has high performance because of the large shift on the text. Its best time complexity is On/(m 1)] , which is an inspiring research result. This paper also discussed the average time complexity of this suggested algorithm, which demonstrates and proves its high efficiency. The experimental result shows that the algorithm is superior to other algorithms for pattern matching. Especially, when the pattern is small, it is more efficient than other algorithms, which is very practical in natural language text retrieval. |
| |
| Keywords: | pattern matching Boyer Moore algorithm quick search algorithm time complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
