Regular Expression Search in a Stream

Regular expression search is a key primitive in myriads of applications, from web scraping to bioinformatics. A regular expression is a formalism for compactly describing a set of strings, built recursively from single characters using three operators: concatenation, union, and Kleene star. Two basic algorithmic problems concerning such expressions are membership and pattern matching. In the regular expression membership problem, we are given a regular expression R and a string T, and must decide whether T matches R. In the regular expression pattern matching problem, the task is to find the substrings of T that match R. In this talk, I will give a survey of recent algorithms for regular expression search in the practically relevant streaming setting.

Authors

• Tatiana Starikovskaya

Keywords

No keywords are indexed for this paper.