[c] Run Lenght Encoding - suggerimenti per ottimizzazione

[-Ivan-]

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?

[Kenger]

Laboratorio di programmazione con D'Angelo eh? Buona fortuna.

[-Ivan-]

Originariamente inviato da Kenger

Laboratorio di programmazione con D'Angelo eh? Buona fortuna.

Eh già , 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]

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

[gugoXX]

Originariamente inviato da -Ivan-

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

[-Ivan-]

Originariamente inviato da gugoXX

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?

[gugoXX]

Originariamente inviato da -Ivan-

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

[Kenger]

Originariamente inviato da -Ivan-

Eh già , 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

Originariamente inviato da gugoXX

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

[-Ivan-]

Originariamente inviato da gugoXX

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!]

Edit: rimosso perché contrario al regolamento

[cionci]

!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]

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]

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!]

Originariamente inviato da cionci

!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

[cionci]

Originariamente inviato da cdimauro

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

[-Ivan-]

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.

[VICIUS]

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

[-Ivan-]

Originariamente inviato da VICIUS

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.

[cionci]

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

[VICIUS]

Originariamente inviato da -Ivan-

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.

Originariamente inviato da cionci

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.