HARDWARE-ACCELERATED REGULAR EXPRESSION MATCHING FOR HIGH-THROUGHPUT TEXT ANALYTICS

Advanced text analytics systems combine regular expres-sion (regex) matching, dictionary processing, and relational algebra for efficient information extraction from text doc-uments. Such systems require support for advanced regex matching features, such as start offset reporting and captur-ing groups. However, existing regex matching architectures based on reconfigurable nondeterministic state machines and programmable deterministic state machines are not designed to support such features. We describe a novel architecture that supports such advanced features using a network of state machines. We also present a compiler that maps the regexs onto such networks that can be efficiently realized on re-configurable logic. For each regex, our compiler produces a state machine description, statically computes the num-ber of state machines needed, and produces an optimized interconnection network. Experiments on an Altera Stratix IV FPGA, using regexs from a real life text analytics bench-mark, show that a throughput rate of 16 Gb/s can be reached. 1