Geek asks and answers

Search string in text

When answering the question here about how to find the city in the question posed by the user, I started thinking about the best way to find a line in the text when you have a limited data set, like this one.

inand findmatches a substring that is not needed. Reqular expressions using word boundaries work, but are rather slow. The “punctuation” approach seems to be a candidate, but there are many punctuation symbols that can appear both in doubt and some in the name of the city (ie the period in St. Louis).

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

The task is as follows:

Find a city in the United States in a user-provided English text, regardless of the case.

My code is very 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 wants to go on my testdata, it can be found here

+3
source share
2 answers

Interestingly, the Prebuild regular expression for all cities (i.e., one regular expression for all cities) seems to benefit from execution. 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 added 5 more f11 functions 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

(f13) (.. ) . , regex (f15) .

@trutheality @Thomas.

+1

"":

#!/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)

:

<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
+1

More articles:


All Articles