Partial Regex matching in Python 3.2

Question

A regex answers a yes or no question - does the string match the pattern.

I want to separate the no's into two categories:

• invalid strings that are prefixes of valid strings
• invalid strings that are not prefixes of valid

Here's an example (regular expression 01+2):

• 012 is valid

• 12 is invalid; it is not a prefix of a valid string

• 01 is invalid; it is a prefix of a valid string: 012

Java can do this.

Can re do this? If not, is there a library that can make this distinction?

Answer 1

I second the recommendation of regex. The module is simply fantastic.

Here's an example of fuzzy matching with regex:

import regex

# traditional matching - three digits
r = '(?:\d\d\d)'
print regex.findall(r, '1xx22yy333zz')
## ['333']

# fuzzy matching - three digits, allow at most 2 deletions
r = '(?:\d\d\d){d<3}'
print regex.findall(r, '1xx22yy333zz')
## ['1', '22', '333']

The {d<3} part basically says "if we add one or two chars to that, that would be a match" - the same as point 3. in your question.

See http://pypi.python.org/pypi/regex for more info (look for 'Approximate "fuzzy" matching').

Answer 2

I can’t tell what you really want. Are you trying to understand incremental matches?

Perhaps you need to learn to use anchors properly. Just as you should never use the Java misnamed and deceptive matches method instead of its find method, you should probably eschew Python’s match method in favor of search, and for precisely the same reason.

Another possibility is to rewrite your pattern with optional portions that you can then inspect the success of.

Or perhaps you should look into the fuzzy matching support in Matthew Barnett’s replacement regex library, which you really should be using instead of the crufty old re.

I can’t tell what you’re realy asking, because you haven’t given examples of desired input and output.

EDIT

Perhaps you need nothing more complex than (?=.*(?:ab|bc)).*a?b?c?, or spaced out:

 (?x)
 (?= .* (?: ab | bc) )
 .*
 a? b? c?

If you put a, b, and c into recursible subgroups, you wouldn’t even have to repeat yourself.

Answer 3

Correct me if I am wrong, I believe the original question was: for some regex and input string if the input string is a possible match (ie. adding more characters to the end of the string could make it a match).

Thus fuzzy matching isn't an answer because:

rgx = regex.compile('(abcdef){d<5}')

str = 'bcd'

will be a match as well

Boost C++ library (Also for Java/Javascript?) provides such an option: http://www.boost.org/doc/libs/1_31_0/libs/regex/doc/partial_matches.html

So does anyone know what is the best way to achieve this in Python?