python - 在文本中搜索字符串

Question

在 SO 上回答了关于在某地寻找城市的问题后用户提供的问题，我开始考虑最好的方法当您的数据集有限时，在文本中搜索字符串。

in 和 find 匹配不需要的子字符串。定期使用“单词边界”的表达式有效但速度很慢。这“标点符号”的做法似乎是一个候选，但有很多标点符号characters既可以出现在问题中也可以出现一些以城市的名义(即“圣路易斯”的一个时期)。

正则表达式可能是最好的通用解决方案，但我好奇这是否可以使用其他技术解决。

任务是:

在用户提供的英文文本中查找美国的城市不分大小写。

我的代码深受 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)

在我的旧笔记本电脑上，我得到以下结果

<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

如果有人想看我的测试数据，可以找到 here

Answer 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 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)

注意:我在 f11 到 f15 添加了 5 个函数。

这是输出(在我的膝上看到的):

<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) 正则表达式(即所有城市的一个正则表达式)性能良好。另请注意，预编译此类预构建正则表达式 (f15) 并未提高性能。

基于@trutheality 和@Thomas 的上述评论。