Finding if a string matches a pattern

I am looking at this as a parsing problem. The idea is that the parser function takes a string and determines if it is valid or not.

The string is valid if you can find it among the given patterns. That means you need an index of all the patterns. The index must be a full text index. Also it must match according to the word position. eg. it should short circuit if the first word of the input is not found among the first word of the patterns. It should take care of the any match ie %s in the pattern.

One solution is to put the patterns in an in memory database (eg. redis) and do a full text index on it. (this will not match according to word position) but you should be able to narrow down to the correct pattern by splitting the input into words and searching. The searches will be very fast because you have a small in memory database. Also note that you are looking for the closest match. One or more words will not match. The highest number of matches is the pattern you want.

An even better solution is to generate your own index in a dictionary format. Here is an example index for the four patterns you gave as a JavaScript object.

{
    "Hi": { "there": {"%s": null}},
    "What: {"a": {"lovely": {"day": {"today": null}}}},
    "Lovely": {"sunset": {"today": {"%s": {"isnt": {"it": null}}}}},
    "Will": {"you": {"be": {"meeting": {"%s": {"today": {"%s": null}}}}}}
}

This index is recursive descending according to the word postion. So search for the first word, if found search for the next within the object returned by the first and so on. Same words at a given level will have only one key. You should also match the any case. This should be blinding fast in memory.

My first thought would be to have the regexp engine take all the trouble of handling this. They're usually optimised to handle large amounts of text so it shouldn't be that much of a performance hassle. It's brute force but the performance seems to be okay. And you could split the input into pieces and have multiple processes handle them. Here's my moderately tested solution (in Python).

import random
import string
import re

def create_random_sentence():
    nwords = random.randint(4, 10)
    sentence = []
    for i in range(nwords):
        sentence.append("".join(random.choice(string.lowercase) for x in range(random.randint(3,10))))
    ret =  " ".join(sentence)
    print ret
    return ret



patterns = [ r"Hi there, [a-zA-Z]+.",
             r"What a lovely day today!",
             r"Lovely sunset today, [a-zA-Z]+, isn't it?",
             r"Will you be meeting [a-zA-Z]+ today, [a-zA-Z]+\?"]

for i in range(95):
    patterns.append(create_random_sentence())


monster_pattern = "|".join("(%s)"%x for x in patterns)

print monster_pattern
print "--------------"

monster_regexp = re.compile(monster_pattern)

inputs = ["Hi there, John.",
          "What a lovely day today!",
          "Lovely sunset today, John, isn't it?",
          "Will you be meeting Linda today, John?",
          "Goobledigoock"]*2000

for i in inputs:
    ret = monster_regexp.search(i)
    if ret:
        print ".",
    else:
        print "x",

I've created a hundred patterns. This is the maximum limit of the python regexp library. 4 of them are your actual examples and the rest are random sentences just to stress performance a little.

Then I combined them into a single regexp with 100 groups. (group1)|(group2)|(group3)|.... I'm guessing you'll have to sanitise the inputs for things that can have meanings in regular expressions (like ? etc.). That's the monster_regexp.

Testing one string against this tests it against 100 patterns in a single shot. There are methods that fetch out the exact group which was matched. I test 10000 strings 80% of which should match and 10% which will not. It short cirtcuits so if there's a success, it will be comparatively quick. Failures will have to run through the whole regexp so it will be slower. You can order things based on the frequency of input to get some more performance out of it.

I ran this on my machine and this is my timing.

python /tmp/scratch.py 0.13s user 0.00s system 97% cpu 0.136 total

which is not too bad.

However, to run a pattern against such a large regexp and fail will take longer so I changed the inputs to have lots of randomly generated strings that won't match and then tried. 10000 strings none of which match the monster_regexp and I got this.

python /tmp/scratch.py 3.76s user 0.01s system 99% cpu 3.779 total

Similar to Noufal's solution, but returns the matched pattern or None.

import re

patterns = [
    "Hi there, %s.",
    "What a lovely day today!",
    "Lovely sunset today, %s, isn't it",
    "Will you be meeting %s today, %s?"
]

def make_re_pattern(pattern):
    # characters like . ? etc. have special meaning in regular expressions.
    # Escape the string to avoid interpretting them as differently.
    # The re.escape function escapes even %, so replacing that with XXX to avoid that. 
    p = re.escape(pattern.replace("%s", "XXX"))
    return p.replace("XXX", "\w+")

# Join all the pattens into a single regular expression.
# Each pattern is enclosed in () to remember the match. 
# This will help us to find the matched pattern.
rx = re.compile("|".join("(" + make_re_pattern(p) + ")" for p in patterns))

def match(s):
    """Given an input strings, returns the matched pattern or None."""
    m = rx.match(s)
    if m:
        # Find the index of the matching group. 
        index = (i for i, group in enumerate(m.groups()) if group is not None).next()
        return patterns[index]

# Testing with couple of patterns
print match("Hi there, John.")
print match("Will you be meeting Linda today, John?")

Python solution. JS should be similar.

>>> re2.compile('^ABC(.*)E$').search('ABCDE') == None
False
>>> re2.compile('^ABC(.*)E$').search('ABCDDDDDDE') == None
False
>>> re2.compile('^ABC(.*)E$').search('ABX') == None
True
>>> 

The trick is to use ^ and $ to bound your pattern and making it a "template". Use (.*) or (.+) or whatever it is that you want to "search" for.

The main bottleneck for you, imho, will be iterating through a list of these patterns. Regex searches are computationally expensive.

If you want a "does any pattern match" result, build a massive OR based regex and let your regex engine handle the 'OR'ing for you.

Also, if you have only prefix patterns, check out the TRIE data structure.

This could be a job for sscanf, there is an implementation in js: http://phpjs.org/functions/sscanf/; the function being copied is this: http://php.net/manual/en/function.sscanf.php.

You should be able to use it without changing the prepared strings much, but I have doubts about the performances.

the problem isn't clear to me. Do you want to take the patterns and build regexes out of it? Most regex engines have a "quoted string" option. (\Q \E). So you could take the string and make it ^\QHi there,\E(?:.*)\Q.\E$ these will be regexes that match exactly the string you want outside your variables.

if you want to use a single regex to match just a single pattern, you can put them in grouped patterns to find out which one matched, but that will not give you EVERY match, just the first one.

if you use a proper parser (I've used PEG.js), it might be more maintainable though. So that's another option if you think you might get stuck in regex hell