[Python] What is the fastest way in Python to find if a string matches any terms in a list of...

I am trying to find a fast way in Python to check if a list of terms can be matched against strings ranging in size from 50 to 50,000 characters.

A term can be:

• A word, eg. 'apple'
• A phrase, eg. 'cherry pie'
• Boolean ANDing of words and phrases, eg. 'sweet pie AND savoury pie AND meringue'

A match is where a word or phrase exists around word boundaries, so:

match(term='apple', string='An apple a day.') # True
match(term='berry pie', string='A delicious berry pie.') # True
match(term='berry pie', string='A delicious blueberry pie.') # False


I currently have about 40 terms, most of them are simple words. The number of terms will increase over time, but I wouldn't expect it to get beyond 400.

I'm not interested in which term(s) a string matches, or where in the string it matches, I just need a true/false value for a match against each string - it is much more likely that no terms will match the string, so for the 1 in 500 where it does match, I can store the string for further processing.

Speed is the most important criteria, and I'd like to leverage the existing code of those smarter than me rather than trying to implement a white-paper.

So far the speediest solution I've come up with is:

def data():
return [
"The apple is the pomaceous fruit of the apple tree, species Malus domestica in the rose family (Rosaceae).",
"This resulted in early armies adopting the style of hunter-foraging.",
"Beef pie fillings are popular in Australia. Chicken pie fillings are too."
]

def boolean_and(terms):
return '(%s)' % (''.join(['(?=.*\\b%s\\b)' % (term) for term in terms]))

def run():
words_and_phrases = ['apple', 'cherry pie']
booleans = [boolean_and(terms) for terms in [['sweet pie', 'savoury pie', 'meringue'], ['chicken pie', 'beef pie']]]
regex = re.compile(r'(?i)(\b(%s)\b|%s)' % ('|'.join(words_and_phrases), '|'.join(booleans)))
matched_data = list()
for d in data():
if regex.search(d):
matched_data.append(d)


The regex winds up as:

(?i)(\b(apple|cherry pie)\b|((?=.*\bsweet pie\b)(?=.*\bsavoury pie\b)(?=.*\bmeringue\b))|((?=.*\bchicken pie\b)(?=.*\bbeef pie\b)))


So all the terms are ORed together, case is ignored, the words/phrases are wrapped in \b for word boundaries, the boolean ANDs use lookaheads so that all the terms are matched, but they do not have to match in a particular order.

Timeit results:

print timeit.Timer('run()', 'from __main__ import run').timeit(number=10000)
1.41534304619


Without the lookaheads (ie. the boolean ANDs) this is really quick, but once they're added the speed slows down considerably.

Does anybody have ideas on how this could be improved? Is there a way to optimise the lookahead, or maybe an entirely different approach? I don't think stemming will work, as it tends to be a bit greedy with what it matches.

Continue reading...