0

I have some short phrases that I want to match on. I used a regex as follows:

(^|)(piston|piston ring)( |$)

Using the above, regex.match("piston ring") matches on "piston". If I change the regex such that the longer phrase "piston ring" comes first then it work as expected.

I was surprised by this behavior as I was assuming that the greedy nature of regex would try to match the longest string "for free."

What am I missing? Can somebody explain this? Thanks!

stema
  • 90,351
  • 20
  • 107
  • 135
ccgillett
  • 4,511
  • 4
  • 21
  • 14
  • 1
    Regex greediness only comes into effect when you're using the `*` and `+` operators. The `|` uses the first match from left to right. – resmon6 Feb 21 '12 at 20:13

4 Answers4

5

When using alternation (|) in regular expressions, each option is attempted in order from left to right until a match can be found. So in your example since a match can be made with piston, piston ring will never be attempted.

A better way to write this regex would be something like this:

(^|)(piston( ring)?)( |$)

This will attempt to match 'piston', and then immediately attempt to match ' ring', with the ? making it optional. Alternatively just make sure your longer options occur at the beginning of the alternation.

You may also want to consider using a word boundary, \b, instead of (^|) and ( |$).

Andrew Clark
  • 202,379
  • 35
  • 273
  • 306
  • I sorted my list in reverse order by length to get good results. I also took your advice and used \b for clarity. Thanks for the help! – ccgillett Feb 21 '12 at 20:36
4

from http://www.regular-expressions.info/alternation.html (first Google result):

the regex engine is eager. It will stop searching as soon as it finds a valid match. The consequence is that in certain situations, the order of the alternatives matters

one exception:

the POSIX standard mandates that the longest match be returned, regardless if the regex engine is implemented using an NFA or DFA algorithm.

possible solutions:

  • piston( ring)?
  • (piston ring|piston) (put the longest before)
Ruggero Turra
  • 16,929
  • 16
  • 85
  • 141
  • 1
    This is also good to read to understand why repetition expressions are greedy. http://www.regular-expressions.info/repeat.html – resmon6 Feb 21 '12 at 20:19
2

Thats the behaviour of Alternations. It tries to match the first alternative, that is "piston" if it is successful it is done.

That means it will not try all alternatives, it will finish with the first that matches.

You can find more details here on regular-expressions.info

What could also be interesting for you are word boundaries \b. I think what you are looking for is

\bpiston(?: ring)?\b
stema
  • 90,351
  • 20
  • 107
  • 135
0
Edit2: It wasn't clear if your test data 
contained pipes or not. I saw the pipes in 
the regex and assumed you are searching 
for pipe delim. Oh well.. not sure if below
helps.

Using regex to match text that's pipe delimited will need more alternations to pick up the beginning and ending columns.

What about another approach?

text='start piston|xxx|piston ring|xxx|piston cast|xxx|piston|xxx|stock piston|piston end'
j=re.split(r'\|',text)

k = [ x for x in j if x.find('piston') >= 0 ]
['start piston', 'piston ring', 'piston cast', 'piston', 'stock piston', 'piston end']

k = [ x for x in j if x.startswith('piston')  ]
['piston ring', 'piston cast', 'piston', 'piston end']

k = [ x for x in j if x == 'piston' ]
['piston']

j=re.split(r'\|',text)
if 'piston ring' in j: 
    print True
> True

Edit: To clarify - take this example:

text2='piston1|xxx|spiston2|xxx|piston ring|xxx|piston3'

I add '.' to match anything to show the items matched

re.findall('piston.',text2)
['piston1', 'piston2', 'piston ', 'piston3']

To make it more accurate, you will need to use look-behind assertion. This guarantees you match '|piston' but doesn't include the pipe in the result

re.findall('(?<=\|)piston.',text2)
['piston ', 'piston3']

Limit matching from greedy to first matching character .*?< stop char > Add grouping parens to exclude the pipe. The match .*? is smart enough to detect if inside a group and ignores the paren and uses the next character as the stop matching sentinel. This seems to work, but it ignores the last column.

re.findall('(?<=\|)(piston.*?)\|',text2)
['piston ring']

When you add grouping you can now just specify starts with an escaped pipe

re.findall('\|(piston.*?)\|',text2)
['piston ring']

To search the last column as well, add this non-grouping match (?:\||$) - which means match on pipe (needs to be escaped) or (|) the end ($) of string. The non-grouping match (?:x1|x2) doesn't get included in the result. An added bonus it gets optimized.

re.findall('\|(piston.*?)(?:\||$)',text2)
['piston ring', 'piston3']

Finally, to fix for the beginning of the string, add another alteration much like the previous one for end string match

re.findall('(?:\||^)(piston.*?)(?:\||$)',text2)
['piston1', 'piston ring', 'piston3']

Hope it helps. :)

Rich
  • 183
  • 5