Search for a string in a text

Question

After answering a question here on SO about finding a city in a user-supplied question, I started thinking about the best way to search for a string in a text when you have a limited data-set as this one.

in and find matches against a substring, which is not wanted. Reqular expressions using "word boundaries" works but are quite slow. The "punctuation" approach seems to be a candidate, but there is a lot of punctuation characters that can appear both in question as well as some in the name of a city (i.e. a period in "St. Louis").

Regexps are probably the best general-purpose solution, but I'm curious if this can be solved using some other technique.

The task is to:

Find a city in the US in a user supplied text in the English language regardless of case.

My code heavily inspired by http://www.python.org/doc/essays/list2str/

#!/usr/bin/env python

import time
import re

def timing(f, n):
    print f.__name__,
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(); f(); f(); f(); f(); f(); f(); f(); f(); f()
    t2 = time.clock()
    print round(t2-t1, 6)


def f0():
    '''broken since it finds sub-strings, e.g.
    city "Erie" is found in "series"'''
    Q = question.upper()
    for c in cities:
        c = c.upper()
        if c in Q:
            pass

def f1():
    '''slow, but working'''
    for c in cities:
        re.search('\\b%s\\b' % c, question, re.IGNORECASE)

def f2():
    '''broken, same problem as f0()'''
    Q = question.upper()
    for c in cities:
        c = c.upper()
        if Q.find(c) > 0:
            pass

def f3():
    '''remove all punctuation, and then search for " str " '''
    Q = question.upper()
    punct = ['.', ',', '(', ')', '"', '\n', '  ', '   ', '    ']
    for p in punct:
        Q = Q.replace(p, ' ')

    for c in cities:
        c = ' ' + c.upper() + ' '
        for p in punct:
            c = c.replace(p, ' ')
        if c in Q:
            pass

with open('cities') as fd:
    cities = [line.strip() for line in fd]

with open('question') as fd:
    question = fd.readlines()[0]

testfuncs = f0, f1, f2, f3

for f in testfuncs:
    print f
    timing(f, 20)

On my old dodgy laptop, I get the following results

<function f0 at 0xb7730bc4>
f0 0.14
<function f1 at 0xb7730f7c>
f1 10.4
<function f2 at 0xb7730f44>
f2 0.15
<function f3 at 0xb7738684>
f3 0.61

If someone would like to have a go on my testdata, it can be found here

Answer 1

Interesting, Prebuild regex for all cities (ie. one regex for all cities) seems to be winning at performance. I used the same test case and here is the result.

#!/usr/bin/env python

import time
import re

def timing(f, n):
    print f.__name__,
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(); f(); f(); f(); f(); f(); f(); f(); f(); f()
    t2 = time.clock()
    print round(t2-t1, 6)


def f0():
    '''broken since it finds sub-strings, e.g.
    city "Erie" is found in "series"'''
    Q = question.upper()
    for c in cities:
        c = c.upper()
        if c in Q:
            pass

def f1():
    '''slow, but working'''
    for c in cities:
        re.search('\\b%s\\b' % c, question, re.IGNORECASE)

def f11():
    '''Same as f1(). Compiled and searched at runtime.'''
    for c in cities:
        re.compile('\\b%s\\b' % c, re.IGNORECASE).search(question)

def f12():
    '''Building single regex for all cities, and searching using it.'''
    regex ="(%s)" % "|".join(re.escape(c) for c in cities)
    re.search(regex, question, re.IGNORECASE)

def f13():
    '''Using prebuild single regex for all cities to search.'''
    re.search(all_cities_regex, question, re.IGNORECASE)

def f14():
    '''Building and compiling single regex for all cities, and searching using it.'''    
    regex = re.compile("(%s)" % "|".join(re.escape(c) for c in cities), re.IGNORECASE)
    regex.search(question)

def f15():
    '''Searching using prebuild, precompiled regex.'''    
    precompiled_all.search(question)

def f2():
    '''broken, same problem as f0()'''
    Q = question.upper()
    for c in cities:
        c = c.upper()
        if Q.find(c) > 0:
            pass

