在文本中查找字符串
在这里回答了一个关于如何在用户提供的问题中找到城市的问题后，我开始思考在这种有限的数据集中，搜索文本中的字符串的最佳方法。
in和find是用来匹配子字符串的，但这并不是我们想要的。使用“单词边界”的正则表达式可以工作，但速度比较慢。“标点符号”方法似乎是一个候选方案，但在问题中和城市名称中都可能出现很多标点符号字符（比如“St. Louis”中的句点）。
正则表达式可能是最好的通用解决方案，但我很好奇是否可以用其他技术来解决这个问题。
任务是：
在用户提供的英文文本中找到美国的城市，不论大小写。
我的代码受到了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
如果有人想试试我的测试数据，可以在这里找到。
2 个回答
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
有趣的是，为所有城市预先构建正则表达式（也就是说，所有城市用一个正则表达式）在性能上似乎表现得更好。我使用了相同的测试案例，结果如下。
#!/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)
注意：我增加了5个新函数，从f11到f15。
这是输出结果（在我的电脑上看到的）：
<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的评论。