[Salta il menu][L'elefantino con la matita, logo del sito]

Diodati.org | Accessibilità e traduzioni dal W3C      Leggi Omega Centauri!

05 L'algoritmo RLE (Run Lenght Encoding)

Proviamo ora a vedere come funziona un sistema di compressione non distruttivo, tuttora diffuso, noto con la sigla RLE, acronimo di Run Lenght Encoding, che potremmo rendere in italiano con codifica della lunghezza di stringa. In questo tipo di compressione, ogni serie ripetuta di caratteri (o run, in inglese) viene codificata usando solo due byte: il primo è utilizzato come contatore, e serve per memorizzare quanto è lunga la stringa; il secondo contiene invece l'elemento ripetitivo che costituisce la stringa.

Immaginate ora di comprimere in questo formato un file grafico contenente un grande sfondo di un solo colore uniforme. Tutte le volte che l'analisi sequenziale del file s'imbatterà in stringhe di caratteri uguali, e ciò accadrà spesso nella scansione dello sfondo omogeneo, le serie ripetitive potranno essere ridotte a due caratteri soltanto: uno che esprime il numero delle ripetizioni, il secondo il valore che si ripete. E il risparmio di spazio sarà direttamente proporzionale al livello di uniformità presente nell'immagine.

Provate ora, invece, ad usare il sistema RLE su una foto piena di colori differenti e di transizioni sfumate: il risparmio di spazio sarà molto minore, perché poche saranno le stringhe di ripetizioni che l'algoritmo riuscirà a trovare leggendo sequenzialmente il file.

Pensate, infine, al caso limite di un'immagine creata artificialmente, come quella riportata qui sotto, contenente una serie di pixel tutti differenti l'uno dall'altro nei valori cromatici. In questo caso, l'uso della compressione RLE si dimostra addirittura controproducente.

Fig.1 – Immagine ingrandita di un file di 16 x 16 pixel, costituito da 256 colori unici differenti

Questo file, salvato in formato BMP non compresso, occupa 822 byte. Salvato invece sempre in formato BMP, ma utilizzando l'algoritmo RLE, occupa 1400 byte, cioè 1,7 volte la sua grandezza originale.

*Leggi: L'algoritmo Huffman
*Vai a: Diodati.org > Guide, articoli, scritti > Algoritmi di compressione...
*Scrivi: info@diodati.org
*Ultima modifica: 15/7/2004 ore 14:18