Seeking regex optimizer

[Kay Schluehr]

I have a list of strings ls = [s_1,s_2,...,s_n] and want to create a
regular expression sx from it, such that sx.match(s) yields a SRE_Match
object when s starts with an s_i for one i in [0,...,n]. There might
be relations between those strings: s_k.startswith( s_1) -> True or
s_k.endswith(s_ 1) -> True. An extreme case would be ls = ['a', 'aa',
....,'aaaa...ab ']. For this reason SRE_Match should provide the longest
possible match.

Is there a Python module able to create an optimized regex rx from ls
for the given constraints?

Regards,
Kay

[Mirco Wahab]

Thus spoke an*********@gma il.com (on 2006-06-19 22:51):

It uses Aho-Corasick for the implementation which is fast and does what
you expect it to do. Nor does it have a problem of matching more than
99 possible strings as the regexp approach may have.

If you pull the strings into (?>( ... )) (atomic groups),
this would't happen.

http://www.regular-expressions.info/atomic.html
...
Everything between (?>) is treated as one single token
by the regex engine, once the regex engine leaves the
group.
Because the entire group is one token, no backtracking
can take place once the regex engine has found a match
for the group.
...

Maybe Py.2.5 will have them?

Regards

Mrico

[andrewdalke]

Replying to me Mirco Wahab wrote:

If you pull the strings into (?>( ... )) (atomic groups),
this would't happen.

Given that Python's re engine doesn't support this feature
it doesn't really help the original poster's problem.

Even if some future Python did support it, the limit
to 100 named groups is unaffected by backtracking.

