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

[Paddy]

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]. 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

A start would be:
regexp = "^(" + "|".join(sorted (ls, reverse=True)) + ")"
But the above does not work if you have special characters in your
strings.

You say you want something that is optimised. What have have you tried?
- Pad.

[Kay Schluehr]

Paddy 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]. 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
A start would be:
regexp = "^(" + "|".join(sorted (ls, reverse=True)) + ")"
But the above does not work if you have special characters in your
strings.

For special characters there might be a workaround using escapes. This
is indeed important, but I do think one should split the problem into
separate parts.
You say you want something that is optimised. What have have you tried?

Sorting the list and checking for successor inclusions. Say you have ls
= ['x','a', 'aa', 'aab' ,'ab']

This can be mapped to:

'x|a(?:(?:ab)?| b?|a?)'

or to:

'^(x|ab|aab|aa| a)'

with reverse sorting as in your proposal.The naive solution is easy to
generate but I'm sceptical about its cost effectiveness. On the other
hand I do not want to investigate this matter if somebody else already
did it thoroughly.

Regards,
Kay

[John Machin]

On 19/06/2006 6:30 AM, Paddy 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]. There might
be relations between those strings: s_k.startswith( s_1) -> True or
s_k.endswith(s_ 1) -> True.
Kay, what is the relevance of one string being a suffix of another? I
don't see how that could affect the outcome.

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?
Optimised with respect to what? speed? ease of construction?

I presume that you will ensure that the members of the list are unique.

