Regex is quite possibly the most ubiquitous way to match text, appearing in (basically) every mainstream programming language. It is at its very basics, simple, fast, and very expressive. However, it can also be very complex, arcane, and in worst case painfully slow. This is exploited in a type of Denial of Service attack, called ReDoS, exploiting the power of regex. Poorly written regex has even caused an Cloudflare outage. It does however remain one of (if not the) best way to pattern match strings.
In this project we will look at the efficiency of different ways to pattern match text. We will compare different regex implementations, to other ways of matching text, such as handwritten solutions. We will write our own regex solver, and try to minimize the energy usage of it, and the running time. This will also give a fundamental understanding of different models of computation, in addition to letting you unleash your creativity for how to add new features to regex, while hopefully keeping the running time low.
# Background
## Regex, the efficiency of
Regex, is short for “regular expression”, to what is this regular referring to? The regularity of its use? The commonness of the concept? No, it is regular as in regular languages, a computational class defined by its machine: the finite automaton. The finite automaton is to regular languages what the Turing machine is to computable languages. Indeed a finite automaton is, in a certain sense, a subset of the Turing machine, dropping more advanced features like the ability to write. The finite automaton is (a) little more than an advanced flowchart.
There are essentially two different ways to implement a regex matcher: backtracking, and constructing a finite automaton.
## Backtracking
Backtracking is general algorithmic technique, aiming to incrementally build a solution. If at any given step the solution is determined to be invalid, then we “backtrack” to the last place we made a choice, and try the next choice. For regex, where many choices can be made, this can quickly blow up the solution search space.
Take the innocuous-looking regex ^(a+)+$, it matches strings only containing as. In regex, ^, and $ matches the start and end of a string respectively, + means at least one of the preceding group/character (or character class) should be matched, and () is a group. There are two choices in this regex which makes it slow for backtracking. How many a’s should a+ match, and how many groups of at least one a should (a+)+ match? For matching strings there are no problems, but if we try to match with non-matching strings, such as aaab we get some problems. First a+ matches all as, but then instead of end of string we see a b, so we backtrack. Maybe a+ then matches two as, no problem, we have another group which can match the remaining a. But then b is encountered and we have to try again. Then maybe a+ matches one a, leaving the other groups to match the remaining two as. To test all possible combinations would be the same as all the different ways to partition a set of identical elements, with a size equal to the number of as. And this number is in fact exponentially growing with respect to the amount of as, and hence the input size.
You might be thinking, this sounds a bit silly, surely this doesn’t actually happen? Well it does, or rather it can. Python’s in-built regex library re, seems to handle this fine, but when the amount of as is around 25, around 0.7s is used to determine it does not match. At 26, around 1.4s is used. In general, the running time seems to follow 0.0000000210 * 2^n, where n is the number of as. Following this trend one would expect a 1h runtime around n=38
The sharp eyed reader might notice ^(a+)+$ can be simplified by writing ^a+$, there is no reason for the group. This is admittedly an artificially selected example, but goes to show the weaknesses of backtracking.
## The other alternative
So what is one to do? Reg(ular)Ex(pression)s are in fact in one to one correspondence between regular languages. And regular languages are solved by finite automaton, which seemed very simple indeed! And they are, every (deterministic) finite automaton runs in O(n), for any input of length n, and they can also be simulated by regular computers, and they will still run in O(n).
What if we take the regex, turn it into a finite automaton, and then simulate this automaton on any given input? Well, then we get a O(n) automaton recognizing every string the regex did. Sure, the translation is done in O(m*n) time (m denoting the size of the regex), but this automaton can easily be encoded, and usually regex strings aren’t too long anyway. This construction is commonly called Thompson’s construction.
On a technical note we get a non-deterministic finite automaton, which can be translated into a deterministic finite automaton, or simply run as is. The determinism here refers to the automaton can make multiple choices at any place. It is easy to get rid of this non-determinism, but one might even want this determinism, splitting these choices between e.g. separate threads.
This increased speed does however come at a cost, any advanced regex features such as back-references (referring to an earlier matched group), lookahead and lookbehind will not be supported, as these features are not regular. An example of this is ^1?$|^(11+?)\1+$ which matches unary numbers which are not primes, e.g. 1, 1111, 111111.
# Relevant courses
- IN5580: Computability theory:
https://www.uio.no/studier/emner/matnat/ifi/IN5580/ - IN5380: Compiler Construction:
https://www.uio.no/studier/emner/matnat/ifi/IN5380/ - IN3130: Algorithms: Design and Efficiency: https://www.uio.no/studier/emner/matnat/ifi/IN3130/