High-performance string matching algorithm for large scale string set

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (34): 168-170.

• 网络、通信与安全 • Previous Articles Next Articles

High-performance string matching algorithm for large scale string set

LI Xue¹,XUE Yi-bo²,WANG Chun-lu¹

1.School of Computer Science & Technology，Beijing University of Posts and Telecommunications，Beijing 100876，China
2.Research Institute of Information Science and Technology，Tsinghua University，Beijing 100084，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-12-01 Published:2007-12-01
Contact: LI Xue

一种适用于大规模特征集的快速匹配算法

李雪¹,薛一波²,王春露¹

1.北京邮电大学计算机科学与技术学院，北京 100876
2.清华大学信息技术研究院，北京 100084

通讯作者: 李雪

Abstract

Abstract: A fast string matching algorithm for large scale string set called SRS is addressed in this paper，it can achieve good performance.The speed of string matching using SRS algorithm can be 10 times higher than that using classical algorithm when the string set is 100 thousand.SRS algorithm can be employed to many applications areas，such as content filtering，antivirus，anti-spam，short message filtering，IDS/IPS systems etc.

Key words: string matching, large scale set pattern matching, SRS algorithm

摘要： 提出了一种适用于大规模特征集的快速匹配算法——SRS算法，该算法性能优异，在特征集达到100 000条时，匹配速度比经典算法快10倍以上。该算法适用于内容过滤、防病毒、反垃圾邮件、短信过滤、网络入侵检测和防御等众多领域。

关键词: 字符串匹配, 大规模特征匹配, SRS算法

LI Xue¹,XUE Yi-bo²,WANG Chun-lu¹. High-performance string matching algorithm for large scale string set[J]. Computer Engineering and Applications, 2007, 43(34): 168-170.

李雪¹,薛一波²,王春露¹. 一种适用于大规模特征集的快速匹配算法[J]. 计算机工程与应用, 2007, 43(34): 168-170.

[1]	ZHANG Yuqing, WANG Weiping, WANG Wei. Identification of changed browser fingerprint [J]. Computer Engineering and Applications, 2018, 54(7): 102-106.
[2]	XIA Nian, SONG Tian. Short-rule-efficient rapid multi-pattern matching algorithm [J]. Computer Engineering and Applications, 2017, 53(7): 1-8.
[3]	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.
[4]	LI Zhiwen, ZHANG Wei. String matching technology for large-scale short pattern set [J]. Computer Engineering and Applications, 2014, 50(1): 105-110.
[5]	CHEN Hu1, PENG Jiangfeng2, SHI Shaohuai1. gAC: high performance AC algorithm based on GPU [J]. Computer Engineering and Applications, 2012, 48(12): 43-48.
[6]	HU Ming-xiao¹，Leon X.Ding². Document distance metric used in plagiarism detection [J]. Computer Engineering and Applications, 2010, 46(7): 148-152.
[7]	CHEN Xiao-jun¹,ZHANG Zhi-bin¹,LIU Yan-bing¹,GUO Li². Charactering memory access behavior of large scale multi-string matching algorithms [J]. Computer Engineering and Applications, 2007, 43(26): 106-109.

High-performance string matching algorithm for large scale string set

一种适用于大规模特征集的快速匹配算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 7

Recommended Articles

Metrics