This "threading" approach looks more complicated than the classic NFA->DFA transformation via subset construction.
Also, I don't see how this "threading" solves the issue pointed out in the article:
> This backtracking-based approach works, but it comes with a problem. The number of branches we need to test can exponentially increase with the size of the regex in certain situations, which means that testing all the branches would potentially take forever.
> [...]
> This approach means we only need to do an amount of tests that’s directly proportional to the size of the string we’re testing against. There’s no possibility for exponential growth, and so our algorithm is said to guarantee to match in linear time.
If the number of branches grows exponentially, then the number of "threads" will also grow exponentially. And so the number of states you step through "simultaneously" will grow exponentially. This "simultaneously" seems to be a bit of a sleight of hand in this article. (Also note that the actual code doesn't use multithreading, although that also wouldn't solve the issue --- you'd just have a big number of actual threads to start and coordinate which would probably also be slower, not faster.)
Subset construction is O(2^m), where m is the number of nodes of NFA. It looks scary, but it's important to note that it doesn't depend on the size of string which we're matching against at all. Matching against the string will be linear. And once you have the DFA you may reuse it for many different strings.
All the while, this "threading" still seems exponential wrt branches, but you can't reuse it for different strings.
I'm not the author of this implementation, so I don't have sufficient understanding of the algorithm to explain why your reasoning is wrong, but the threading approach is widely known (used in e.g. Go) and is not exponential.
A good explanation of why and how it works can be found in a collection of posts by Russ Cox, at https://swtch.com/~rsc/regexp/.
Russ made a different claim though. He wrote that the backtracking approach is O(2^n), where n is the size of the string matched against, while simulating NFA is O(mn)[1] (not O(n) as the article claims), where m is the length of the regex. The article on the other hand claims that backtracking gives you O(2^m):
> This backtracking-based approach works, but it comes with a problem. The number of branches we need to test can exponentially increase with the size of the regex in certain situations, which means that testing all the branches would potentially take forever.
I think that's where it went wrong. And my comment is also subtly wrong in that it implicitly assumed this is right and proceeded from there.
The important part though is that simulating an NFA grows with the regex, while with DFA it doesn't, and you can also find it in Russ's article ("Caching the NFA to build a DFA").
The article's claim that this is what grep and AWK use is also contradicted by Russ. Claim:
> Incidentally, this is the approach used in grep and awk.
Russ:
> Awk, Tcl, GNU grep, and GNU awk build DFAs, either precomputing them or using the on-the-fly construction described in the next section.
[1]: Most sources claim that it's actually O(nm^2), where m is the number of states of NFA (which is linear to length of regex, so you can treat m as length of regex as well).
Hi, author here! I think you're right that some things in the article are a bit wrong, I seem to have used inaccurate wording about the actual complexity, and I think I also failed to differentiate between the NFA and DFA cases (which I wanted to do a bit for simplicity, but it seems I overdid it). I'll be looking over the details more carefully and updating the wording. Thank you for your comment! :)
5 comments
[ 3.0 ms ] story [ 24.9 ms ] threadAlso, I don't see how this "threading" solves the issue pointed out in the article:
> This backtracking-based approach works, but it comes with a problem. The number of branches we need to test can exponentially increase with the size of the regex in certain situations, which means that testing all the branches would potentially take forever.
> [...]
> This approach means we only need to do an amount of tests that’s directly proportional to the size of the string we’re testing against. There’s no possibility for exponential growth, and so our algorithm is said to guarantee to match in linear time.
If the number of branches grows exponentially, then the number of "threads" will also grow exponentially. And so the number of states you step through "simultaneously" will grow exponentially. This "simultaneously" seems to be a bit of a sleight of hand in this article. (Also note that the actual code doesn't use multithreading, although that also wouldn't solve the issue --- you'd just have a big number of actual threads to start and coordinate which would probably also be slower, not faster.)
Subset construction is O(2^m), where m is the number of nodes of NFA. It looks scary, but it's important to note that it doesn't depend on the size of string which we're matching against at all. Matching against the string will be linear. And once you have the DFA you may reuse it for many different strings.
All the while, this "threading" still seems exponential wrt branches, but you can't reuse it for different strings.
A good explanation of why and how it works can be found in a collection of posts by Russ Cox, at https://swtch.com/~rsc/regexp/.
> This backtracking-based approach works, but it comes with a problem. The number of branches we need to test can exponentially increase with the size of the regex in certain situations, which means that testing all the branches would potentially take forever.
I think that's where it went wrong. And my comment is also subtly wrong in that it implicitly assumed this is right and proceeded from there.
The important part though is that simulating an NFA grows with the regex, while with DFA it doesn't, and you can also find it in Russ's article ("Caching the NFA to build a DFA").
The article's claim that this is what grep and AWK use is also contradicted by Russ. Claim:
> Incidentally, this is the approach used in grep and awk.
Russ:
> Awk, Tcl, GNU grep, and GNU awk build DFAs, either precomputing them or using the on-the-fly construction described in the next section.
[1]: Most sources claim that it's actually O(nm^2), where m is the number of states of NFA (which is linear to length of regex, so you can treat m as length of regex as well).