Tools for Very Fast Regular Expression Matching
Authors:
- 11 March 2010
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Computer
- Vol. 43 (3) , 50-58
Abstract
Regular expressions, or regex, are a common choice for defining configurable rules for data parsing because of their expressiveness in detecting recurrent patterns and information. For many data-intensive applications, regex matching is the first line of defense in performing online data filtering. Unfortunately, few solutions can keep up with the increasing data rates and the complexity posed by sets with hundreds of expressions. DotStar addresses this problem by providing a complete algorithmic solution and a software tool chain that can compile large sets of user-provided regex first into a sequence of intermediate representations and then into an automaton that can search for matches in a single pass without backtracking. The entire software tool chain supports the extended Posix standard syntax for regex.Keywords
This publication has 9 references indexed in Scilit:
- Hardware-accelerated regular expression matching at multiple tens of Gb/s2012
- SCAMPI2009
- High-performance regular expression scanning on the Cell/B.E. processor2009
- Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia2007
- A high performance NIDS using FPGA-based regular expression matching2007
- Fast, Large-Scale String Match for a 10Gbps FPGA-Based Network Intrusion Detection System2003
- Flexible Pattern Matching in Strings2002
- Characterization of Glushkov automataTheoretical Computer Science, 2000
- THE ABSTRACT THEORY OF AUTOMATARussian Mathematical Surveys, 1961