Run-Length Encoding
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