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

Question

Ho un elenco di possibili sottostringhe, ad es.['gatto', 'pesce', 'cane'].In pratica l'elenco 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 sottostringa è stata trovata (ad es.il suo indice nell'elenco delle sottostringhe o nel testo stesso), o almeno la lunghezza della sottostringa corrispondente.

Esistono ovvi modi di forza bruta per raggiungere questo obiettivo, mi chiedevo se esistesse qualche elegante soluzione Python/Regex per questo.

Grazie, rax

Answer 1

Presumo che una regex sia migliore del controllo individuale di ciascuna sottostringa perché concettualmente l'espressione regolare è modellata come un DFA e quindi, man mano che l'input viene utilizzato, tutte le corrispondenze vengono testate contemporaneamente (con conseguente 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

AGGIORNAMENTO:È necessario prestare una certa attenzione quando si combinano le parole in un unico modello di parole alternative.Il codice seguente crea una regex, ma sfugge a qualsiasi carattere speciale regex e ordina le parole in modo che le parole più lunghe abbiano la possibilità di corrispondere prima di qualsiasi prefisso più breve 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 AGGIORNAMENTO

Va notato che vorrai formare la regex (cioè la chiamata a re.compile()) il meno possibile.Il caso migliore sarebbe che tu sapessi in anticipo quali sono le tue ricerche (o le calcoli una volta/raramente) e quindi salvi il risultato di ricompilare da qualche parte.Il mio esempio è solo una semplice funzione senza senso in modo da poter vedere l'utilizzo della regex.Ci sono altri documenti regex qui:

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

Spero che questo ti aiuti.

AGGIORNAMENTO: Non sono sicuro di come Python implementi le espressioni regolari, ma per rispondere alla domanda di Rax sull'esistenza o meno di limitazioni di re.compile() (ad esempio, quante parole puoi provare a "|" insieme per far corrispondere contemporaneamente), e la quantità di tempo per eseguire la compilazione:nessuno di questi sembra essere un problema.Ho provato questo codice, che è abbastanza buono da convincermi.(Avrei potuto migliorarlo aggiungendo tempistiche e riportando i risultati, oltre a inserire l'elenco di parole in un set per garantire che non ci siano duplicati...ma entrambi questi miglioramenti sembrano eccessivi).Questo codice è stato eseguito praticamente istantaneamente e mi ha convinto 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)

AGGIORNAMENTO: Va notato che l'ordine delle cose è combinato con OR nella regex importa.Dai un'occhiata al seguente test ispirato da 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 che l'ordine è importante :-/.Non sono sicuro di cosa significhi per l'applicazione di Rax, ma almeno il comportamento è noto.

AGGIORNAMENTO: ho pubblicato questa domanda sull'implementazione delle espressioni regolari in Python che si spera ci forniranno alcune informazioni sui problemi riscontrati 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

Voglio solo sottolineare la differenza di tempo tra la risposta di DisplacedAussie e la risposta di Tom. Entrambi sono stati veloci se usati una volta, quindi non dovresti avere alcuna attesa evidente per entrambi, ma quando li credi:

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, sia per la leggibilità che per la velocità.

Answer 4

Questa è una risposta vaga e teorica senza codice fornito, ma spero che possa indicarti la giusta direzione.

Innanzitutto, avrai bisogno di una ricerca più efficiente per il tuo elenco di sottostringhe. Consiglierei una sorta di struttura ad albero. Inizia con una radice, quindi aggiungi un nodo 'a' se alcune sottostringhe iniziano con 'b', aggiungi un nodo 'n' se eventuali sottostringhe iniziano con 't' e così via. Per ciascuno di questi nodi, continua ad aggiungere nodi secondari.

Ad esempio, se hai una sottostringa con la parola " ant " ;, dovresti avere un nodo radice, un nodo figlio name, un nodo nipote <=> e un ottimo nodo nipote <=>.

I nodi dovrebbero essere abbastanza facili da creare.

class Node(object):
    children = []

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

dove <=> è un personaggio.

Scorrere le stringhe lettera per lettera. Tieni traccia della lettera in cui ti trovi. Ad ogni lettera, prova a usare le prossime lettere per attraversare l'albero. Se hai esito positivo, il numero della tua lettera sarà la posizione della sottostringa e il tuo ordine di movimento indicherà la sottostringa che è stata trovata.

Chiarire la modifica: i DFA dovrebbero essere molto più veloci di questo metodo, quindi dovrei approvare La risposta di Tom . Conservo questa risposta solo nel caso in cui l'elenco delle sottostringhe cambi spesso, nel qual caso l'utilizzo di un albero potrebbe essere più veloce.

Answer 5

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

Answer 6

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, potresti restituire qualcosa di diverso da una tupla.

Funziona con:

• Filtraggio dell'elenco delle sottostringhe fino a quelle presenti nella stringa
• Creazione di un elenco di tuple contenente l'indice della sottostringa e della sottostringa
• Se è stata trovata una sottostringa, trova il valore minimo basato sull'indice