一种快速高效的模式匹配算法的应用研究

doi:10.3778/j.issn.1002-8331.2008.32.028

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (32): 93-95.DOI: 10.3778/j.issn.1002-8331.2008.32.028

一种快速高效的模式匹配算法的应用研究

王杰,刘亚宾,孙珂珂

郑州大学电气工程学院，郑州 450001

收稿日期:2008-06-03 修回日期:2008-08-21 出版日期:2008-11-11 发布日期:2008-11-11
通讯作者: 王杰

Research of fast and memory-efficient pattern matching algorithm

WANG Jie,LIU Ya-bin,SUN Ke-ke

School of Electrical Engineering，Zhengzhou University，Zhengzhou 450001，China

Received:2008-06-03 Revised:2008-08-21 Online:2008-11-11 Published:2008-11-11
Contact: WANG Jie

摘要/Abstract

摘要： 提出一种高性能的模式匹配算法——MAC算法，它通过使用从确定性有限状态机（DFA）中得到的特征等同态，在保证高速匹配的前提下，极大地减少了内存需求。同时，该算法具有高度的灵活性，即通过调整就可以适应不同的特定性能和资源限制的要求。在软件使用环境中的实验结果表明，MAC算法的内存使用性能相对目前先进的模式匹配算法提高了1.51~2.40倍。

关键词: MAC算法, 网络入侵检测系统, 模式匹配, 确定性有限状态机, 非确定性有限状态机

Abstract: Modified Aho-Corasick（MAC） algorithm，an effective string matching algorithm with advantages of both compact memory and high performance，is proposed.By employing the characteristics of same states observed from the deterministic finite state automata，the proposed MAC significantly reduces the memory requirement without sacrificing high speed.The MAC algorithm also provides high flexibility that it can be tuned to fit specific performance requirement and resource constraints.The experimental results show that the performance of ACMS is over 1.51~2.40 times in software implementation compared to existing state-of-the-art algorithms.

Key words: Modified Aho-Corasick（MAC） algorithm, Network Intrusion Detection System（NIDS）, pattern matching, Deterministic Finite-state Automata（DFA）, Nondeterministic Finite-state Automata（NFA）

王杰,刘亚宾,孙珂珂. 一种快速高效的模式匹配算法的应用研究[J]. 计算机工程与应用, 2008, 44(32): 93-95.

WANG Jie,LIU Ya-bin,SUN Ke-ke. Research of fast and memory-efficient pattern matching algorithm[J]. Computer Engineering and Applications, 2008, 44(32): 93-95.

[1]	孙云浩，李逢雨，李冠宇，韩冰，邢维康. 面向RDF图的多模式匹配方法[J]. 计算机工程与应用, 2020, 56(13): 84-92.
[2]	王红，祝寒，林海舟. 航空安全事故因果关系抽取方法的研究[J]. 计算机工程与应用, 2020, 56(11): 265-270.
[3]	谭章禄，王兆刚，胡翰. 时间序列趋势相似性度量方法研究[J]. 计算机工程与应用, 2020, 56(10): 94-99.
[4]	黄思猛1，程良伦2，王涛2. 基于双数组trie树的多模式复杂事件检测方法[J]. 计算机工程与应用, 2019, 55(4): 91-95.
[5]	夏念，嵩天. 短规则有效的快速多模式匹配算法[J]. 计算机工程与应用, 2017, 53(7): 1-8.
[6]	王歧1，2，3，卢毓海1，3，刘洋1，3，刘燕兵1，3，谭建龙1，3，孙波4. 支持模式串动态更新的多模式匹配Karp-Rabin算法[J]. 计算机工程与应用, 2017, 53(4): 39-44.
[7]	范洪博，史舒鹏，张晶. 改进的AAC多模式实时匹配算法[J]. 计算机工程与应用, 2017, 53(3): 68-73.
[8]	李莉1，江育娥1，林劼1，江秉华2. 基于KMP算法的改进算法KMPP[J]. 计算机工程与应用, 2016, 52(8): 33-37.
[9]	张玉叶1，王颖颖1，王春歆2，彭海军1. 分析参数相关和时序特征的飞行动作识别方法[J]. 计算机工程与应用, 2016, 52(5): 246-249.
[10]	赵旭，王伟. 结合遗传算法的NIDS多媒体包多线程择危模型[J]. 计算机工程与应用, 2016, 52(14): 115-118.
[11]	袁淼，王鑫. 基于抽样的Deep Web模式匹配框架[J]. 计算机工程与应用, 2015, 51(3): 117-123.
[12]	胥永康1，杨光露2，路松峰3. 基于压缩后缀数组的近似字符串匹配算法[J]. 计算机工程与应用, 2015, 51(23): 139-142.
[13]	汪宏1，2，王鹏1，2. 基于GPU的AC模式匹配改进算法[J]. 计算机工程与应用, 2015, 51(18): 7-12.
[14]	文举荣，王永利，刘伟. 支持多类型瑕疵度量的RETE改进算法[J]. 计算机工程与应用, 2015, 51(15): 48-55.
[15]	沈璐1，2，纪允1，纪冬宝3，李萍4. 带可变长度通配符的模式匹配算法[J]. 计算机工程与应用, 2015, 51(15): 43-47.

一种快速高效的模式匹配算法的应用研究

Research of fast and memory-efficient pattern matching algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics