Qual è il modo più efficiente per trovare una delle varie sottostringhe in Python?

Question

Ho una lista di possibili sottostringhe, ad es. ['gatto', 'pesce', 'cane']. In pratica la lista contiene centinaia di voci.

Sto elaborando una stringa e quello che sto cercando è trovare l'indice della prima apparizione di una qualsiasi di queste sottostringhe.

per chiarire, per '012cat' il risultato è 3, e per '0123dog789cat' il risultato è 4.

Ho anche bisogno di sapere quale stringa è stato trovato (ad esempio, il suo indice nella lista sottostringa o il testo stesso), o almeno la lunghezza della sottostringa corrispondente.

Ci sono ovvi modi di forza bruta per raggiungere questo obiettivo, mi chiedevo se per questo ci fosse una soluzione Python/Regex elegante.

Grazie, Rax

Answer 1

Vorrei assumere una regex è migliore di controllo per ogni sottostringa singolarmente perché concettualmente l'espressione regolare è modellato come un DFA, e così come l'ingresso è consumato tutte le partite vengono testati contemporaneamente (risultante in una scansione della stringa di input).

Quindi, ecco un esempio:

import re 

def work(): 
    to_find = re.compile("cat|fish|dog") 
    search_str = "blah fish cat dog haha" 
    match_obj = to_find.search(search_str) 
    the_index = match_obj.start() # produces 5, the index of fish 
    which_word_matched = match_obj.group() # "fish" 
    # Note, if no match, match_obj is None 

UPDATE: Alcuni occorre prestare attenzione quando si combinano parole ad un singolo modello di parole alternative. Il codice seguente costruisce un'espressione regolare, ma escapes any regex special characters e ordina le parole in modo che le parole più lunghe hanno la possibilità di abbinare prima di qualsiasi prefissi più brevi della stessa parola:

def wordlist_to_regex(words): 
    escaped = map(re.escape, words) 
    combined = '|'.join(sorted(escaped, key=len, reverse=True)) 
    return re.compile(combined) 

>>> r.search('smash atomic particles').span() 
(6, 10) 
>>> r.search('visit usenet:comp.lang.python today').span() 
(13, 29) 
>>> r.search('a north\south division').span() 
(2, 13) 
>>> r.search('012cat').span() 
(3, 6) 
>>> r.search('0123dog789cat').span() 
(4, 7) 

FINE UPDATE

Dovrebbe si noti che si vorrà formare la regex (es. - chiama re.compile()) il meno possibile. Il miglior caso sarebbe sapere in anticipo quali sono le tue ricerche (o le calcoli una volta/di rado) e poi salvare il risultato di re.compile da qualche parte. Il mio esempio è solo una semplice funzione senza senso in modo da poter vedere l'uso della regex. Ci sono alcuni documenti più regex qui:

http://docs.python.org/library/re.html

Spero che questo aiuti.

UPDATE: Non sono sicuro di come Python implementa le espressioni regolari, ma per rispondere alla domanda di Rax circa se o non ci sono limitazioni di re.compile() (ad esempio, quante parole si può provare a " | "insieme per abbinare in una sola volta), e la quantità di tempo per eseguire compilare: nessuno di questi sembra essere un problema. Ho provato questo codice, che è abbastanza buono per convincermi. (Avrei potuto farlo meglio aggiungendo i tempi e riportando i risultati, così come lanciando la lista di parole in un set per garantire che non ci siano duplicati ... ma entrambi questi miglioramenti sembrano un eccesso). Questo codice funzionava praticamente istantaneamente e mi convinse che sono in grado di cercare 2000 parole (di dimensione 10), e che e di esse corrisponderanno in modo appropriato.Ecco il codice:

import random 
import re 
import string 
import sys 

def main(args): 
    words = [] 
    letters_and_digits = "%s%s" % (string.letters, string.digits) 
    for i in range(2000): 
     chars = [] 
     for j in range(10): 
      chars.append(random.choice(letters_and_digits)) 
     words.append(("%s"*10) % tuple(chars)) 
    search_for = re.compile("|".join(words)) 
    first, middle, last = words[0], words[len(words)/2], words[-1] 
    search_string = "%s, %s, %s" % (last, middle, first) 
    match_obj = search_for.search(search_string) 
    if match_obj is None: 
     print "Ahhhg" 
     return 
    index = match_obj.start() 
    which = match_obj.group() 
    if index != 0: 
     print "ahhhg" 
     return 
    if words[-1] != which: 
     print "ahhg" 
     return 

    print "success!!! Generated 2000 random words, compiled re, and was able to perform matches." 

if __name__ == "__main__": 
    main(sys.argv) 

UPDATE: Va notato che l'ordine delle cose ORed insieme nella regex conta. Date un'occhiata al seguente test ispirato TZOTZIOY:

>>> search_str = "01catdog" 
>>> test1 = re.compile("cat|catdog") 
>>> match1 = test1.search(search_str) 
>>> match1.group() 
'cat' 
>>> match1.start() 
2 
>>> test2 = re.compile("catdog|cat") # reverse order 
>>> match2 = test2.search(search_str) 
>>> match2.group() 
'catdog' 
>>> match2.start() 
2 

