How to get the "longest possible" match with Python's RE module?

[Licheng Fang]

Basically, the problem is this:

>>p = re.compile("do| dolittle")
p.match("doli ttle").group()

'do'

Python's NFA regexp engine trys only the first option, and happily
rests on that. There's another example:

>>p = re.compile("one (self)?(selfsuf ficient)?")
p.match("ones elfsufficient") .group()

'oneself'

The Python regular expression engine doesn't exaust all the
possibilities, but in my application I hope to get the longest possible
match, starting from a given point.

Is there a way to do this in Python?

[MonkeeSage]

Licheng Fang wrote:

Basically, the problem is this:

>p = re.compile("do| dolittle")
p.match("dolit tle").group()

'do'

>From what I understand, this isn't python specific, it is the expected

behavior of that pattern in any implementation. You are using
alternation, which means "either, or", and you have the shorter
subexpression first, so the condition is satisfied by just 'do' and the
matching terminates.

There's another example:

>p = re.compile("one (self)?(selfsuf ficient)?")
p.match("onese lfsufficient"). group()

'oneself'

Again, I don't think this has anything to do with python. You pattern
basically means "match 'one' whether it is followed by 'self' or not,
and whether it is followed by 'selfsufficient ' or not". For this
particular example, you'd want something like
"one(self)?(suf ficient)?".

I think you could construct a pattern that would do what you want in
python without any problem. If you post a (short) example of your data,
I'm sure someone could help you with it.

Regards,
Jordan

[kondal]

Licheng Fang wrote:

Basically, the problem is this:

>p = re.compile("do| dolittle")
p.match("dolit tle").group()

'do'

Python's NFA regexp engine trys only the first option, and happily
rests on that. There's another example:

>p = re.compile("one (self)?(selfsuf ficient)?")
p.match("onese lfsufficient"). group()

'oneself'

The Python regular expression engine doesn't exaust all the
possibilities, but in my application I hope to get the longest possible
match, starting from a given point.

Is there a way to do this in Python?

This is the way the regexp works python doesn't has anything to do with
it. It starts parsing the data with the pattern given. It returns the
matched string acording the pattern and doesn't go back to find the
other combinations.

So to get all the combinations you would probably require to give
different patterns each time.

[Licheng Fang]

MonkeeSage wrote:

Licheng Fang wrote:

Basically, the problem is this:

>>p = re.compile("do| dolittle")
>>p.match("doli ttle").group()

'do'

From what I understand, this isn't python specific, it is the expected

behavior of that pattern in any implementation. You are using
alternation, which means "either, or", and you have the shorter
subexpression first, so the condition is satisfied by just 'do' and the
matching terminates.

There's another example:

>>p = re.compile("one (self)?(selfsuf ficient)?")
>>p.match("ones elfsufficient") .group()

'oneself'

Again, I don't think this has anything to do with python. You pattern
basically means "match 'one' whether it is followed by 'self' or not,
and whether it is followed by 'selfsufficient ' or not". For this
particular example, you'd want something like
"one(self)?(suf ficient)?".

I think you could construct a pattern that would do what you want in
python without any problem. If you post a (short) example of your data,
I'm sure someone could help you with it.

Regards,
Jordan

Hi, according to these regexp engine discussions, it's NOT a behavior
true to any implementation.

http://www.softec.st/en/OpenSource/D...onEngines.html
http://www.softec.st/en/OpenSource/D...onEngines.html

Python's NFA engine reads along the input string, matching it to the
pattern, and backtracking when needed. By contrast a DFA engine, to my
understanding, constructs a DFA and uses it to munch as many characters
as possible. Maybe it's like this:

Pattern: one(self)?(self sufficient)?

PYTHON'S NFA ENGINE:

one self, none selfsufficient, none
(start)------->((1))------------>((2))----------------------->((3))

DFA ENGINE:

one self
(start)------->((123))------------>((23))
|
|
| selfsufficient
--------------->((3))

I want to know if there is some way to make Python RE behave like grep
does, or do I have to change to another engine?

[Paddy]

>
I want to know if there is some way to make Python RE behave like grep
does, or do I have to change to another engine?

