3
\$\begingroup\$

This is a similar question to this, but I am looking for the set of all possible values that will match a regular expression pattern.

To avoid an infinite set of possible values, I am willing to restrict the regular expression pattern to a subset of the regular expression language.

Here's the approach I took (Python code):

def generate_possible_strings(pattern):
    '''
    input: 'K0[2468]'
    output: ['K02', 'K04', 'K06', 'K08']

    generates a list of possible strings that would match pattern
    ie, any value X such that re.search(pattern, X) is a match
    '''
    query = re.compile(pattern, re.IGNORECASE)
    fill_in = string.uppercase + string.digits + '_'

    # Build a re for a language subset that is supported by reverse_search
    bracket = r'\[[^\]]*\]' #finds [A-Z], [0-5], [02468]
    symbol = r'\\.' #finds \w, \d
    expression = '|'.join((bracket,symbol)) #search query

    tokens = re.split(expression, pattern)
    for c in product(fill_in, repeat=len(tokens)-1):
        candidate = ''.join(roundrobin(tokens, c)) #roundrobin recipe from itertools documentation
        if query.match(candidate):
            yield candidate

Supported subset of regular expressions language

  • Supports [] set of characters ([A-Z], [0-5], etc)
  • Supports escaped special characters (\w, \d, \D, etc)

Basically what this does is locate all parts of a regular expression that could match a single character ([A-Z] or [0-5] or [02468] or \w or \d), then for all of the valid replacement characters A-Z0-9_ test to see if the replacement matches the regular expression.

This algorithm is slow for regular expressions with many fields or if fill_in is not restricted to just A-Z0-9_, but at least it guarantees finding every possible string that will match a regular expression in finite time (if the solution set is finite).

Is there a faster approach to solving this problem, or an approach that supports a larger percentage of the standard regular expression language?

\$\endgroup\$

migrated from stackoverflow.com Mar 10 '14 at 20:27

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ Are you looking to exhaustively test all possible inputs to this regex? That could get quickly out of hand, and some regex's could literally have an infinite number of possible inputs (you'll run out of memory or time before you test them all). How about some representative sample that covers all the things you want to test? It might even be possible to automatically generate such coverage (your intent, I believe). \$\endgroup\$ – Phil Perry Mar 10 '14 at 18:08
  • \$\begingroup\$ In line with comment from @PhilPerry - if your regex uses any "closure" type operations (e.g. + meaning one-or-more or * for zero-or-more), the set of possible matches will not be finite. \$\endgroup\$ – twalberg Mar 10 '14 at 18:10
  • \$\begingroup\$ Using a generator function, itertools.product, and itertools.roundrobin resolves the infinite memory problem, but you're right that this could require infinite time. I have do not need to support closure operators * or +. @PhilPerry I need the full solution set. A sample will not satisfy the problem I am solving. \$\endgroup\$ – IceArdor Mar 10 '14 at 18:12
  • \$\begingroup\$ This is quite a challenge. Even short regexes with no closure operations can produce more strings than you could possibly store. For instance, "\d\d\d\d\d\d\d\d\d\d\d\d" matches a trillion different strings. \$\endgroup\$ – Kevin Mar 10 '14 at 18:21
  • 1
    \$\begingroup\$ Why do you call query.match(candidate)? Does your algorithm generate candidates that don't match? \$\endgroup\$ – Janne Karila Mar 11 '14 at 6:48
4
\$\begingroup\$

A major inefficiency in your solution is that you try every fill_in character as a replacement for any character class in the pattern. Instead, you could use the character class to select matching characters from fill_in and only loop over those.

>>> pattern = 'K0[2468]'
>>> re.findall(expression, pattern)
['[2468]']
>>> re.findall('[2468]', fill_in)
['2', '4', '6', '8']

For a more complete existing solution, you may want to look into these:

\$\endgroup\$
  • \$\begingroup\$ Thank you! This helps a lot, particularly for cases like '\d\d\d', where only 1000 of 50653 candidates are matches (given fill_in is [A-Z0-9_]) \$\endgroup\$ – IceArdor Mar 12 '14 at 16:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.