Ciò suggerisce le questioni di ordine: - /. Non sono sicuro di cosa significhi per l'applicazione di Rax, ma almeno il comportamento è noto.

UPDATE: ho postato this questions about the implementation of regular expressions in Python che si spera di darci qualche informazione sulle problemi rilevati con questa domanda.

Answer 2

subs = ['cat', 'fish', 'dog'] 
sentences = ['0123dog789cat'] 

import re 

subs = re.compile("|".join(subs)) 
def search(): 
    for sentence in sentences: 
     result = subs.search(sentence) 
     if result != None: 
      return (result.group(), result.span()[0]) 

# ('dog', 4) 

Answer 3

Questa è una vaga risposta teorica senza codice fornito, ma spero che possa indirizzarvi nella giusta direzione.

In primo luogo, sarà necessaria una ricerca più efficiente per l'elenco delle sottostringhe. Consiglierei una sorta di struttura ad albero. Iniziare con una radice, quindi aggiungere un nodo 'a' se alcune sottostringhe iniziano con 'a', aggiungi un nodo 'b' se alcune sottostringhe iniziano con 'b' e così via. Per ognuno di questi nodi, continua ad aggiungere sottonodi.

Ad esempio, se si dispone di una stringa con la parola "ant", si dovrebbe avere un nodo radice, un nodo figlio 'a', un nodo nipotino 'n', e un grande nodo nipotino 't'.

I nodi dovrebbero essere abbastanza facili da realizzare.

class Node(object): 
    children = [] 

    def __init__(self, name): 
     self.name = name 

dove name è un personaggio.

Iterate attraverso le vostre stringhe lettera per lettera. Tieni traccia di quale lettera sei su. Ad ogni lettera, prova a usare le lettere successive per attraversare l'albero. Se hai successo, il tuo numero di lettera sarà la posizione della sottostringa e il tuo ordine trasversale indicherà la sottostringa trovata.

Modifica chiarificazione: i DFA dovrebbero essere molto più veloci di questo metodo, quindi dovrei sostenere Tom's answer. Sto mantenendo questa risposta solo nel caso in cui l'elenco delle sottostringhe cambia spesso, nel qual caso l'utilizzo di un albero potrebbe essere più veloce.

Answer 4

Prima di tutto, ti suggerisco di ordinare l'elenco iniziale in ordine crescente. Poiché la scansione di una sottostringa più corta è più veloce della scansione per una sottostringa più lunga.

Answer 5

Che ne dici di questo.

>>> substrings = ['cat', 'fish', 'dog'] 
>>> _string = '0123dog789cat' 
>>> found = map(lambda x: (_string.index(x), x), filter(lambda x: x in _string, substrings)) 
[(10, 'cat'), (4, 'dog')] 
>>> if found: 
>>>  min(found, key=lambda x: x[0]) 
(4, 'dog') 

Ovviamente, è possibile restituire qualcosa di diverso da una tupla.

Questo funziona:

• Filtrare l'elenco di sottostringhe verso il basso per quelli che sono nella stringa
• Costruire una lista di tuple contenenti l'indice della stringa, e la sottostringa
• Se un sottostringa trovata, trovare il valore minimo in base all'indice

Answer 6

Voglio solo sottolineare la differenza di tempo tra la risposta di DisplacedAussie e la risposta di Tom. Entrambi erano veloce quando usato una volta, quindi non dovreste avere alcun attesa evidente per entrambi, ma quando li avete tempo:

import random 
import re 
import string 

words = [] 
letters_and_digits = "%s%s" % (string.letters, string.digits) 
for i in range(2000): 
    chars = [] 
    for j in range(10): 
     chars.append(random.choice(letters_and_digits)) 
    words.append(("%s"*10) % tuple(chars)) 
search_for = re.compile("|".join(words)) 
first, middle, last = words[0], words[len(words)/2], words[-1] 
search_string = "%s, %s, %s" % (last, middle, first) 

def _search(): 
    match_obj = search_for.search(search_string) 
    # Note, if no match, match_obj is None 
    if match_obj is not None: 
     return (match_obj.start(), match_obj.group()) 

def _map(): 
    search_for = search_for.pattern.split("|") 
    found = map(lambda x: (search_string.index(x), x), filter(lambda x: x in search_string, search_for)) 
    if found: 
     return min(found, key=lambda x: x[0]) 


if __name__ == '__main__': 
    from timeit import Timer 


    t = Timer("_search(search_for, search_string)", "from __main__ import _search, search_for, search_string") 
    print _search(search_for, search_string) 
    print t.timeit() 

    t = Timer("_map(search_for, search_string)", "from __main__ import _map, search_for, search_string") 
    print _map(search_for, search_string) 
    print t.timeit() 

Uscite:

(0, '841EzpjttV') 
14.3660159111 
(0, '841EzpjttV') 
# I couldn't wait this long 

vorrei andare con la risposta di Tom, per entrambi leggibilità e velocità.