Поиск строки в тексте

Question

После ответа на вопрос в SO о поиске города в пользовательском вопросе я начал думать о best способе поиска строки в тексте, когда у вас ограниченный набор данныхкак этот.

in и find совпадают с подстрокой, которая не нужна.Регулярные выражения, использующие «границы слов», работают, но работают довольно медленно.Подход «пунктуации» кажется подходящим, но есть много знаков препинания символов , которые могут появляться как в вопросе, так и в названии города (то есть точка в «Сент-Луисе»").

Регулярные выражения, вероятно, являются лучшим решением общего назначения, но мне любопытно, может ли это быть решено с использованием некоторой другой техники.

Задача состоит в том, чтобы:

Найти город в США по тексту, предоставленному пользователем на английском языке, независимо от регистра.

Мой код в значительной степени вдохновлен 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

Если кто-то захочет проверить мои тестовые данные, его можно найти здесь

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

Answer 2

Интересно, Регулярное выражение для всех городов (т. Е. Одно регулярное выражение для всех городов) , кажется, выигрывает в производительности.Я использовал тот же тест, и вот результат.

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