Qualche giorno fa, ispirato da una discussione avuta sul forum su questo algoritmo, mi è scattata la scimmia di scrivermi un piccolo programmino che lo usasse per comprimere testo ed immagini. Visto che l'ho finito ed è venuto bene perché non scriverne anche sul sito?
RLE è forse l'algoritmo di compressione dati senza perdita più semplice a cui si possa pensare. Si basa sull'idea che spesso all'interno dei file si trovano lunghe sequenze di simboli tutti uguali. L'algoritmo non fa altro che sostituire queste stringhe con una rappresentazione più corta da cui è poi possibile ricostruire quella originale durante la decompressione.
Supponete ad esempio di avere un piccolo file di testo.
AAAAAAAAABBCDDDDDD
L'algoritmo legge il file un byte per volta e codifica le varie sequenze con due byte. Il primo rappresenta il simbolo mentre il secondo indica il numero di ripetizioni. Una volta compresso il file conterrà l stringa seguente:
A9B2C1D6
Questo approccio ha però un grosso problema. Se si cerca di comprimere un normale file di testo questo diventa più grande invece di diminuire di dimensione. Capire il perché è piuttosto semplice. In quello che scriviamo normalmente è quasi impossibile trovare lunghe sequenze di simboli tutti uguali. Ci esprimiamo usando stringhe, parole, in cui i simboli, le lettere, si ripetono raramente e mai per pi di due o tre volte.
L'ideale sarebbe quindi poter scrivere il byte che rappresenta il numero di ripetizioni solo nei casi in cui ci sia un guadagno, cioè quando un simbolo è ripetuto più di due volte. Questo ci permettere di avere un file compresso in cui le stringhe "BB" e "C" sono lasciate invariate.
A9BBCD6
Ora però non possiamo più decomprimere il file perché non siamo in grado di distinguere tra le lettere ed il numero di ripetizioni. Prima, infatti, i byte pari contenevano sempre il simbolo mentre quelli dispari contenevano il contatore.
Esistono varie soluzioni a questo problema. Alcune più più semplici di altre. Quella che preferisco consiste nel far precedere un byte speciale che indichi quando la coppia (simbolo, contatore) sta cominciando. Ad esempio è possibile usare il carattere "#" ottenendo quindi.
#A9BBC#D6
In questo modo non abbiamo più problemi ma visto che ora le stringhe sono compresse con tre byte ha senso applicare la compressione solo quando un simbolo è ripetuto almeno quattro volte.
Se si decide di percorre la strada del byte di escape però si deve fare attenzione ad usarne uno che non sia possibile trovare normalmente all'interno dei file che andiamo a comprimere. Se questo non fosse possibile è necessario scrivere questi byte nel file compresso in modo che il decompressore non venga confuso e sia sempre in grado di ricostruire la sequenza originale.
Il modo più semplice consiste nello scrivere sempre e comunque la terna (escape,escape,contatore) sia che questo compaia una volta oppure che sia ripetuto. Le dimensioni del file finale aumentano di qualche byte perché ogni volta che si incontra una stringa composta da byte di escape di lunghezza minore a 3 questa viene compressa usandone tre.
Decidere il byte da usare come escape ha priori semplifica molto il codice ma in alcuni casi può portare a risultati disastrosi. Se per esempio si sceglie il NULL come escape e si comprime un file di testo non abbiamo problemi. Se però proviamo con una immagine bmp in cui compaiono molti punti e linee nere il file compresso avrà quasi sicuramente dimensioni di molto superiori al file originale. Questo succede perché il colore nero ed il NULL sono rappresentati allo stesso modo quando vengono scritti su file.
La cosa migliore è fare una prima scansione del file da comprimere e controllare quale byte è ripetuto il minor numero di volte e sceglierlo come escape. Così è possibile minimizzare l'overhead. Ci si deve poi ricordare di indicare ad inizio file quale byte usare come escape durante la decompressione.
In fine è interessante notare che il valore del contatore nel caso di normali simboli non può mai essere minore di 4 mentre per l'escape mai minore di 1. Se si modifica opportunamente il codice in modo che lo 0 sia interpretato come un 4 è possibile usare un singolo byte per comprimere sequenze di simboli più lunghe di quello che normalmente sarebbe possibile.
Codice sorgente
Potete scaricare il codice sorgente dei due programmini che ho scritto da GitHub.
http://github.com/mmacrelli/rle
Ma scusa che bisogno hai del carattere # se hai la stringa
A9BBCD6
puoi leggere un byte/carattere alla volta se questo è seguito
da un numero allora va ripetuto N volte altrimenti va solo
riscritto non capisco la difficoltà?
Forse non ho capito bene
Le lettere sono comunque codificate come numeri dal computer. Non hai modo di distinguere se si tratti di un numero che rappresenta un dato oppure quello che indica le ripetizioni perché non hanno posizioni prevedibili. Il carattere speciale serve ad indicare al programma quando sta cominciando una sequenza speciale.
Si logicamente se leggi i byte hai valori compresi tra 0-255 (2^8-1)ogni numero nell'intervallo corrisponde ad un carattere ASCII/UTF-8 o UNICODE ecc ma se tu hai un testo
222222A3CBBB
giustamente come hai precisato avresti questa stringa
62A3C3B
che decompressa sarebbe
222222ACCCBBB
ora ho capito cosa intendevi :)))
Ma secondo te non è stupido scaricare/archiviare file di dimensioni enormi che sono comunque formati da sequenze di numeri interi nell'intervallo 0-255?
O meglio conoscendo l'ordine della sequenza potrei rigenerare il file anziché
ricopiarlo....forse è una domanda stupida :(
File che contengono lunghe sequenze di simboli ripetuti che potrebbero essere compressi con questo semplice algoritmo sono estremamente rari. Anche se fossero comuni non penso che ne varrebbe la pena. Il processore dovrebbe comprimere/decomprimere i file ogni volta e si avrebbe una riduzione delle prestazioni generali del sistema.
Però pensa alla comodità del file sharing scarichi un file da 1Gb in 100mB e poi con calma lo decomprimi e decongestioni al tempo stesso la rete... non sarebbe male???
Quello che si scarica di solito con programmi p2p è già compresso con tecniche ben più avanzate di questa. Non credo si possa fare meglio di quello che già stanno facendo programmi come 7-zip e rar.