| 一种改进的多模式匹配算法 |
| |
| 引用本文： | 殷丽华,方滨兴.一种改进的多模式匹配算法[J].华中科技大学学报(自然科学版),2005,33(Z1):300-303. |
| |
| 作者姓名： | 殷丽华 方滨兴 |
| |
| 作者单位： | 哈尔滨工业大学,计算机网络与信息安全技术研究中心,黑龙江,哈尔滨,150001 |
| |
| 基金项目： | 国家自然科学基金资助项目(60203021) |
| |
| 摘 要： | 在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.
|
| 关 键 词： | 字符串匹配 有限状态自动机 TunedBM算法 多模式匹配 算法复杂度 |
| 文章编号： | 1671-4512(2005)S1-0300-04 |
| 修稿时间： | 2005年8月25日 |
An improved algorithm for multiple patterns matching |
| |
| Yin Lihua,Fang Binxing.An improved algorithm for multiple patterns matching[J].JOURNAL OF HUAZHONG UNIVERSITY OF SCIENCE AND TECHNOLOGY.NATURE SCIENCE,2005,33(Z1):300-303. |
| |
| Authors: | Yin Lihua Fang Binxing |
| |
| Institution: | Yin Lihua Fang Binxing Assistant Professor,Network and Information Security Research Center,Harbin Institute of Technology,Harbin 150001,China. |
| |
| Abstract: | |
| |
| Keywords: | string matching finite state automaton Tuned BM algorithm multiple patterns matching computational complexity |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
