Space-time tradeoff in the Aho-Corasick string matching algorithm

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

1 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publication2015 IEEE Conference on Communications and NetworkSecurity, CNS 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages713-714
ISBN (Print)9781467378765
Publication statusPublished - 3 Dec 2015

Conference

Title3rd IEEE International Conference on Communications and Network Security, CNS 2015
PlaceItaly
CityFlorence
Period28 - 30 September 2015

Abstract

The Aho-Corasick (AC) string matching algorithm is widely used in intrusion detection systems and anti-virus systems. The basic version consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. In this article we study the space-time tradeoff in the AC algorithm. A transition rule table compression scheme based on transition edge elimination and perfect hashing is developed. The proposed method can reduce the size of the fully expanded transition rule table by a factor of 23 to 25, and the processing speed is 5 to 7.7 times the speed of the basic version.

Research Area(s)

  • deterministic finite automaton, string matching, transition rule table compression

Citation Format(s)

Space-time tradeoff in the Aho-Corasick string matching algorithm. / Xu, Yisi; Pao, Derek.

2015 IEEE Conference on Communications and NetworkSecurity, CNS 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 713-714 7346899.

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review