Note that the Python regex engine will consider each candidate in
Paddy's solution left to right until it gets a match or reaches the end
(that's why the reverse sort is needed to get longest possible match).
This is worst-case O(N) where N is the total of the lengths of all the
strings in your list.

As far as I can see, this is the only basic solution (modulo one or two
twiddles -- see below) using Python's re.

You could possibly consider producing "zzz|foo(?:bar) ?|aaa" instead of
"zzz|foobar|foo |aaa" -- but whether that would run sufficiently faster
to offset the cost of construction is anybody's guess.

How many strings in your list? Average/maximum length? Likelihood of
ls[i].startswith(ls[j]) == True? unicode or str?

Your requirements are rather constrained: "sx.match(s ) yields a
SRE_Match object" ... why do you need this? Surely all you need is
matched_len (which may be zero) such that s[:matched_len] is the matched
prefix.

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.

A cheap hack using Python's re: divide the problem according to first
character:

prefix_dict_mat ch = {
'a': re.compile('alp aca|alligator') .match,
'f': re.compile('foo bar|foo').match ,
'z': re.compile('zoo |zebra').match,
}
if s and s[0] in prefix_dict_mat ch:
match_obj = prefix_dict_mat ch[s[0]](s)
else:
match_obj = None

Regards,
Kay

A start would be:
regexp = "^(" + "|".join(sorted (ls, reverse=True)) + ")"
But the above does not work if you have special characters in your
strings.

Paddy, fixing that problem, and "optimising " by removing the redundant
^() metacharacters:

regexp = "|".join(map(re .escape, sorted(ls, reverse=True)))
Hoping some of this helps,
Regards,
John

[Mirco Wahab]

Thus spoke Kay Schluehr (on 2006-06-18 19:07):

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.

With some ideas from Kay and Paddy, it tried to get
along with Python in doing this.

If its allowed to spread the individual strings
into alterations, the following would imho do:
#!/usr/bin/python
# -*- coding: iso-8859-15 -*-
text = r'this is a text containing aaaöüöaaaµaaa and more';
lstr = [
'a',
'aa',
'aaaaa',
'aaaöüöaaaµaaa' ,
'aaaaaaaaaaaaaa ab'
]

import re
pat = re.compile( \
'(' + \
'|'.join(sorted (lstr,lambda a,b: len(b)-len(a))) + \
')', re.VERBOSE);

hits = sorted( pat.findall(tex t), lambda a,b: len(b)-len(a) )
print 'Longest: ', hits[0]

This will print 'aaaöüöaaaµaaa' from the text
and won't complain about specuial characters used.

in Perl, you could build up the regex
by dynamic evaluation (??{..}), but I
didn't manage to get this working in Python,
so here is (in Perl) how I thougt it would work:

my $text = "this is a text containing aaaöüöaaaµaaa and more";
my @lstr = (
'a',
'aa',
'aaaaa',
'aaaöüöaaaµaaa' ,
'aaaaaaaaaaaaaa ab',
);

my $re = qr{
(??{
join '|',
map { quotemeta }
sort{ length $b <=> length $a }
@lstr
})
}x;

$_ = $text;
print "Longest: ", (my $hit) = reverse sort /$re/g;
Maybe the experts can bring some light to it.

Regards

Mirco

[Paddy]

Kay Schluehr wrote:
<SNIP>

with reverse sorting as in your proposal.The naive solution is easy to
generate but I'm sceptical about its cost effectiveness. On the other
hand I do not want to investigate this matter if somebody else already
did it thoroughly.

Regards,
Kay

Hi Kay,
The only way to know if something is optimised enough, is for you to
test it in your application. If you haven't finished your application,
then don't sweat it. take a note of your options, stick one in, then
get the application finished.
Its only when its finished that you can really say if further
optimisations are necessary, and you would have to profile the complete
prog to see where it's spending its time.

I usually find myself using string methods where possible, then regular
expressions only for things that string methods cannot do. When I
finish my script I usually find that Pythons speed is adequate for most
of my text processing tasks, or if speed IS an issue, then i needed to
profile the completed application anyway.

- Pad.

[Kay Schluehr]

Mirco,

with "special characters" I mentioned control characters of regular
expressions i.e. one of ".^$()?[]{}\|+*" but not non ascii-127
characters.

For a workaround you simply have to "mangle" those using an escape
control character:

REGEXCHAR = ".^$()?[]{}\\|+*"
def mangle(s):
pattern = []
for c in s:
if c in REGEXCHAR:
pattern.append( "\\")
pattern.append( c)
return "".join(pattern )

Regards,
Kay

[John Machin]

On 19/06/2006 7:06 PM, Kay Schluehr wrote:

Mirco,

with "special characters" I mentioned control characters of regular
expressions i.e. one of ".^$()?[]{}\|+*" but not non ascii-127
characters.

For a workaround you simply have to "mangle" those using an escape
control character:

REGEXCHAR = ".^$()?[]{}\\|+*"
def mangle(s):
pattern = []
for c in s:
if c in REGEXCHAR:
pattern.append( "\\")
pattern.append( c)
return "".join(pattern )

What's wrong with re.escape()?
Have you not read (a) my response to Paddy's first posting (b) the manual?

[gry]

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]. 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.
In a very similar case I used a simple tree of dictionaries, one node
per letter, to represent the strings.
This naturally collapses cases like ['a','aa','aaa']. Then a recursive
function finds
the desired prefix. This was WAY faster than the "re" module for large
n (tradeoff point for me was n~1000). It requires a bit more coding,
but I think it is the natural data structure for this problem.

As others have suggested, you should first try the most naive
implementation before making a hard optimization problem out of this.
Is there a Python module able to create an optimized regex rx from ls
for the given constraints?

Regards,
Kay

[andrewdalke]

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? When you have constant
strings there are other solutions. For example, this uses Nicolas
Lehuen's
pytst module from http://nicolas.lehuen.com/index.php/Pytst

import tst
tree = tst.TST()
tree["aa"] = (1, "String with 'aa'")
tree["aahhh"] = (2, "At the doctor's")
tree["a"] = (3, "indefinite article")
tree.scan("This is a bunch of text. Have you seen an aardvark?", .... tst.TupleListAc tion())
[('This is ', -8, None), ('a', 1, (3, 'indefinite article')), (' bunch
of text. H', -18, None), ('a', 1, (3, 'indefinite article')), ('ve you
seen ', -12, None), ('a', 1, (3, 'indefinite article')), ('n ', -2,
None), ('aa', 2, (1, "String with 'aa'")), ('rdv', -3, None), ('a', 1,
(3, 'indefinite article')), ('rk?', -3, None)]

Each returned tuple has three elements:
For a substring which is not a match these are:
- the unmatched substring
- the negative length of the substring
- None

For a substring which matches:
- the matched substring
- the positive length of the substring
- the value of the match in the TST (the tree)

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.

Andrew
da***@dalkescie ntific.com