# Why is StringExpression faster than RegularExpression?

Edit: as noted by Albert Retey the performance difference is only seen when sub expression extraction is performed. If this test is used below the timings are similar:

First@Timing[r1 = StringCases[textBig, se];]
First@Timing[r2 = StringCases[textBig, re];]


According to the documentation:

Any symbolic string pattern is first translated to a regular expression. You can see this translation by using the internal StringPatternPatternConvert function.

StringPatternPatternConvert["a" | "" ~~ DigitCharacter ..] // InputForm

{"(?ms)a?\\d+", {}, {}, Hold[None]}


The first element returned is the regular expression, while the rest of the elements have to do with conditions, replacement rules, and named patterns.

The regular expression is then compiled by PCRE, and the compiled version is cached for future use when the same pattern appears again. The translation from symbolic string pattern to regular expression only happens once.

Based on this I would expect a StringExpression and the regular expression produced by PatternConvert to perform similarly, but they do not. Taking an example from this recent question please observe:

se = Shortest["(ICD-9-CM " ~~ code__ ~~ ")"];
re = First @ StringPatternPatternConvert[se] // RegularExpression

RegularExpression["(?ms)$ICD-9-CM (.+?)$"]

text1 = "  A  Vitamin D Deficiency (ICD-9-CM 268.9) (ICD-9-CM 268.9) 09/11/2015  01 ";
textBig = StringJoin @ ConstantArray[text1, 1*^6];

First@Timing[r1 = StringCases[textBig, se :> code];]
First@Timing[r2 = StringCases[textBig, re :> "\$1"];]

r1 === r2

0.718
1.903
True

• Why is using the StringExpression more than twice as fast as the RegularExpression?
• Is there a way to make the RegularExpression matching run just as quickly?
-
I think you have v7. Just mentioning that it's the same in 9 too. –  Szabolcs May 22 '13 at 15:59
The answer might be in StringPatternPatternConvert[re]... which is not the same as re. –  Szabolcs May 22 '13 at 16:00
@Szabolcs ?: means clustering but not capturing, so you can group regexes within (?:) but doesn't make backreferences as () does. –  Stefan May 22 '13 at 16:26
it seems like that StringExpression does something magical with RegularExpression. Presumably it does compile/cache the pattern –  Stefan May 22 '13 at 17:06
I have no time to investigate that more closely, but I think the difference could well come from how the resubstituting of the matches is implemented. If you try the same thing without such substitutions, then the runtime differences are marginal, e.g.: StringCases[textBig, RegularExpression["(?ms)$ICD-9-CM .+?$"]] vs. StringCases[textBig, Shortest["(ICD-9-CM " ~~ __ ~~ ")"]] seem to be equally fast (or probably slow when compared to pcregrep :-) –  Albert Retey May 22 '13 at 19:56

Since we can not see the source code of Mathematica, we don't know the detailed algorithm Mathematica use to do string pattern searching.

But in most other languages, they use KMP algorithm to do explicit string matching. KMP is in fact a very compact design of the DFA pattern matching algorithm. You can find a comparison here. You can see that the construction time complexity of KMP and DFA are O(m) and Θ(m |Σ|), where m is the length of the searching string and |Σ| is the size of the alphabets. But the matching phrase are all O(n) where n is the length of string to search. You can find a detailed code describe the DFA pattern search in Sedgewick's Algorithm 4th Edition. In Chapter 5 String, you can find the author provide a DFA simulation algorithm. The clever idea to build the prefix array is to match the string to search to itself and build the prefix array, instead of building the dfa[][] two dimensional array like in Sedgewick's book. But the essence of the two algorithm are the same. You can just think KMP as an optimization of the DFA pattern matching.

While Regular Expression is equivalent to Nondeterministic finite automaton(NFA). NFA is more powerful than DFA in computing, which means that all DFA can be expressed in NFA, while the opposite is not true. More power sometimes means more expensive to achieve. Although according to the wikipedia of Regular Expression#Running Time section, ther are algorithm that when the NFA is constructed, the pattern matching procedure can be done in O(n) . But in real life, the running time can usually be multiply by an constant factor. Like in this case, the regular expression code is two times slower than the string expression one. This may be because there are more memory usage to construct the NFA, which eventually cause more catch mis-match, or the more complex codes are compiled to more machine instructions while executing.

Like the blog post here also indicate a slower factor of regular expression compare to string matching in C#, but we can see that both algorithm running in linear time complexity, just with different slope. But there are also some algorithm of regular expression (like in perl), which runs exponentially. You can check it here

-