| 一种存储优化的多模式匹配算法 |
| |
| 引用本文： | 段惠超,韩建民,邱晟.一种存储优化的多模式匹配算法[J].微型机与应用,2015(2):14-17. |
| |
| 作者姓名： | 段惠超 韩建民 邱晟 |
| |
| 作者单位： | 浙江师范大学数理与信息工程学院 |
| |
| 基金项目： | 国家自然科学基金(61170108);国家级大学生创新创业训练计划项目(201310345005) |
| |
| 摘 要： | AC(Aho-Corasick)自动机是经典的多模式匹配算法,但在模式串字符集较大的情况下,AC自动机的存储开销较大。为降低存储开销提出了存储优化的多模式匹配算法SMMA,该算法在Trie树建立阶段利用正向表来存储每个状态的后续状态指针以及失配指针,而无需存储字符集所有字符的后继指针,从而压缩了每个状态的储存空间。实验表明,所提出的算法与AC自动机算法在时间效率上相近,但极大地降低了存储开销。
|
| 关 键 词： | 模式匹配 AC自动机 Trie树 |
A storage-optimized multi-pattern matching algorithm |
| |
| Duan Huichao;Han Jianmin;Qiu Sheng.A storage-optimized multi-pattern matching algorithm[J].Microcomputer & its Applications,2015(2):14-17. |
| |
| Authors: | Duan Huichao;Han Jianmin;Qiu Sheng |
| |
| Affiliation: | Duan Huichao;Han Jianmin;Qiu Sheng;College of Mathematics, Physics and Information Engineering, Zhejiang Normal University; |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
|
