您的位置：首页 > 论文页面
多模式匹配快速算法的设计
发表时间：2008-06-30 浏览量：2655 下载量：904
| 全部作者： | 王永革，李胜才 |
| 作者单位： | 北京航空航天大学理学院 |
| 摘 要： | 字符串匹配速度是关键字检测和过滤系统的核心。本文在有限状态自动机AC算法的基础上，综合BM算法的跳跃思想和QS算法的优点，提出了一个快速的多模式字符串匹配算法。该算法能充分利用每次匹配过程中匹配不成功和已经成功的信息，尽可能多地跳过待查文本串中的字符，从而不需要匹配目标文本串的每个字符，而在比较次数最少的情况下，能一次性无需回溯地实现对文本的快速搜索。实验证明，在模式串较长和较短的情况下，该算法都能有效地改善关键字检测过滤系统的匹配性能。 |
| 关 键 词： | 算法理论；多模式串匹配；自动机理论；关键字检测过滤；匹配 |
| Title： | The design of a new fast multi-pattern matching algorithm |
| Author： | WANG Yongge, LI Shengcai |
| Organization： | School of Science, Beihang University |
| Abstract： | The string matching speed is one of the central issues of keywords detection and filtering system. Based on the AC algorithm for finite state automation, a fast algorithm to perform multi-pattern matching in a string is proposed which combines jump idea of boyer-moore(BM) algorithm and the advantages of an improved quick search(QS) algorithm. The algorithm makes full use of the successful results and failure ones in each matching and skips as more characters as possible. Hence, it can perform fast searching under least comparison times and without retrospect to each character in the target text. Experimental results show that the algorithm improves the matching ability of the keywords detection and filtering system for both cases of very long and very short patterns. |
| Key words： | algorithm theory; multi-pattern matching; automata theory; keywords detection and filtering; matching |
| 发表期数： | 2008年10月第12期 |
| 引用格式： | 王永革，李胜才. 多模式匹配快速算法的设计[J]. 中国科技论文在线精品论文，2008，1（12）：1354-1358. |
3
评论数 0请您登录
暂无评论
下载全文
多维论文