Utente:Hellis/Run-length encoding

L'algoritmo Run-length encoding (RLE) è uno dei primi algoritmi di compressione inventati. Viene utilizzato principalmente per memorizzare dati che contengono al loro interno molte ripetizioni.

L'idea che sta alla base dell'algoritmo è di individuare simboli che vengono ripetuti sequenzialmente all'interno del file e di sostituirli con una rappresentazione compatta, tipicamente il simbolo più il numero di ripetizioni.

Per esempio la stringa

"WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

codificata con l'algoritmo RLE diventerebbe:

12W1B12W3B24W1B14W

Quindi una stringa di 67 caratteri viene codificata con una stringa di 18 caratteri, portando una compressione di quasi il 75%.

Questo algoritmo mostra buone prestazioni in presenza di file con molte ripetizioni consecutive, questa condizione si verifica spesso nelle immagini con pochi colori. L'algoritmo ha inoltre due grandi vantaggio, è semplice da implementare e molto veloce nella codifica e nella decodifica dei file, difatti i primi formati grafici lo implementavano dato che i primi computer avevano pochi colori e non erano molto potenti quindi richiedevano degli algoritmi di compressione molto veloci.