Run-length encoding: differenze tra le versioni

Versione delle 14:26, 24 ago 2005

Versione attuale delle 14:00, 16 ago 2022

(44 versioni intermedie di 34 utenti non mostrate)

Riga 1:

{{F|programmazione|settembre 2010}}

{{da cancellare}}

[[en:'''Run-length encoding]]''',

in [[informatica]], indica un [[algoritmo]] di [[Compressione dei dati|compressione]] inventato per le [[immagine digitale|immagini]], utilizzato nei [[fax]] ben prima che le elaborazioni grafiche al [[computer]] fossero un'attività comune. L'RLE è una codifica [[Compressione dati senza perdita|senza perdita di informazioni]] (''lossless''), ovvero permette di comprimere e decomprimere senza alcuna perdita di [[informazione]].

==Descrizione==

In [[informatica]], l'[[algoritmo]] '''Run Length Encoding''' ('''RLE''') è storicamente il primo algoritmo di [[compressione]] per le immagini inventato. Solitamente si applica alle immagini e si fonda su l'assunto che l'immagine abbia pochi colori, ma può essere utilizzato su qualunque file dove si trovino lunghe sequenze dove lo stesso [[byte]] viene ripetuto.

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 [[protocollo di rete|protocolli di rete]] (ad esempio, [[IBM]] [[Systems Network Architecture|SNA]]) o nei formati di dati di applicazioni in cui il tempo di elaborazione è critico (ad esempio, alcuni filmati [[Audio Video Interleave|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 campionatura 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.

L'algoritmo di RLE cerca nei dati da comprimere una serie di elementi uguali (in un'immagine [[bitmap]], essa corrisponde ad una campionatura[[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 [[implementare|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. Immagini con molti colori non sono adatte a questo tipo di compressione ed esistono algoritmi molto più efficienti, come il [[Portable Network Graphics|PNG]] o il [[Joint Photographic Experts Group|JPEG]].

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. Immagini con molti colori non sono adatte a questo tipo di compressione ed esistono algoritmi molto più efficienti, come il [[Portable Network Graphics|PNG]] o il [[Joint Photographic Experts Group|JPEG]].

[[categoria:Algoritmi]]

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 [[Portable Network Graphics|PNG]] o il [[Joint Photographic Experts Group|JPEG]].

[[de:Lauflängenkodierung]]

[[en:Run-length encoding]]

== Voci correlate ==

[[fr:Run-length encoding]]

* [[Compressione dei dati]]

[[ja:連長圧縮]]

* [[Ridondanza spaziale nelle immagini]]

[[nl:Run-length encoding]]

[[pl:RLE]]

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Metodi di compressione}}

{{Portale|informatica}}

[[Categoria:Algoritmi di compressione]]

[[Categoria:Compressione dei dati]]

[[Categoria:Elaborazione digitale delle immagini]]