def f3():
    '''remove all punctuation, and then search for " str " '''
    Q = question.upper()
    punct = ['.', ',', '(', ')', '"', '\n', '  ', '   ', '    ']
    for p in punct:
        Q = Q.replace(p, ' ')

    for c in cities:
        c = ' ' + c.upper() + ' '
        for p in punct:
            c = c.replace(p, ' ')
        if c in Q:
            pass

with open('cities') as fd:
    cities = [line.strip() for line in fd]

with open('question') as fd:
    question = fd.readlines()[0]

all_cities_regex ="(%s)" % "|".join(re.escape(c) for c in cities)
precompiled_all = re.compile("(%s)" % "|".join(re.escape(c) for c in cities), re.IGNORECASE)

testfuncs = f0, f1, f11, f12, f13, f14, f15, f2, f3

for f in testfuncs:
    print f
    timing(f, 20)

Note: I have added 5 more functions f11 to f15.

Here's the output (as seen in my lappy):

<function f0 at 0x259c938>
f0 0.06
<function f1 at 0x259c9b0>
f1 3.81
<function f11 at 0x259ca28>
f11 3.87
<function f12 at 0x259caa0>
f12 0.35
<function f13 at 0x259cb18>
f13 0.2
<function f14 at 0x259cb90>
f14 0.34
<function f15 at 0x259cc08>
f15 0.2
<function f2 at 0x259cc80>
f2 0.06
<function f3 at 0x259ccf8>
f3 0.18

Prebuild (f13) regex for all cities (ie. one regex for all cities) is good at performance. Also notice that, precompiling such prebuild regex (f15) didn't add to the performance.

Based on the comments above by @trutheality and @Thomas.

Answer 2

An upgrowth of your "punctuation" approach:

#!/usr/bin/env python

import time
import re

def timing(f, n):
    print f.__name__,
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(); f(); f(); f(); f(); f(); f(); f(); f(); f()
    t2 = time.clock()
    print round(t2-t1, 6)


def f0():
    '''broken since it finds sub-strings, e.g.
    city "Erie" is found in "series"'''
    Q = question.upper()
    for c in cities:
        c = c.upper()
        if c in Q:
            pass

def f1():
    '''slow, but working'''
    for c in cities:
        re.search('\\b%s\\b' % c, question, re.IGNORECASE)

def f2():
    '''broken, same problem as f0()'''
    Q = question.upper()
    for c in cities:
        c = c.upper()
        if Q.find(c) > 0:
            pass

def f3():
    '''remove all punctuation, and then search for " str " '''
    Q = question.upper()
    punct = ['.', ',', '(', ')', '"', '\n', '  ', '   ', '    ']
    for p in punct:
        Q = Q.replace(p, ' ')

    for c in cities:
        c = ' ' + c.upper() + ' '
        for p in punct:
            c = c.replace(p, ' ')
        if c in Q:
            pass

def f4():
    '''Single regex which is also broken'''
    regex ="(%s)" % "|".join(re.escape(c) for c in cities)
    re.search(regex, question, re.IGNORECASE)

def f5():
    '''Upgrowth of 'punctiation' approach'''
    r = re.compile('\W')
    #Additional space is for the case 
    #when city is at the end of the line
    Q = r.sub(' ',''.join([question,' '])).upper()
    for c in cities:
        C = r.sub(' ',''.join([' ',c,' '])).upper()      
        if C in Q:
            pass

with open('cities') as fd:
    cities = [line.strip() for line in fd]

with open('question') as fd:
    question = fd.readlines()[0]

testfuncs = f0, f1, f2, f3, f4, f5

for f in testfuncs:
    print f
    timing(f, 20)

It is pretty fast:

<function f0 at 0x01F9B470>
f0 0.092498
<function f1 at 0x01F9B530>
f1 6.48321
<function f2 at 0x01F9B870>
f2 0.101243
<function f3 at 0x01F9B3F0>
f3 0.304404
<function f4 at 0x01F9B4F0>
f4 0.671799
<function f5 at 0x01F9B570>
f5 0.278714