Ricerca di una stringa in un flusso di input

Question

Ho un file binario di grandi dimensioni (molti gigabyte, quindi caricarlo in memoria non è un'opzione) che voglio cercare tutte le occorrenze della stringa "icpf".

Ho provato a utilizzare std::search per questo, ma sono stato appena morso dal fatto che std::search funziona solo per gli iteratori di inoltro, non per gli iteratori di input.

La libreria standard fornisce un'alternativa veloce per questo? O ho bisogno di codificare manualmente la ricerca (o leggere in blocchi alla volta poi std::search su quelli, o ignore tutto fino a un 'i' e quindi controllare manualmente i prossimi tre caratteri)?

Answer 1

La libreria standard fornisce un'alternativa rapida per questo?

Sebbene la libreria C++ standard offra modi per cercare flussi di testo, non offre algoritmi comparabili per i flussi binari.

o devo a mano il codice di ricerca (sia la lettura in blocchi alla volta poi std::search su quelle, o ignorare tutto ciò fino a quando un 'i' e quindi controllare manualmente i tre caratteri successivi)?

Codificare l'approccio "salta e cerca" potrebbe essere complicato, perché è facile codificare una soluzione che salta le voci. Ad esempio, se si sta cercando in un file contenente "icpicpf", un semplice programma che elabora un carattere per volta non riesce a trovare il suffisso "icpf" dopo aver scartato il prefisso "icpi".

Se si desidera codificarlo autonomamente, prendere in considerazione l'implementazione di Knuth–Morris–Pratt algorithm. Esistono molte implementazioni disponibili online e funzionano correttamente sui flussi, poiché considerano un carattere alla volta e non tornano mai indietro.

Answer 2

Il metodo più veloce è caricare l'intero file in memoria, quindi cercare nella memoria.

La prossima alternativa migliore è quella di mantenere il disco rigido in movimento. Forse ha un thread che legge blocchi di dati in un buffer e un altro thread che cerca nel buffer.

Scendendo alla lista, leggendo grandi blocchi di dati in un buffer, la ricerca del buffer è una buona tecnica, sebbene non efficiente come i metodi precedenti.

È possibile leggere linea per linea, utilizzando std::getline e std::string. Non è veloce quanto la lettura di blocchi perché la funzione di input sta cercando il carattere di nuova riga (e l'allocazione della memoria nello std::string).

Il caso peggiore è probabilmente la lettura carattere per carattere. Il sovraccarico della funzione è negativo per la lettura di un singolo carattere (in genere il sovraccarico è lo stesso per la lettura di un grande blocco di dati).

No, non esiste una funzione di libreria C++ standard per la ricerca di file. Alcuni sistemi operativi dispongono di utilità per la ricerca di file; forse puoi usare uno di quelli.

Edit 1:
Il collo di bottiglia è l'immissione dei dati. Una volta ottenuti i dati in un buffer, esistono molti algoritmi di ricerca efficienti piuttosto che la forza bruta (cercare la prima lettera, quindi cercare le lettere successive, ecc.).

Cercare in Internet "algoritmo di ricerca stringa".

Answer 3

Non so di qualsiasi soluzione di libreria standard puro, ma il kernel implementa già prefetching, quindi dovrebbe essere possibile mmap() il file per ottenere le richieste in avanti iteratori: (Gestione degli errori omesso)

size_t search(int fd, size_t fileSize) { 
    auto start = reinterpret_cast<char*>(
     ::mmap(nullptr, fileSize, PROT_READ, MAP_PRIVATE | MAP_NORESERVE, fd, 0)); 
    ::madvise(start, fileSize, MADV_SEQUENTIAL); 
    auto pattern = "icpf"; 
    auto offset = std::search(start, start+fileSize, pattern, pattern+4); 
    return offset - start; 
} 

È un piccolo atto di fiducia, confidando nel fatto che il kernel esegua il caricamento lazy, il prefetch e lo scarto correttamente. D'altra parte, se puoi fidarti di chiunque con questo, probabilmente saranno gli sviluppatori del kernel.

Declinazione di responsabilità: in realtà non l'ho verificato su un file multi-gigabyte.