Rechercher une chaîne dans un texte

Question

Après avoir répondu à une question ici sur le SO de trouver une ville dans une question fournie par l'utilisateur , je commencé à penser à la meilleure façon de recherche d'une chaîne dans un texte lorsque vous avez un ensemble de données limité comme celui-ci.

in et find correspond à une sous-chaîne, ce qui n'est pas souhaitable. Exiger les expressions utilisant des "limites de mots" fonctionnent mais sont assez lentes. L'approche "ponctuation" semble être un candidat, mais il y a beaucoup de ponctuation characters qui peuvent apparaître à la fois en question ainsi que certains dans le nom d'une ville (c'est-à-dire une période dans "St. Louis").

Les expressions rationnelles sont probablement la meilleure solution à usage général, mais je suis curieux de savoir si cela peut être résolu en utilisant une autre technique.

La tâche consiste à:

Trouver une ville aux États-Unis dans un texte fourni par l'utilisateur dans la langue anglaise quel que soit le cas.

Mon code fortement inspiré par 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) 

Sur mon vieux portable louches, je reçois les résultats suivants

<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 

Si quelqu'un aimerait avoir un aller sur mon testdata, il peut être trouvé here

Answer 1

Intéressant, Prebuild regex pour toutes les villes (ie. un regex semble gagner à la performance. J'ai utilisé le même cas de test et voici le résultat.

#!/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: J'ai ajouté 5 autres fonctions f11 à f15.

est ici la sortie (comme on le voit dans mon lappy): (.-À-dire une expression rationnelle pour toutes les villes)

<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 pour toutes les villes est bonne à la performance. Notez également que la précompilation d'une telle expression regex (f15) n'a pas été ajoutée à la performance. Basé sur les commentaires ci-dessus par @trutheality et @Thomas

Answer 2

Une upgrowth de votre approche "ponctuation":

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

Il est assez rapide:

<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