modo più veloce per cercare 1GB + una stringa di dati per la prima occorrenza di un modello in Python

Question

C'è una stringa di 1 gigabyte di dati arbitrari, che si può presumere di essere equivalente a qualcosa come:

1_gb_string=os.urandom(1*gigabyte) 

Saremo cercando questa stringa, 1_gb_string, per un numero infinito di larghezza fissa, modelli 1 kilobyte, 1_kb_pattern. Ogni volta che cerchiamo il modello sarà diverso. Quindi le opportunità di caching non sono evidenti. La stessa stringa da 1 gigabyte verrà ricercata più e più volte. Ecco un semplice generatore per descrivere cosa sta succedendo:

def findit(1_gb_string): 
    1_kb_pattern=get_next_pattern() 
    yield 1_gb_string.find(1_kb_pattern) 

Si noti che deve essere trovata solo la prima occorrenza del modello. Dopodiché, non dovrebbe essere eseguita alcuna altra elaborazione importante.

Cosa posso usare che è più veloce di trovare Python bultin per la corrispondenza 1KB modelli contro 1 GB o più stringhe di dati?

(io sono già a conoscenza di come dividere la stringa e la ricerca in parallelo, in modo da poter ignorare che l'ottimizzazione di base.)

Aggiornamento: Si prega di bound requisiti di memoria a 16 GB.

Answer 1

Con memoria infinita, è possibile eseguire l'hash di ogni stringa da 1 k insieme alla posizione nel file da 1 GB.

Con meno di memoria infinita, sarai limitato da quante pagine di memoria tocchi durante la ricerca.

Answer 2

Esistono numerosi algoritmi di corrispondenza delle stringhe utilizzati nel campo della genetica per trovare sottostringhe. Potresti provare this paper o this paper

Answer 3

Sei disposto a dedicare un tempo significativo alla pre-elaborazione della stringa?

Se lo sei, ciò che puoi fare è creare un elenco di n-grammi con offset.

Supponiamo che il tuo alfabeto sia esadecimale e tu stia usando 1 grammo.

Poi per 00-FF, è possibile creare un dizionario che si presenta così (perlese, scusate)

$offset_list{00} = @array_of_offsets 
$offset_list{01} = #...etc 

dove si cammina lungo la corda e crea il @array_of_offsets da tutti i punti in cui avvengono byte. Puoi farlo per arbitrari n-grammi.

Questo fornisce un "punto di partenza per la ricerca" che è possibile utilizzare per camminare.

Ovviamente, lo svantaggio è che è necessario eseguire il preprocesso della stringa, quindi questo è il tuo compromesso.

edit:

---

L'idea di base è quella di abbinare i prefissi. Ciò potrebbe causare gravi bombardamenti se l'informazione è super-simile, ma se ha una buona dose di divergenza tra n-grammi, dovresti essere in grado di abbinare i prefissi piuttosto bene.

Cerchiamo di quantificare la divergenza, dal momento che non hai discusso il tipo di informazioni che stai analizzando.Ai fini di questo algoritmo, possiamo caratterizzare la divergenza come una funzione di distanza: è necessario un decente alto Hamming distance. Se la distanza di hamming tra n-gram è, ad esempio, 1, l'idea di cui sopra non funzionerà. Ma se è n-1, l'algoritmo di cui sopra sarà molto più facile.

di migliorare il mio algoritmo, costruiamo un algoritmo che fa alcune successiva eliminazione della possibilità:

Possiamo invocare Shannon Entropy per definire le informazioni di un determinato n-gram. Prendi la tua stringa di ricerca e successivamente costruisci un prefisso basato sui primi m caratteri. Quando l'entropia del prefisso m è "sufficientemente alta", usala in un secondo momento.

1. Definire p essere un m-prefix della stringa di ricerca
2. Cerca la stringa di 1 GB e creare una serie di compensazioni che corrispondono a p.
3. Estendere il prefisso m come prefisso k, k> m, entropia del prefisso k superiore al prefisso m.
4. Mantiene l'array di offset di elementi definito in precedenza, in modo che corrisponda alla stringa del prefisso k. Scarta gli elementi non corrispondenti.
5. Goto 4 fino a quando non viene soddisfatta l'intera stringa di ricerca.

In un certo senso, questo è come invertire la codifica di Huffman.

Answer 4

Non so definitivamente se il metodo find() per le stringhe è più veloce rispetto al metodo search() fornito da re (espressioni regolari) di Python modulo, ma non c'è un solo modo per scoprirlo.

Se sei solo alla ricerca di una stringa, ciò che si vuole è questo:

import re 
def findit(1_gb_string): 
    yield re.search(1_kb_pattern, 1_gb_string) 

Tuttavia, se si vuole veramente solo la prima partita, si potrebbe essere meglio utilizzare finditer(), che restituisce un iteratore, e con operazioni così grandi potrebbe effettivamente essere migliore.

Answer 5

http://www.youtube.com/watch?v=V5hZoJ6uK-s Sarà di gran valore per voi. È una conferenza del MIT su Programmazione dinamica

Answer 6

Per quanto ne so, l'algoritmo di ricerca standard è un algoritmo ingenuo con complessità sui confronti n * m, perché lo controlla i pattern contro ogni offset possibile. Ci sono alcuni algoithms più efficaci, che richiedono circa n + m confronti. Se la tua stringa non è una stringa di lingua naturale, puoi provare Knuth–Morris–Pratt algorithm. Anche l'algoritmo di ricerca di Boyer-Moore è abbastanza veloce e semplice.

Answer 7

Se i motivi sono abbastanza casuali, è possibile precomputare la posizione dei prefissi n delle stringhe.

Invece di andare su tutte le opzioni per i prefissi n, basta usare quelli effettivi nella stringa da 1 GB - ci sarà meno di 1Gig di quelli. Utilizzare come prefisso grande come si adatta alla memoria, non ho 16 GB di RAM da controllare ma un prefisso di 4 potrebbe funzionare (almeno in una struttura di dati efficiente della memoria), se non provare 3 o addirittura 2.

Per una stringa casuale da 1 GB e pattern casuali da 1 KB, è consigliabile ottenere 10 secondi di posizioni per prefisso se si usano prefissi da 3 byte, ma i prefissi da 4 byte dovrebbero ottenere una media di 0 o 1, quindi la ricerca dovrebbe essere veloce.

Precompute Luoghi

def find_all(pattern, string): 
    cur_loc = 0 
    while True: 
    next_loc = string.find(pattern, cur_loc) 
    if next_loc < 0: return 
    yield next_loc 
    cur_loc = next_loc+1 

big_string = ... 
CHUNK_SIZE = 1024 
PREFIX_SIZE = 4 
precomputed_indices = {} 
for i in xrange(len(big_string)-CHUNK_SIZE): 
    prefix = big_string[i:i+PREFIX_SIZE] 
    if prefix not in precomputed_indices: 
    precomputed_indices[prefix] = tuple(find_all(prefix, big_string)) 

Cercare un modello

def find_pattern(pattern): 
    prefix = pattern[:PREFIX_SIZE] 
    # optimization - big prefixes will result in many misses 
    if prefix not in precomputed_indices: 
    return -1 
    for loc in precomputed_indices[prefix]: 
    if big_string[loc:loc+CHUNK_SIZE] == pattern: 
     return loc 
    return -1 

Answer 8

Come a chiarire che la pre-elaborazione a lungo ish è accettabile, io suggerirei di una variante di Rabin-Karp: "un algoritmo di scelta per la ricerca di più pattern ", come dice wikipedia.

Definire una funzione "rolling hash", ad esempio una che, quando si conosce l'hash per haystack[x:x+N], il calcolo dell'hash per haystack[x+1:x+N+1] è O (1). (Le normali funzioni di hashing come il hash integrato di Python non hanno questa proprietà, motivo per cui è necessario scriverne una propria, altrimenti la preelaborazione diventa estenuante piuttosto che meramente long-ish ;-). Un approccio polinomiale è fruttuoso e si potrebbero usare, ad esempio, risultati di hash a 30 bit (mascherando se necessario, cioè, è possibile eseguire il calcolo con maggiore precisione e memorizzare solo i 30 bit mascherati di scelta). Chiamiamo questa funzione rotativa di hash RH per chiarezza.

Quindi, calcolare 1G di risultati RH mentre si scorre lungo la stringa 1GB del pagliaio; se li hai appena archiviati, ti darebbe un array H di valori 1G a 30 bit (4 GB) di mappatura index-in-haystack-> RH value. Ma vuoi la mappatura inversa, quindi usa invece un array A di 2 ** 30 voci (1G voci) che per ogni valore di RH ti dà tutti gli indici di interesse nel pagliaio (indici a cui si verifica quel valore di RH); per ogni voce si memorizza l'indice del primo indice di pagliaio possibilmente interessante in un altro array B di indici 1G nel mucchio di fieno che viene ordinato di mantenere tutti gli indici nel pagliaio con valori RH identici ("collisioni" in termini di hashing) adiacenti. H, A e B hanno entrambe voci 1G da 4 byte ciascuna, quindi 12 GB totali.

Ora per ogni ago 1K in arrivo, calcolare la sua RH, chiamarlo k e usarlo come indice in A; A [k] ti dà il primo indice b in B al quale vale la pena confrontare. Quindi, fare:

ib = A[k] 
b = B[ib] 
while b < len(haystack) - 1024: 
    if H[b] != k: return "not found" 
    if needle == haystack[b:b+1024]: return "found at", b 
    ib += 1 
    b = B[ib] 

con una buona umidità relativa si dovrebbe avere alcuni contatti, quindi il tempo deve essere avviata a pochissime volte fino a quando il ritorno in un modo o nell'altro. Quindi ogni ricerca dell'ago dovrebbe essere davvero molto veloce.

Answer 9

Qualcuno ha suggerito un modo per indicizzare questa cosa se si dispone di RAM abbondante (o forse anche di disco/scambio) disponibile.

Immaginate se eseguite un semplice CRC a 32 bit su un blocco 1K che si estende da ciascun carattere nella stringa Gig originale. Ciò risulterebbe in 4 byte di dati di checksum per ogni offset di byte dall'inizio dei dati.

Di per sé, questo potrebbe fornire un modesto miglioramento della velocità di ricerca. Il checksum di ciascun target di ricerca 1K potrebbe essere verificato rispetto a ciascun CRC ... che ogni collisione ha testato per una corrispondenza vera. Dovrebbe comunque essere un paio di ordini di grandezza più veloce di una normale ricerca lineare.

Questo, ovviamente, ci costa 4 GB di RAM per l'array CRC (oltre al Gig originale per i dati originali e un po 'più di overhead per l'ambiente e il nostro programma).

Se si dispone di ~ 16 GB, è possibile ordinare i checksum e memorizzare un elenco di offset in cui ciascuno viene trovato. Ciò diventa una ricerca indicizzata (media di circa 16 sonde per ricerca obiettivo ... caso peggiore intorno a 32 o 33 (potrebbe essere un recinto lì).

È possibile che un indice di file 16BG continui a fornire prestazioni migliori rispetto a una ricerca di checksum lineare e sarebbe quasi certamente migliore di una ricerca raw lineare (a meno che non si disponga di filesystem/storage estremamente lenti).

(Aggiunta): Devo chiarire che questa strategia è utile solo perché hai descritto la necessità di eseguire molte ricerche sullo stesso blob di dati di un gigabyte.

È possibile utilizzare un approccio a thread per creare l'indice (durante la lettura e per avere più thread che eseguono il checksum). È inoltre possibile scaricare l'indicizzazione in processi separati o in un cluster di nodi (in particolare se si utilizza un indice basato su file, l'opzione ~ 16 GB descritta sopra). Con un semplice CRC a 32 bit potresti essere in grado di eseguire il checksum/indicizzazione con la stessa velocità con cui il thread del lettore può ottenere i dati (ma stiamo parlando di 1024 checksum per ogni 1K di dati, quindi forse no).

È possibile migliorare ulteriormente le prestazioni codificando un modulo Python in C per eseguire effettivamente la ricerca ... e/o eventualmente per eseguire il checksum/l'indicizzazione.

Lo sviluppo e il test di tali estensioni C comportano altri compromessi, ovviamente. Sembra che questo avrebbe quasi zero riutilizzabilità.

Answer 10

Un modo efficiente ma complesso è full-text indexing with the Burrows-Wheeler transform. Si tratta di eseguire un BWT sul testo sorgente, quindi utilizzare un piccolo indice su quello per trovare rapidamente sottostringhe nel testo che corrisponde al modello di input.

La complessità temporale di questo algoritmo è approssimativamente O (n) con la lunghezza della stringa che si sta verificando - e indipendente dalla lunghezza della stringa di input! Inoltre, la dimensione dell'indice non è molto più grande dei dati di input, e con la compressione può anche essere ridotta al di sotto della dimensione del testo sorgente.