import re
re.compile("(.) "*100) Traceback (most recent call last):
File "<stdin>", line 1, in ?
File
"/Library/Frameworks/Python.framewor k/Versions/2.4/lib/python2.4/sre.py",
line 180, in compile
return _compile(patter n, flags)
File
"/Library/Frameworks/Python.framewor k/Versions/2.4/lib/python2.4/sre.py",
line 225, in _compile
p = sre_compile.com pile(pattern, flags)
File
"/Library/Frameworks/Python.framewor k/Versions/2.4/lib/python2.4/sre_compile.py" ,
line 506, in compile
raise AssertionError(
AssertionError: sorry, but this version only supports 100 named groups

There was no backtracking in "(.)"*100.

Andrew
da***@dalkescie ntific.com

[Kay Schluehr]

an*********@gma il.com wrote:

Kay Schluehr wrote:

I have a list of strings ls = [s_1,s_2,...,s_n] and want to create a
regular expression sx from it, such that sx.match(s) yields a SRE_Match
object when s starts with an s_i for one i in [0,...,n].

Why do you want to use a regex for this?

Because it is part of a tokenizer that already uses regexps and I do
not intend to rewrite / replace it. Certain groups of token (
operators, braces and special characters ) should be user extensible.
All others will stay as they are. I found that certain groups of token
might be represented in a more compact mannerr: for matching ['+',
'++'] one might generate '\+|\+\+' or '\+\+?' and I wanted to know if
there is some generic approach to solve the "inverse regexp" problem in
a non-trivial fashion.

Regards,
Kay

[andrewdalke]

Kay Schluehr replied to my question:

Why do you want to use a regex for this?
Because it is part of a tokenizer that already uses regexps and I do
not intend to rewrite / replace it.

Switching to pytst is not a big change - there will be little
impact on the rest of your code. On the other hand, it does
change your build and deployment process because of the
need for another package.

Because you are constraining yourself to regex there isn't
much of an improvement you can do.
I found that certain groups of token
might be represented in a more compact mannerr: for matching ['+',
'++'] one might generate '\+|\+\+' or '\+\+?' and I wanted to know if
there is some generic approach to solve the "inverse regexp" problem in
a non-trivial fashion.
There are a few questions which come up. Why do you want to
have a "more compact" representation? Do you think it will
make the result faster? Likely it will because of the reduced
need for backtracking but unless you have a lot of strings with
the same prefix then the number of backtracks should go as
something like the log of the number of words, which scales
pretty well.

Are you speed limited by the existing implementation? Likely
not. In which case the performance isn't an issue. Consider
this anecdote from http://www.technicat.com/writing/programming.html

I was asked in a phone interview with Google how I would
search for a number in an array of ordered numbers.
Obviously, the questioner was asking for a CS 101 answer -
binary search. But in real life, I would probably do the "wrong"
thing - search the array from beginning to end. There's no point
in taking twice the time to write twice as much code that has
to be maintained and debugged if the application performance
is good enough, and in particular if that piece of code is not
the bottleneck in the application. (And I seriously doubt you'd
have that data laid out linearly in a fixed array like that if it
was
the bottleneck)

As it turns out, the regexp implementation could do the optimization
you want. That is, it could recognize that the input sequence is
a set of fixed words (no special characters) and implement something
like Aho-Corasick, in which case you wouldn't need to change
your input.

I don't know if Python's regexp implementation does this already.
Neither do you. Test the functionality and performance first
before going starting other work.

I am not the first to give you this advice:

John Machin: Optimised with respect to what? speed? ease of construction?
gr*@ll.mit.edu: As others have suggested, you should first try the most naive
implementation before making a hard optimization problem out of this.

As for the general question of the existance of a "generic approach
to solve the "inverse regexp" problem in a non-trivial fashion."

Yes, there is. Kinda of. All (formal/theoretical) regular
expressions
can be written as a regular expression without need for backtracking.
If you look up the theory of regular expressions, backtracking occurs
when there are ambiguities in traversing the state machine. These
are called nondeterministi c finite state machines, or NFAs. It turns
out that every NFA can be written as a DFA, which has no need for
backtracking.

Except. Actually, two excepts. The normal algorithm for converting
an NFA to a DFA doesn't support grouping, which you'll need to
figure out which group matched. Wikipedia says there is an alternate,
slower algorithm which does support groups.

The second except is that regexps in Python, Perl, etc. are not
regular expressions. Some patterns, like r"([A-Z][a-z]+)\1", which
matches "WikiWiki", are not "regular grammars" under the definition
used in language theory. It's possible to use regexps to match
strings of prime length, for example.

So in the general case there is no solution. There are many
possible optimizations, but no general solution.

For your problem, which is a limited subset of the problem as
it involves only constant strings, then the solution is a prefix
tree, also called a trie. See http://en.wikipedia.org/wiki/Prefix_tree

John Machin in an earlier post suggested you search along these
lines when he said I would have thought the way to approach this would be a simple
character-by-character tree/trie-driven lookup. This would be worst case
O(n) where n is the length of the longest string in your list. There may
well be a Python-callable gadget for this on the net somewhere. Google
"Danny Yoo ahocorasick" for a Python-callable solution to a similar but
more complex problem.

For that matter I suggested it when I pointed you to pytst. The tst
means "ternary search tree" (some write it "ternary search trie") which
is a different implementation of the same idea.

Your posts read like you ignored those pointers because they didn't
fall into the category "implemente d with a regular expression". If
that's the case then no, there is no solution. You're letting a sense
of purity overwhelm practicality.

If you are really interested in this problem, try taking a CS
course titled something like "Automata Theory" or "Foundation s
of Computer Science". The one which covers DFAs, NFAs,
CFGs, Turing machines, etc. It's the CS class I enjoyed the most.

Andrew
da***@dalkescie ntific.com

[Mirco Wahab]

Thus spoke an*********@gma il.com (on 2006-06-20 01:39):

Hi, are you the A.Dalke from the Schulten group (VMD) as
listed here: http://www.ks.uiuc.edu/Overview/People/former.cgi

Replying to me Mirco Wahab wrote:

If you pull the strings into (?>( ... )) (atomic groups),
this would't happen.
Given that Python's re engine doesn't support this feature
it doesn't really help the original poster's problem.

Yeah, right. I misunderstood the problem
- where it was meant to be 'literally'
a problem of capture group id's. I took
it metaphorical, which meant to me
'problems by backtracking' (which was wrong).
Even if some future Python did support it, the limit
to 100 named groups is unaffected by backtracking.

Right for that one, what I had in mind was something
like the following:

# naive regex '\d+9'
# find some number only if it ends by 9
my $str="100990000 000000000000000 000000000000000 0";

print "non-atomic backtracks: $1\n" if $str =~ / ( \d+9 )/x;
print "atomic: matches $1\n" if $str =~ / ( (?>\d+)9 )/x;

Second line would not backtrack and not find the 9 behind \d+
because atomic grouping prevents that, so line 1 matches
10099 and line 2 nothing (but very fast, which is the point).

import re
re.compile("(.) "*100) Traceback (most recent call last):
...
...
AssertionError: sorry, but this version only supports 100 named groups

I tried:

my $re = '(\d+)\D' x 10000;
my $text = join ' ', 0..10000;

print $+ if $text =~ /$re/;

print "\n", $1001;

which prints:
9999
1000

Why is there a named group count
restriction in Python? Any reasons
one should know?

Regards & thanks

Mirco

[andrewdalke]

Mirco Wahab wrote:

Hi, are you the A.Dalke from the Schulten group (VMD) as
listed here: http://www.ks.uiuc.edu/Overview/People/former.cgi
Yes. But I left there nearly a decade ago.
# naive regex '\d+9'
# find some number only if it ends by 9
my $str="100990000 000000000000000 000000000000000 0";

print "non-atomic backtracks: $1\n" if $str =~ / ( \d+9 )/x;
print "atomic: matches $1\n" if $str =~ / ( (?>\d+)9 )/x;
What makes me less than enthusiastic about various new regexp
features is that they can be written other ways. For example,

import re
pat = re.compile("([0-8]*9)+")
pat.match("1009 900000000000000 000000000000000 000000") <_sre.SRE_Mat ch object at 0x590a0> _.group(0) '10099' pat = re.compile("([0-8]*9)+(?!\d)")
pat.match("1009 900000000000000 000000000000000 000000")

They are different ways to reach the same goal. Understanding
the alternatives requires some non-trivial understanding about
how regexp engines work. The diversity of solutions with no
clear preference of one over the other overly promotes
idiosyncratic patterns and requires that everyone reading the
regexps must understand all the special syntax contructions
even when a person's working vocabulary only uses a subset
of those.
Second line would not backtrack and not find the 9 behind \d+
because atomic grouping prevents that, so line 1 matches
10099 and line 2 nothing (but very fast, which is the point).
While my pattern is not as fast. It's linearly slower than yours
as it does the backtracking. (Unless the engine is very smart.)
That factor is not something I'm concerned with.

I can also get performance without backtracking (though there
is setup for backtracking) using
pat = re.compile("([0-8]*9)+([0-8]*)")
m = pat.match("1009 900000000000000 000000000000000 000000")
if m.group(2): print "does not end in a 9" ....
does not end in a 9
m = pat.match("1009 900000000000000 000000000000000 0000009a")
if m.group(2): print "does not end in a 9" .... Why is there a named group count
restriction in Python? Any reasons
one should know?

While not definite, I think it introduces an ambiguity with octal
escape codes. (*That's* something to omit in Python 3000!)
Here's the quote from perlre

There is no limit to the number of captured substrings that you
may
use. However Perl also uses \10, \11, etc. as aliases for \010,
\011,
etc. (Recall that 0 means octal, so \011 is the character at
number 9
in your coded character set; which would be the 10th character,
a hori-
zontal tab under ASCII.) Perl resolves this ambiguity by
interpreting
\10 as a backreference only if at least 10 left parentheses have
opened
before it. Likewise \11 is a backreference only if at least 11
left
parentheses have opened before it. And so on. \1 through \9
are
always interpreted as backreferences.

Python doesn't have "\10", "\11", etc. as aliases for "\010", "\011",
etc.
re.compile("\10 ") <_sre.SRE_Patte rn object at 0x575c0> pat = re.compile(r"\1 0") Traceback (most recent call last):
File "<stdin>", line 1, in ?
File
"/Library/Frameworks/Python.framewor k/Versions/2.4/lib/python2.4/sre.py",
line 180, in compile
return _compile(patter n, flags)
File
"/Library/Frameworks/Python.framewor k/Versions/2.4/lib/python2.4/sre.py",
line 227, in _compile
raise error, v # invalid expression
sre_constants.e rror: bogus escape: '\\10' pat = re.compile(r"\0 10")

so there is no ambiguity until reaching \100.
pat = re.compile(r"\1 00")
pat.match("@") <_sre.SRE_Mat ch object at 0x232560>

Most likely /F (who implemented the regex engine) decided
to refuse the temptation to guess the meaning, eg by
parens counting as Perl does.

Try this variation of your program to see how Perl changes
the meaning of "\100" based on the input string

for (my $i=98; $i<=103; $i++) {
my $re = '(\d+)\D' x $i . '\100';
my $text = join ' ', 0..$i;
$text .= " @";

print "Testing $i\n";
if ($text =~ /$re/) {
print " Number of matches: $+\n";
print " Last group: ${$i}\n";
} else {
print "No matches\n";
}
}

I get

Testing 98
Number of matches: 98
Last group: 98
Testing 99
Number of matches: 99
Last group: 99
Testing 100
No matches
Testing 101
No matches
Testing 102
No matches
Testing 103
No matches
Andrew
da***@dalkescie ntific.com