Improved string matching algorithm

Abstract

Abstract: String matching algorithm is an important method in intrusion detection. An improved algorithm is proposed for string matching based on the discussions of several common string matching algorithms, for example, AC, AC_BMH, Sunday, etc. This algorithm can jump over more characters to do next matching when this matching is lost. At the same time, the matching times decrease sharply. In this case, it improves the matching efficiency. The analysis of this algorithm’s performance and the comparisons of the testing results of several matching algorithms are given.

Key words: pattern matching, AC algorithm, AC_BMH algorithm

摘要： 基于字符串匹配的检测方法是入侵检测系统中的一种重要方法。通过分析几种常见的字符串匹配算法（AC、AC_BMH、Sunday等）的基础，提出了一种对AC算法的改进，新算法每一次匹配不成功后都能跳过尽可能多的字符以进行下一轮匹配，使得匹配次数大大减少，从而提高了匹配效率。分析了该算法的性能，并用具体的实验数据给出了几种匹配算法的测试结果。

关键词: 模式匹配, AC算法, AC_BMH算法

DONG Shibo, LI Xungen, YIN Zhenzhen. Improved string matching algorithm[J]. Computer Engineering and Applications, 2013, 49(8): 133-137.

董世博，李训根，殷珍珍. 一种改进的字符串多模式匹配算法[J]. 计算机工程与应用, 2013, 49(8): 133-137.

[1]	ZHANG Yi, WANG Yanbo, GAO Qifeng, YANG Dewei, WEI Bo. Recognition and Location of Cigarette Packages Based on Improved FAST-SURF Algorithm [J]. Computer Engineering and Applications, 2020, 56(3): 252-258.
[2]	SUN Yunhao, LI Fengyu, LI Guanyu, HAN Bing, XING Weikang. Multi-pattern Matching Method for RDF Graph [J]. Computer Engineering and Applications, 2020, 56(13): 84-92.
[3]	WANG Hong, ZHU Han, LIN Haizhou. Research on Causality Extraction of Civil Aviation Accident [J]. Computer Engineering and Applications, 2020, 56(11): 265-270.
[4]	TAN Zhanglu, WANG Zhaogang, HU Han. Research on Trend Similarity Measurement Method of Time Series [J]. Computer Engineering and Applications, 2020, 56(10): 94-99.
[5]	HUANG Simeng1, CHENG Lianglun2, WANG Tao2. Multi-Pattern Complex Event Detection Method Based on Double-Array Trie-Tree [J]. Computer Engineering and Applications, 2019, 55(4): 91-95.
[6]	CAO Wanpeng, LUO Yunbin, SHI Hui. Robust AdaBoost classifier construction method against outlier interference [J]. Computer Engineering and Applications, 2018, 54(7): 132-137.
[7]	REN Shengbing, WANG Zhijian, WANG Yu. Layout mining and pattern matching algorithm on automatic Web page design [J]. Computer Engineering and Applications, 2018, 54(3): 227-232.
[8]	XIA Nian, SONG Tian. Short-rule-efficient rapid multi-pattern matching algorithm [J]. Computer Engineering and Applications, 2017, 53(7): 1-8.
[9]	WANG Qi1，2，3, LU Yuhai1，3, LIU Yang1，3, LIU Yanbing1，3, TAN Jianlong1，3, SUN Bo4. Dynamical adaptive Karp-Rabin multi-pattern matching algorithm [J]. Computer Engineering and Applications, 2017, 53(4): 39-44.
[10]	FAN Hongbo, SHI Shupeng, ZHANG Jing. Improvement of multi-patterns string matching algorithms of Advanced AC [J]. Computer Engineering and Applications, 2017, 53(3): 68-73.
[11]	LI Li1, JIANG Yu’e1, LIN Jie1, JIANG Binghua2. Improved algorithm KMPP based on KMP [J]. Computer Engineering and Applications, 2016, 52(8): 33-37.
[12]	ZHANG Yuye1, WANG Yingying1, WANG Chunxin2, PENG Haijun1. Acrobatic maneuver reorganization method compared with parameters relevance and feature of sequence change [J]. Computer Engineering and Applications, 2016, 52(5): 246-249.
[13]	LI Xinyu, HOU Chunping, WANG Baoliang, NING Guojin, YU Kuixing. Research on automated testing of mobile applications based on image matching [J]. Computer Engineering and Applications, 2016, 52(13): 43-47.
[14]	XU Yongkang1, YANG Guanglu2, LU Songfeng3. Approximate string matching algorithm based on compressed suffix array [J]. Computer Engineering and Applications, 2015, 51(23): 139-142.
[15]	WANG Hong1，2, WANG Peng1，2. Improved AC pattern matching algorithm based on GPU [J]. Computer Engineering and Applications, 2015, 51(18): 7-12.

Improved string matching algorithm

一种改进的字符串多模式匹配算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics