c++ Caricamento file e ricerca

[Hardcore]

Allora quello che devo fare è caricare un file di QUALSIASI dimensione e poi cercare se su questo file ci sono byte simili da poi dare in pasto a un algoritmo di comprensione.

Il problema è questo.

Per caricare il file, dato che lo posso vedere come una sequenza di byte, carico il file in una stringa.

Mi ritrovo pertanto una stringa grande tot carattari quanti sono i byte del file.

Dopo per trovare byte simili uso il metodo find, ad esempio passo il primo byte e vedo se ne trova un altro.

Ora il metodo find sembra funzionare bene per file di piccole dimensioni:100-200kb
Ma risulta una merda se il file è di qualche MB, non parliamo di GB..........

Esiste un qualche modo per avere un find decente?
Esistono altri modi per caricare file e operare funzioni di ricerca su essi piu veloci?

La risposta è sicuramente si, in quanto algoritmi come WinZip fanno quello che io voglio e ci mettono secondi non ore come me. Il discorso è, come fanno?

[Bers]

beh buttare un file da qualche gb in una stringa (quindi in memoria) sicuramente non è efficente...
se poi parliamo del find...
secondo mepuoi usare il vecchio fread (non ricordo se è deprecato) -> bufferizzi il byte in una variabile (mi pare esista il Byte) e fai il check con tutti gli if annidati in modo: (trovo il primo che mi fa, continuo, trovo il secondo, continuo ecc ecc

altra soluzione meno laboriosa: cerchi qualcosa in rete di già compilato (esisterà di sicuro per linux una cosa fatta come serve a te) e ci fai una fork e poi un exec :)

[Eltarion]

si sennò bufferizzi la lettura e vai di memcmp ahahah :D

[Amiag]

che vuol dire byte simile ? devi cercare una sequenza di byte ?

in ogni caso ti sconsiglio di caricarlo in memoria se il file puo essere molto grande, cerca direttamente da file leggendo i byte/sequenze una per volta

[Hardcore]

Devo implementare l'algoritmo Lempel Ziv 77.
Deve trovare sequenze di byte simili all'interno di una sliding windows che scorre mentre leggo il file.

Il find non è eseguito sul file che viene letto sequenzialmente, bensi è eseguita su questa windows.
Le terne in output sono: quanto vado indietro nel dizionario,dimensione stringa trovata nel dizionario, carattere aggiuntivo che inserisco

Faccio un esempio per chiarire:


File= aaabbcdeaab
Dizionario dimensione max=3

T0: Read a C'è nel dizionario? No Diz=a Output(0,0,a);
T1: Read a C'è? SI. Read a. C'è? Si. Read b. C'è? NO Diz=aaab. Dimensione >3? SI -> Taglio il primo valore . Diz= aab. Output(1,2,b);
T2: Read b C'è? SI Read c. C'è? No. Diz=aabbc. Dimensione >3? Si, tolgo 2 elementi. Diz= bbc Output (1,1,c)

[Eltarion]

Non riesco bene a capire cosa ti serva sapere quindi :/

Cioè il file lo tieni aperto in uno stream e poi ti sposti di quanto ti pare nella direzione che ti pare e le sequenze te le salvi in mappe o array o quello che ti aggrada di più, ma forse non ho ben compreso il problema.

[Hardcore]

il problema è che se il dizionario è grande 10000 Byte
e io cerco la stringa 100 volte A

lui parte a cercare A
poi AA
poi AAA
poi AAAA

se ogni volta la trova e poniamo che ci sia davvero
esegue sto Find 100 volte.

Poniamo che la stringa sia in fondo al dizionario

legge ogni volta TUTTO il dizionario.

Ora io mi chiedevo se esistono algoritmi per ottimizzare il find di sub.stringhe in una stringa.

[Amiag]

onestamente non riesco a capire cosa ti serva, ma mi pare che leggi un carattere per volta dal file, quindi se mai il problema e' l'accesso al dizionario.

hai provato con una hashmap o simili invece che lo stringone ?

[San Vegeta]

Ciao, mi permetto di farti notare delle cose, poi vedo se riesco ad aiutarti.

1) non esistono byte simili, esistono byte identici o diversi
2) parli di byte e poi parli di caratteri: sappi che fino a un alfabeto di 256 simboli puoi continuare a trattarli nel medesimo modo, per albafeti con più simboli non puoi più ragionare per byte=char
3) Se hai un insieme A di N elementi, in cui ogni n appartenente a A può essere un {s1, s2, s3, ... sm}, quindi M diversi simboli, sono valide le seguenti regole:
- per conoscere ogni n di A, devi leggere ogni elemento, quindi almeno N letture.
- le possibili combinazioni sono NxM

passiamo all'algoritmo.
sinceramente non ho capito bene come funziona e non ho voglia di andare a cercarmi la spiegazione, cmq posso darti alcuni hint

parli di finestre: è corretto, un algoritmo di compressione per essere performante deve lavorare su sottogruppi di elementi, quindi finestre di dati
per leggere N byte in memoria, basta allorare un array di N byte (o char): lavorerai su quell'array. Leggere N byte è la parte più "pesante" del lavoro.
per come hai spiegato l'algoritmo, è ovvio che ad ogni passaggio esamini un carattere, carattere che hai già in memoria, quindi le operazioni di confronto sono da considerare quasi istantanee

non capisco perchè poi chiedi algoritmi che ottimizzare il find di sottostringhe in stringhe (se non puoi fare nessuna assunzione sul contenuto della stringa, non ci sono alternative a esaminare ogni singolo elemento): esistono dei metodi che confrontano array di caratteri, sfruttando la rappresentazione a bit di ogni carattere, ma credo sia al di fuori della tua portata per lo scopo.

poi visto che chiedevi come farlo in C++, ecco un help, poi continui tu



std::ifstream file
int windowSize = 100;
size_t fileSize;
size_t deltaSize = 0;

file.open("mycert.cer", ios_base::binary);
if(!file.is_open())
return;

file.seekg(0, ios::end);
fileSize = file.tellg();
deltaSize = fileSize;

file.seekg(0, ios::beg);


std::vector<byte> data(windowSize, 0);

do {
if(deltaSize < windowSize) {
file.read(reinterpret_cast<char*>(&data[0]), deltaSize );
} else {
file.read(reinterpret_cast<char*>(&data[0]), windowSize);
}
deltaSize -= windowSize;
// do something with data


} while (deltaSize == 0);

file.close();

[Axet]

Quello che intendi fare, per come l'hai spiegato, si chiama string pattern matching.
Esistono un tot di algoritmi preposti, ti porto l'esempio del Boyer-Moore che se non ricordo male ha tempo di calcolo O(m+n) e anzi SE NON ERRO nel caso medio è pure logaritmico.