Run-length encoding

Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Run-length encoding, in informatica, indica un algoritmo di compressione inventato per le immagini, utilizzato nei fax ben prima che le elaborazioni grafiche al computer fossero un'attività comune. L'RLE è una codifica senza perdita di informazioni (lossless), ovvero permette di comprimere e decomprimere senza alcuna perdita di informazione.

Solitamente si applica alle immagini e si fonda sull'assunto che l'immagine abbia pochi colori, ma può essere utilizzato su qualunque file dove si trovino lunghe sequenze dove lo stesso bit viene ripetuto. La compressione RLE viene spesso impiegata anche nei protocolli di rete (ad esempio, IBM SNA) o nei formati di dati di applicazioni in cui il tempo di elaborazione è critico (ad esempio, alcuni filmati AVI), perché è il formato che permette la maggior velocità di decompressione.

L'algoritmo di RLE cerca nei dati da comprimere una serie di elementi uguali (in un'immagine bitmap, essa corrisponde ad una campitura piatta), e la sostituisce con un solo elemento, quindi un carattere speciale e infine il numero di volte che esso va ripetuto. Per esempio supponiamo di avere un'immagine dove la prima riga è formata da cento pixel neri, il RLE memorizzerà il primo pixel nero poi metterà il carattere speciale e in seguito memorizzerà il numero 100. Così invece di occupare cento locazioni la prima riga ne occuperà solo 3. Il carattere speciale è definito diversamente da ogni implementazione dell'algoritmo, e serve a distinguere un elemento normale da uno compresso.

Questo algoritmo funziona bene in presenza di immagini con pochi colori molto uniformi, ovvero in serie di dati che abbiano molte ripetizioni al loro interno. Attualmente è utilizzato solo in alcune immagini bitmap; per esempio le bitmap utilizzate sui sistemi Microsoft possono essere compresse con RLE. Più precisamente, le primitive grafiche dei sistemi operativi Microsoft supportano tre tipi di compressione RLE:

• biCompression, Windows NT 3.51 e precedenti;
• bV4Compression, Windows 95 e Windows NT 4.0;
• bV5Compression, Windows 98/Me, Windows 2000 e successivi.

Immagini con molti colori non sono adatte a questo tipo di compressione ed esistono algoritmi molto più efficienti, come il PNG o il JPEG.

• Compressione dei dati
• Ridondanza spaziale nelle immagini

• (EN) run-length encoding, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica