High Performance Regular Expression Matching Using Parallel Bit Stream Technology

Regular expressions can be thought of as a mini programming language that has a general pattern notation that allows you to search texts for occurrences of string patterns. Recently, a prototype compiler for regular expressions was introduced that provided a 5x or better performance advantage over its closest competitors. The prototype implemented a novel new approach for the parallel processing of text. The project that is being proposed will build upon the lessons that were learned from this initial prototype. The compiler will be modified in order to achieve platform independence, the compilation process will be optimized, and optimizations will be applied to the search algorithms in an attempt to extend the number of use cases where the compiler has a performance advantage. Upon the successful completion of this project, International Characters, Inc. will be provided with yet another high-performance software component that can be used to meet the needs of its customers.

Faculty Supervisor:

Dr. Nick Sumner

Student:

Dale Denis

Partner:

International Characters Inc.

Discipline:

Computer science

Sector:

Information and communications technologies

University:

Simon Fraser University