View Full Version : [c] Run Lenght Encoding - suggerimenti per ottimizzazione
Ciao a tutti, ho fatto un programma molto semplice che ricevendo in input un file lo comprime o lo decomprime a seconda dell'estensione che ha.
Devo utilizzare il metodo rle:
esempio file originale
aaaabbcde
esempio file compresso
a4b2c1d1e1
Dal punto di vista pratico nel file compresso ci sono delle lettere scritte come char (1 byte) e dei numeri scritti come short int (2 byte).
In questo modo se ho ad esempio una sequenza di 300 volte lo stesso carattere scrivendolo come short int occupa 3 byte (1 byte il carattere più 2 il numero di ripetizioni) mentre se usavo solo char ne avrebbe occupati 4.
Il problema sorge a questo punto a causa della premessa implementativa che ho descritto sopra.
Per ottimizzarlo potrei fare ad esempio così:
a4bbcde
cioè non scrivere il numero per le lettere con meno di 3 ripetizioni.
Però a questo punto il decompressore come agisce?
Il decompressore che ho fatto io legge sempre un char e poi uno short int che è il numero di ripetizioni perchè ogni carattere di fianco ha il numero.
Se io lo tolgo per alcuni di questi come faccio poi a sapere cosa devo leggere?
Laboratorio di programmazione con D'Angelo eh? Buona fortuna.
Laboratorio di programmazione con D'Angelo eh? Buona fortuna.
Eh già :D , per adesso non mi sembra complicato, solo non so usare cygwin e mi fa bestemmiare parecchio, comunque il progetto è quasi finito.
Spero che non mi massacri all'orale.
lupoxxx87
18-04-2010, 12:45
il decompressore deve fare uno scan di tutto il bytestream e ogni volta che incontra un intero n, fai partire un loop con n-1 cicli in cui inserisci in quel punto dello stream la lettera precedente al numero
Ciao a tutti, ho fatto un programma molto semplice che ricevendo in input un file lo comprime o lo decomprime a seconda dell'estensione che ha.
Devo utilizzare il metodo rle:
esempio file originale
aaaabbcde
esempio file compresso
a4b2c1d1e1
Dal punto di vista pratico nel file compresso ci sono delle lettere scritte come char (1 byte) e dei numeri scritti come short int (2 byte).
In questo modo se ho ad esempio una sequenza di 300 volte lo stesso carattere scrivendolo come short int occupa 3 byte (1 byte il carattere più 2 il numero di ripetizioni) mentre se usavo solo char ne avrebbe occupati 4.
Il problema sorge a questo punto a causa della premessa implementativa che ho descritto sopra.
Per ottimizzarlo potrei fare ad esempio così:
a4bbcde
cioè non scrivere il numero per le lettere con meno di 3 ripetizioni.
Però a questo punto il decompressore come agisce?
Il decompressore che ho fatto io legge sempre un char e poi uno short int che è il numero di ripetizioni perchè ogni carattere di fianco ha il numero.
Se io lo tolgo per alcuni di questi come faccio poi a sapere cosa devo leggere?
Io metterei un numero massimo di ripetizioni di 256, in modo tale da avere sempre e solo un byte per il numero, e non un short int.
Gia' in questo modo ho idea che si riduca notevolmente la lunghezza media del file compresso
E inoltre in questo modo non hai piu' alcun problema per la ripetizione doppia
Io metterei un numero massimo di ripetizioni di 256, in modo tale da avere sempre e solo un byte per il numero, e non un short int.
Gia' in questo modo ho idea che si riduca notevolmente la lunghezza media del file compresso
E inoltre in questo modo non hai piu' alcun problema per la ripetizione doppia
Ciao, grazie per la risposta, purtroppo da specifiche non posso mettere limitazioni di alcun tipo.
Il problema comunque è questo:
il programma riceve un file qualsiasi di cui non si conosce la natura per cui è impensabile leggere un po' di char e un po' di short int.
Potrei leggere solo char tanto per dire e poi se quello che ho letto non corrisponde ad una lettera dell'alfabeto (visto che nel file possono esserci solo lettere minuscole e spazi) allora lo rileggo come short int.
Il problema è: e se per caso quello che leggo come char (1 byte) casualmente mi corrisponde ad una lettera minuscola ma è in realtà il primo dei due byte di uno short int?
Ciao, grazie per la risposta, purtroppo da specifiche non posso mettere limitazioni di alcun tipo.
Il problema comunque è questo:
il programma riceve un file qualsiasi di cui non si conosce la natura per cui è impensabile leggere un po' di char e un po' di short int.
Potrei leggere solo char tanto per dire e poi se quello che ho letto non corrisponde ad una lettera dell'alfabeto (visto che nel file possono esserci solo lettere minuscole e spazi) allora lo rileggo come short int.
Il problema è: e se per caso quello che leggo come char (1 byte) casualmente mi corrisponde ad una lettera minuscola ma è in realtà il primo dei due byte di uno short int?
Ma "Short int" te lo impone il problema?
Comunque non proponevo di mettere limitazioni.
Se ad esempio avessi
bbb....bbb per 400 volte, lo comprimerei in
b255b45 (Oppure b0b45, contando lo 0 come 256, essendo che il valore 0 non avrebbe alcun senso)
per un totale di 4 bytes.
bb invece semplicemente
b2
:)
Eh già :D , per adesso non mi sembra complicato, solo non so usare cygwin e mi fa bestemmiare parecchio, comunque il progetto è quasi finito.
Spero che non mi massacri all'orale.
Tranquillo, non è niente di impossibile, soprattutto ora che non ne potrà più di LabProg :D
Ma "Short int" te lo impone il problema?
Comunque non proponevo di mettere limitazioni.
Se ad esempio avessi
bbb....bbb per 400 volte, lo comprimerei in
b255b45 (Oppure b0b45, contando lo 0 come 256, essendo che il valore 0 non avrebbe alcun senso)
per un totale di 4 bytes.
bb invece semplicemente
b2
:)
E' esattamente la stessa idea che ho consigliato io ad un mio compagno di corso :D
Ma "Short int" te lo impone il problema?
Comunque non proponevo di mettere limitazioni.
Se ad esempio avessi
bbb....bbb per 400 volte, lo comprimerei in
b255b45 (Oppure b0b45, contando lo 0 come 256, essendo che il valore 0 non avrebbe alcun senso)
per un totale di 4 bytes.
bb invece semplicemente
b2
:)
Un attimo perchè io con i cast ancora mi incasino.
Faccio un esempio semplice in cui non si va oltre le 256 ripetizioni.
Dunque, se ho un file che è solo una sequenza di 200 a, in pratica scrivo su file un char 'a' e un intero '200' convertito in char che quindi occupa 1 byte.
Poi leggo solo char e riconverto uno no e uno sì in interi?
Così occupa solo due byte un file che a me ne avrebbe occupati 3.
Però se poi ho un file 300 a e devo scrivere un char 'a' più un char '255' più un char 'a' più un char '45' mi occupa 4 byte invece di 3.
Come banco di test ho anche file di 300 mega (cha tra l'altro mi impallano il pc e non riesco a usare) per cui suppongo ci siano all'interno ripetizioni molto lunghe.
Posso provare ad implementarlo per vedere se ho capito bene la conversione dei tipi perchè mi sa che sto facendo un po' casino.
Però mi rimane il problema che non posso evitare di scrivere il numero di ripetizioni nelle lettere che si presentano una volta sola.
!k-0t1c!
18-04-2010, 14:53
Edit: rimosso perché contrario al regolamento
!k-0t1c!: non si scrivono soluzioni per esercizi universitari.
Potresti fare in questo modo...
Data una dimensione maggiore di 127 inserisci sempre un nuovo byte successivo al corrente.
In pratica puoi utilizzare l'ultimo bit del byte come un flag che indica la presenza di un altro byte da leggere. Chiaramente la dimensione può anche andare fino a 5 byte (con un intero a 32 bit) o anche oltre (in teoria potresti contare anche simulando un intero a 64 bit con due interi a 32 bit).
cdimauro
18-04-2010, 20:37
E' concettualmente simile alla codifica utilizzata per l'UTF-8.
Ma per il dato problema non mi sento di consigliarla, e preferisco la soluzione di "gugo", che è molto più semplice da implementare e rimane abbastanza generale ed efficiente.
In passato mi sono dedicato molto alla compressione dei dati (di qualunque natura), e debbo dire che molto, ma molto difficilmente i file presentano una "regolarità" tale da giustificare una codifica più complessa della classica RLE (che è stata comunque brevettata da un giapponese; ma penso che il brevetto sia ormai scaduto da tempo) con la coppia di byte lunghezza (da 1 a 256) + simbolo.
wingman87
18-04-2010, 21:56
Potresti rimappare i caratteri a-z più lo spazio nei valori da 0 a 26 ed usare i 229 valori rimanenti per i contatori.
Es:
a a a b b c
97 97 97 98 98 99
diventa:
a 3 b b c
0 29 1 1 2
oppure:
a 3 b 2 c
0 29 1 28 2
EDIT: non avevo letto bene, devi usare 2 byte per il contatore... Forse si può comunque riadattare l'idea
EDIT2: puoi usare i valori da 0 a 26 per i caratteri che hanno una sola occorrenza (quindi non c'è un contatore da leggere dopo) e i valori da 27 a 53 per i caratteri che precedono un contatore.
Es:
a a a b b c
97 97 97 98 98 99
diventa:
a 3 b b c
27 00 29 1 1 2
(ho messo 00 solo per indicare che 29 occupa 2 byte invece di uno)
!k-0t1c!
19-04-2010, 00:12
!k-0t1c!: non si scrivono soluzioni per esercizi universitari.
Almeno la parte in F# avresti potuto lasciarla, non era direttamente utile...
Inoltre l'implementazione che avevo proposto era a molto ingenua, avrebbe richiesto molto lavoro prima di essere presentabile ad un prof...senza contare che contavo deliberatamente solo fino a 255 per accertarmi che il copia-incolla fosse penalizzante :p
E' concettualmente simile alla codifica utilizzata per l'UTF-8.
Era giusto per fare un qualcosa di diverso dalla classica RLE ;) Sicuramente è più difficile da implementare, ma proprio per questo più culturalmente appagante :D
Grazie a tutti delle idee, sto prendendo un po' di qua e un po' di la per cercare di ottimizzare la cosa visto che il voto si basa sulla capacità di compressione ma anche sulla velocità impiegata.
Perché non usi un byte come escape che indica quando sta cominciando una sequenza di caratteri compressa? Ad esempio un '\0'. Se i caratteri sono ripetuti meno di 4 volte li copi così come sono altrimenti stampi il null, poi il carattere ripetuto e i due byte del short int con il numero di ripetizioni.
Dovrebbe scappare qualcosa di simile a questo (con i null al posto dei punti)
.a5bbbcdbbccccbb.a6.e12ffcde.f6.e9
Perché non usi un byte come escape che indica quando sta cominciando una sequenza di caratteri compressa? Ad esempio un '\0'. Se i caratteri sono ripetuti meno di 4 volte li copi così come sono altrimenti stampi il null, poi il carattere ripetuto e i due byte del short int con il numero di ripetizioni.
Dovrebbe scappare qualcosa di simile a questo (con i null al posto dei punti)
.a5bbbcdbbccccbb.a6.e12ffcde.f6.e9
Il problema in questo caso è che se ho ad esempio un file così:
aaaaaabhhhhhhhcaaaaaaa
mi vengono fuori tanti /0 ed alla fine non so se conviene o meno (anche perchè dovrei mettere un altro carattere una volta finita la sequenza compressa).
Il problema è che non so come saranno strutturati i file da comprimere quindi non posso fare dei calcoli di convenienza.
Però l'idea del /0 in effetti potrebbe farmi risparmiare il numero di fianco alle lettere singole.
Vi chiedo un'altra cosa: secondo voi mi conviene fare come diceva !k-0t1c! cioè leggere il file e mettere tutto in memoria (una matrice di char) e poi elaborarla dopo?
Perchè adesso come adesso io leggo un carattere da un file, eseguo calcoli e lo scrivo su file.
Leggere tutto il file e memorizzarlo per poi elaborare la matrice e riscriverla non mi viene a costare di più in termini di tempo? I calcoli comunque sono fatti in memoria anche se per effettuarli ora deve attendere i tempi di lettura, però anche leggendo tutto prima non si annullano. Il file rimane comunque aperto non è che ogni volta devo fare l'operazione di riaprirlo.
Ti conviene leggere un buffer di dimensione pari ad un multiplo o un sottomultiplo dell'unità di allocazione minima del disco. Quindi 4096 byte dovrebbe essere perfetto.
Se trovi \0 nel file però è un po' complessa la cosa ;)
Il problema in questo caso è che se ho ad esempio un file così:
aaaaaabhhhhhhhcaaaaaaa
mi vengono fuori tanti /0 ed alla fine non so se conviene o meno (anche perchè dovrei mettere un altro carattere una volta finita la sequenza compressa).
Il problema è che non so come saranno strutturati i file da comprimere quindi non posso fare dei calcoli di convenienza.
Però l'idea del /0 in effetti potrebbe farmi risparmiare il numero di fianco alle lettere singole.
Si. Se il file è composto principalmente da sequenze di caratteri molto lunghe allora non conviene. Se hai un po' di file di esempio prova a vedere con che probabilità compaiono. Così puoi decidere meglio. Ricorda poi che i contatori sono short int quindi valgono doppio.
Ti conviene leggere un buffer di dimensione pari ad un multiplo o un sottomultiplo dell'unità di allocazione minima del disco. Quindi 4096 byte dovrebbe essere perfetto.
Se trovi \0 nel file però è un po' complessa la cosa ;)
Se trova uno o più null stampa due null e il numero di volte ripetuto. Il decoder dovrebbe semplicemente controllare per il caso particolare in cui il null è seguito da un'altro null.
A spingersi ancora di più in la si potrebbe fare una scansione iniziale del file per vedere quale è il byte meno probabile ed usare quello come sequenza di escape.
DanieleC88
20-04-2010, 00:19
A spingersi ancora di più in la si potrebbe fare una scansione iniziale del file per vedere quale è il byte meno probabile ed usare quello come sequenza di escape.
:sofico:
:sofico:
-rw-r--r-- 1 mirco staff 294 20 Apr 00:35 prova.gz
-rw-r--r-- 1 mirco staff 357 20 Apr 00:35 prova.rle
-rw-r--r--@ 1 mirco staff 1488 20 Apr 00:21 prova.txt
Non è gzip ma considerato che sono 11 righe di codice non ci si può lamentare :asd:
DanieleC88
20-04-2010, 00:45
Dipende. Io in 11 righe di codice farei di meglio. :O
Bisogna vedere la lunghezza di queste righe.
:Prrr:
||ElChE||88
20-04-2010, 00:57
Dipende. Io in 11 righe di codice farei di meglio. :O
Bisogna vedere la lunghezza di queste righe.
:Prrr:
Potresti provare a scrivere un sistema operativo in una riga (lunga a piacere).
DanieleC88
20-04-2010, 09:03
Già. :)
Come se il mio interesse fosse rimasto fermo ai sistemi operativi da anni ed anni a questa parte. :)
Ti conviene leggere un buffer di dimensione pari ad un multiplo o un sottomultiplo dell'unità di allocazione minima del disco. Quindi 4096 byte dovrebbe essere perfetto.
Se trovi \0 nel file però è un po' complessa la cosa ;)
Mi spieghi questa cosa che non so perchè convenga?
Mi spieghi questa cosa che non so perchè convenga?
Perché così fai bufferizzare in modo efficiente il file dalla fread ;)
Sarebbe un'idea anche creare thread diversi, uno legge una quantità multipla della quantità di allocazione minima del disco che sia significativamente grande e la bufferizza, un altro thread inizia a elaborare il buffer.
Dite che si risparmia tempo?
Per adesso comunque ho finito il compressore e il decompressore che hanno un funzionamento abbastanza semplice.
Su file compresso sono tutti char ed i caratteri presenti consecutivamente per più di 255 volte vengono ripetuti.
Credo che al prof basti questo, adesso provo a fare qualche ottimizzazione, poi c'è una parte aggiuntiva che devo implementare.
Credo che al prof basti questo, adesso provo a fare qualche ottimizzazione, poi c'è una parte aggiuntiva che devo implementare.
E' moooolto difficile rispondere a questa domanda. Dipende anche dal sistema operativo. Fai prima a provare.
E' moooolto difficile rispondere a questa domanda. Dipende anche dal sistema operativo. Fai prima a provare.
Sono sotto cygwin, adesso comunque implemento la funzionalità supplementare così il progetto è finito, poi nel tempo rimanente spatacco con le ottimizzazioni.
Grazie a tutti dell'aiuto.
Ritiro su la discussione per chiedere una cosa senza stare a creare un altro 3d perchè dovrebbe essere una cosa da poco (che mi sta facendo perdere un sacco di tempo).
Non penso sia necessario riportare il codice, se mi dite che potrebbe servire lo posto in un secondo momento, ma se io ho una situazione del genere:
printf("qui ci arriva");
nuovoElemento = (struct elemento*)malloc(sizeof(struct elemento));
printf("qui non ci arriva");
Dove il primo printf viene stampato ma il secondo no, quale potrebbe essere il problema?
Il problema non dovrebbe essere che la memoria non è sufficiente perchè ne ho parecchia libera e non alloco niente di enorme (potrò occupare qualche kb al massimo con le variabili).
La situazione è questa:
quelle 3 righe di codice sono in una funzione che riceve una parola (vettore di char allocato dinamicamente); il programma crasha con parole di 120 lettere, funziona perfettamente con parole fino a 119 lettere.
Il problema è che non crasha quando invoca la funzione o quando metto la parola in nuovoElemento->parola, ma quando semplicemente faccio la malloc di nuovoElemento.
Mi sembra assurdo e non capisco cosa possa essere.
ps: i controlli sulla parola li ho fatti, ha il '\0' alla fine, è della lunghezza esatta e contiene quello che deve contenere.
Sembra un buffer overflow... Controlla che tutte le stringhe che usi abbiano spazio di memoria allocato e che lo spazio sia sufficiente (ricordati di mettere il carattere \0 in fondo alle stringhe).
Dopo aver usato printf devi anche usare l'istruzione fflush(stdout) (mi sembra si usi così). Se non lo fai il tuo printf viene messo nel buffer di stdout, e il programma crasha prima di scriverlo davvero.
L'ho scoperto facendo labProg pure io :D
Per me se metti fflush vedrai che scrive anche il secondo printf.
Stampa su stderr con fprintf. Non è bufferizzato come stdout e dovresti vedere il messaggio senza problemi.
fprintf(stderr, "messaggio");
Per oggi ho chiuso perchè stavo diventando cieco, domani provo.
Comunque mi dite che quindi non è lì l'errore ma più avanti anche se non vedo quel printf...proverò a capirci qualcosa.
Grazie.
Per oggi ho chiuso perchè stavo diventando cieco, domani provo.
Comunque mi dite che quindi non è lì l'errore ma più avanti anche se non vedo quel printf...proverò a capirci qualcosa.
Grazie.
Secondo me si, quasi sicuramente. Tra l'altro il metodo di Vicious (che non conoscevo, grazie) è molto più comodo del mio.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.