Maybe if you posted a (tested) grep example and data, that does as you
want, the group could better understand what you are asking for?

- Paddy.

[Tim Peters]

[Licheng Fang]

...
I want to know if there is some way to make Python RE behave like grep
does,

Not in general, no. The matching strategies couldn't be more
different, and that's both deep and intentional. See Friedl's book
for details:

http://regex.info/

or do I have to change to another engine?

Yes, if POSIX regexp semantics are what you require. Several years
ago there was an extension module for Python supplying POSIX
semantics, but I couldn't find anything current just now in a minute
of searching. You may be more motivated to search longer ;-)

[MonkeeSage]

Licheng Fang wrote:

Hi, according to these regexp engine discussions, it's NOT a behavior
true to any implementation.
[snip]

Well, I just double-checked in ruby (oniguruma regexp engine):

r = Regexp.new("do| dolittle")
puts r.match("dolitt le")[0]
# do

r = Regexp.new("one (self)?(suffici ent)?")
puts r.match("onesel fsufficient")[0]
# oneself

And perl:

if ("doolittle" =~
/(do|dolittle)/) {
print "$1\n";
# do
}

if ("oneselfsuffic ient" =~
/(one(self)?(sel fsufficient)?)/) {
print "$1\n";
# oneself
}

And Javascript (whatever regexp engine Spidermonkey uses):

var r = new RegExp(/do|dolittle/);
alert("dolittle ".match(r)[0]);

var r = new RegExp(/one(self)?(self sufficient)?/);
alert("oneselfs ufficient".matc h(r)[0]);

So, it seems they are all broken, or python is correct as well.

Regards,
Jordan

[MonkeeSage]

MonkeeSage wrote:

So, it seems they are all broken, or python is correct as well.

Aha, sorry about that Licheng (re: Tim's post). I guess "broken"
depends on if you are expecting perl-compatible behavior or otherwise.
I have my own scripts I use to do (f)grep and sed-like operations, so I
almost never use those programs and forgot about the different pattern
semantics (part of the reason I made my own scripts).

Regards,
Jordan

[Licheng Fang]

Oh, please do have a look at the second link I've posted. There's a
table comparing the regexp engines. The engines you've tested probably
all use an NFA implementation.

MonkeeSage wrote:

Licheng Fang wrote:

Hi, according to these regexp engine discussions, it's NOT a behavior
true to any implementation.
[snip]

Well, I just double-checked in ruby (oniguruma regexp engine):

r = Regexp.new("do| dolittle")
puts r.match("dolitt le")[0]
# do

r = Regexp.new("one (self)?(suffici ent)?")
puts r.match("onesel fsufficient")[0]
# oneself

And perl:

if ("doolittle" =~
/(do|dolittle)/) {
print "$1\n";
# do
}

if ("oneselfsuffic ient" =~
/(one(self)?(sel fsufficient)?)/) {
print "$1\n";
# oneself
}

And Javascript (whatever regexp engine Spidermonkey uses):

var r = new RegExp(/do|dolittle/);
alert("dolittle ".match(r)[0]);

var r = new RegExp(/one(self)?(self sufficient)?/);
alert("oneselfs ufficient".matc h(r)[0]);

So, it seems they are all broken, or python is correct as well.

Regards,
Jordan

[MonkeeSage]

Licheng Fang wrote:

Oh, please do have a look at the second link I've posted. There's a
table comparing the regexp engines. The engines you've tested probably
all use an NFA implementation.

Sorry! *blush* I admit I skipped over your links. I'll have a look now.

BTW, just an idea that may or may not work. What about finding all
matches that meet the absolute baseline pattern, then taking the
longest of them...somethin g like this mabye:

def matcher(strings , pattern):
out = ''
reg = re.compile(patt ern)
for string in strings:
match = reg.match(strin g).group()
if (len(match) >= len(out)): # should this use or >= ?
out = match
return out # empty is no matches, else longest match

p = ['dodad', 'dolittle', 'dodaday']
print matcher(p, r'do.*')
# dolittle

Just a thought...

Regards,
Jordan