Codifica run-length

La compressione RLE o la codifica Run-Lenght è una forma molto semplice di compressione dei dati in cui sequenze consecutive di dati con lo stesso valore vengono archiviate come un unico valore più il relativo conteggio. Questo è molto utile sui dati che contengono molte di queste "sequenze"; ad esempio, grafica semplice con aree di colore piatte, come icone e loghi .

Si consideri ad esempio uno schermo che contiene testo nero su sfondo bianco. Ci sarebbero molte di queste sequenze con pixel bianchi nei margini vuoti e altre sequenze di pixel neri nell'area di testo. Supponiamo una singola linea (o scanline ), con N che rappresenta le aree nere e B quelle bianche:

BBBBBBBBBBBBBBBBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

Se applichiamo la codifica run-length a questa riga, otterremmo quanto segue:

12B1N12B3N24B1N14B

Interpretato come 12 lettere B, 1 lettera N, 12 lettere B, 3 lettere N, ecc. Il codice run-length esegue il rendering dei 67 caratteri originali in soli 18. Ciò significa che la riga originale è di 67 byte e la stringa codificata è di soli 18 byte. Questa codifica tradotta in binary , il cui principio è lo stesso, viene utilizzata per la memorizzazione delle immagini. Anche i file di dati binari possono essere compressi utilizzando questo metodo. Il primo byte contiene un numero che rappresenta il numero di volte in cui il carattere viene ripetuto. Il secondo byte contiene il carattere stesso. Negli altri casi sono codificati in un unico byte: 1 bit (0 o 1) e 7 bit per specificare il numero di caratteri consecutivi.

Tuttavia, i sistemi di compressione più moderni utilizzano spesso l' algoritmo di deflazione o altri algoritmi basati su LZ77 , che hanno il vantaggio di utilizzare sequenze di stringhe .

Alcuni formati che utilizzano questa codifica includono Packbits , PCX e ILBM .

La codifica run-length esegue la compressione dei dati senza perdita di dati ed è ampiamente utilizzata su immagini indicizzate a 8 bit (era originariamente utilizzata per immagini in bianco e nero). Non funziona altrettanto bene su immagini a colori pixel costantemente variabili come fotografie, sebbene JPEG lo usi efficacemente sui coefficienti rimasti dopo aver trasformato e quantizzato blocchi di immagini. Successivamente ha costituito la base di altri sistemi di compressione come il gruppo CCITT 3 – 1D