摘要
引入连续跳跃查找文本的思想 ,提出了一种新的单模式精确匹配算法 ,其最优条件下的时间复杂度为 O[n/(m+1 ) ],新算法的平均时间复杂度分析表明其具有优越的查找性能 .对比实验结果显示 ,新算法的性能优于目前所见的同类算法 ,特别是在模式较短的情况下 ,优势更为明显 ,这一特点非常适合于自然语言文本的检索 .
A faster algorithm was suggested for single pattern matching by utilizing a continuous skip over the text. It has high performance because of the large shift on the text. Its best time complexity is O[n/(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 results show 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 shows It is quite a practical tool in natural language text retrieval.
出处
《上海交通大学学报》
EI
CAS
CSCD
北大核心
2001年第2期192-196,共5页
Journal of Shanghai Jiaotong University
基金
国家"8 6 3"计划资助!项目 (86 3-30 6 -ZD0 3-0 4-1)
关键词
模式匹配
波艺尔-默尔算法
快速搜索算法
时间复杂度
算法
Algorithms
Data acquisition
Information retrieval
Natural language processing systems
Sorting
