Home » Tutte

Algoritmo base di compressione dati LZW - Un implementazione efficace dell'algoritmo LZW in C/C++ by Ugo Cirmignani

Descrizione implementazione ed esempio dell'algoritmo LZW in C/C++

In Programmazione - By kingk (art. no 18)



In questo articolo viene illustrato brevemente l'algoritmo LZW, vedremole insidie ed i consigli per una buona implementazione dell'algoritmo ed una sua buona implementazione in C/C++. Oltre al codice dimostrativo trovereteun piccolo software in C++ denominato 'FAC' dotato di interfaccia grafica questo software è capace di comprimere/decomprimere directory in vari formati tra cui LZW con il codice compreso in questo articolo, il software in questione utilizza un algoritmo di concatenamento file per comprimere intere directory in file unici.

Senza soffermarci troppo sulla storia di LZW passiamo a descrivere le caratteristiche principali dell'algoritmo:
-Algoritmo Loseless (nessuna perdita di informazioni con la compressione/decompressione dei files)
-Ottima velocità di compressione/decompressione
-Buon rapporto di compressione
-Principio di funzionamento basato su dizionario (infatti l'algoritmo è un evoluzione del primo noto algoritmo a dizionario: LZ77)
-Possibilità di comprimere dati in streaming senza conoscere i dati prima della compressione

LZW è attualmente utilizzato soprattutto nella compressione delle immagini dei più noti formati di immagini esistenti, è un algoritmo libero da brevetti da non molti anni per questo motivo la sua diffusione è ancora limitata.

L'algoritmo basa il suo funzionamento sul principio di utilizzare un dizionario che viene costruito man mano durante la lettura di un file/stream di dati.
Ma cosa significa utilizzare un dizionario per la compressione file?
Il principio di funzionamento è molto banale, consiste nel sostituire un insieme di simboli ricorrenticon simboli abbreviati nei dati di output.

Per fare un esempio di un algoritmo con dizionario possiamo immaginare di comprimere un SMS sostituendo le parole più utilizzate con dei numeri binari.
Ad esempio utilizzando 16bit potremmo disporre di ben 65535 parole nel nostro nuovo dizionario compresso, più che sufficienti per comporre un SMS.

Il risparmio di questo algoritmo immaginario in termini di dati sarebbe notevole, infatti ogni parola potrebbe occupare solo 2 simboli (in informatica ogni carattere di testo occupa 8bit), con una compressione del genere potremmo arrivare a comporre SMS con un numero di parole quintuplicato rispetto ad un SMS classico.

Sfortunatamente in informatica nella maggior parte dei casi bisogna lavorare con dei dati molto vari e non ricorsivi come delle semplici parole, trovare un algoritmo buono per molte casistiche non è un impresa da poco, ma è proprio quello che LZW garantisce.

Come funziona LZW?
L'algoritmo inizializza in memoria un dizionario di base composto da 256 simboli (tutti i valori che 1 byte può assumere).

L'algoritmo procede leggendo byte dopo byte tutti i dati in ingresso accodandoli tra loro in un buffer al fine di formare simboli finché tali simboli sono presenti nel dizionario e producendo nel caso contrario il valore della posizione occupata dall'ultimo simbolo riscontrato nel buffer come output. I simboli non riscontrati vengono inseriti nel dizionario in maniera dinamica.

Per comprendere meglio il processo prendiamo ad esempio una parola da comprimere formata da 11 caratteri: ABCABEFGHIL

Dopo la prima lettura il buffer in ingresso sarà formato da: A
Il carattere A è un simbolo presente nel dizionario dato che questo è stato inizializzato con tutti i 256 simboli ad 8 bit, se nella memoria di buffer è presente un simbolo riscontrabile nel dizionario l'algoritmo continua la lettura accodando i byte nuovi a quelli che formano il simbolo riscontrato nel buffer.
Nel secondo passaggio l'algoritmo legge B, ed il buffer diventa: AB

AB è un simbolo non presente nel dizionario dato che inizialmente è formato da simboli ad un carattere singolo, a questo punto l'algoritmo inserisce il nuovo simbolo mai riscontrato AB nella prima posizione disponibile nel dizionario ossia la posizione n 257 che conterrà quindi il simbolo AB.
Aggiunto questo simbolo l'algoritmo produrrà un output corrispondente alla posizione dell'ultimo simbolo riscontrato ossia il valore della posizione associato al carattere A precisamente: 65

L'algoritmo procede scartando il simbolo mandato in output dal buffer e accodando il nuovo byte da leggere all'ultimo letto, il buffer diventa cosi BC.
Il nuovo simbolo BC non è presente nel dizionario, l'algoritmo inserisce il nuovo simbolo BC nella posizione 258, come output restituisce sempre il valore della posizione dell'ultimo simbolo riscontrato in questo il valore 66 associato al simbolo B.

Il processo continua e il buffer diventa: CA ma anche il simbolo CA non è presente nel dizionario, l'algoritmo produce come output la posizione del simbolo C cioè : 67 e inserisce il nuovo simbolo CA nella posizione 259

Nel prossimo step il buffer diventa AB, AB è un simbolo presente nel dizionario, l'algoritmo non produce nessun output e continua con la lettura (la compressione ha cosi inizio).
Il buffer diventa quindi: ABE, questo simbolo non è presente nel dizionario in questo caso come output abbiamo 257 (il valore del simbolo AB) il nuovo simbolo inserito nel dizionario è: ABE con valore 260 ed il buffer diventa EF.

L'algoritmo procede in questo modo finché i dati in ingresso non terminano.

La decompressione avviene in modo del tutto analogo alla compressione, ma con qualche piccola differenza facilmente intuibile.

Dal punto di vista logico l'algoritmo è piuttosto semplice da comprendere, dal punto di vista pratico una sua implementazione presenta notevoli difficoltà tecniche:

1) L'uso di memoria deve essere ottimizzato all'interno del codice, bisogna trovare un sistema per memorizzare un dizionario molto vasto in poco spazio dato che è molto facile riempire la ram di un calcolatore con una cattiva implementazione di LZW.

2 ) La ricerca dei simboli nel dizionario deve essere ottimizzata altrimenti il tempo per comprimere dati può rendere l'algoritmo inutilizzabile

3 ) I simboli devono essere scritti in un formato con bit-size variabile a seconda delle dimensioni del dizionario durante la fase di compressione per massimizzare i benefici dell'algoritmo, i linguaggi di programmazione non consentono di scrivere dati in un numero di bit non multiplo di 8 con funzioni convenzionali.

4) Bisogna limitare le dimensioni del dizionario, in informatica la grandezza dei numeri non è illimitata

5) Bisogna resettare il dizionario quando questo diventa pieno o il rapporto di compressione diventa sconveniente, dato che durante la compressione con questo metodo il rapporto di compressione tende molto facilmente al degrado a seconda della porzione di dati da comprimere.

Ho trovato una soluzione per ognuno di questi puntinella mia implementazione dell'algoritmo presente in questo articolo,alcune soluzioni non sono state ottimizzate al 100% per questioni di tempo, ma tuttavia mi ritengo comunque molto soddisfatto di questa mia buona implementazione di LZW


Vediamo bene le soluzioni ai problemi citati:

1)Per limitare lo spazio occupato dal dizionario si può conservare in memoria solamente una lista di coppiedi variabili per ogni simbolo del dizionario esattamente una coppia prefisso/ultimo carattere. Si può notare che ogni nuovo simbolo da inserire nel dizionario non è altro che un vecchio simbolo presente nel dizionario con un ultimo carattere in più. Basta quindi memorizzare il valore del vecchio simbolo e il carattere che forma il nuovo simbolo e non memorizzare il nuovo simbolo per intero.
Nel primo passo di memorizzazione dell'esempio precedente l'inserimento del simbolo AB nel dizionario diventa qualcosa del tipo: prefisso 65 carattere B

2)In molte implementazioni di LZW per risolvere i problemi dei tempi di ricerca dei simboli all'interno del dizionario si utilizza un algoritmo di Hash per la ricerca, ma una soluzione simile comporta però molti svantaggi: L'algoritmo di Hash è un ulteriore complicazione all'interno di un codice non molto semplice, è difficile scrivere uno di questi algoritmi in modo perfetto, il costo di un algoritmo del genere poi non è pari a 1 ma può aumentare a seconda del tipo di dizionario che l'algoritmo crea in modo casuale, inoltre questo comporta un necessario incremento della memoria da dedicare al salvataggio del dizionario molte porzioni di memoria verranno sprecate a svantaggio delle capacità massime di compressione. Ho risolto questo puntoper l'implementazione di questo algoritmo con una soluzione davvero ottimale che garantisce ricerche ad un costo fisso di 1.
Una soluzione ottimale consiste nello sfruttare al massimo lastruttura ipotizzata per memorizzare il dizionario.
Possiamo notare che ogni elemento prefisso-carattere della nostra struttura verrà utilizzato per formare altri simboli del tipo prefisso/carattere+carattere secondo, il numero massimo di simboli derivati non sarà mai superiore a 256 per via dei principi di funzionamento dell'algoritmo.
Si può aggiungere quindi un array di 256 puntatori per ogni coppia prefisso-carattere, questi puntatori punteranno alle coppie derivate da quelle di origine. L'indice di questi puntatori verranno utilizzati con il carattere secondo.
Si può immaginare l'importanza di questa soluzione nella stesura di un implementazione.

3)Per massimizzare gli effetti della compressione bisogna memorizzare i valori dell'output utilizzando solo lo spazio necessario per memorizzarli. Questo significa che nel momento in cui nel dizionario viene aggiunto un simbolo con posizione 257, il valore dovrà occupare solamente 9 Bit di memoria e non 16bit anche se 16bit è la dimensione massima del dizionario, questo ovviamente finché il simbolo più grande del dizionario non avrà bisogno di più bit per la memorizzazione.
Il bit-size dovrà crescere in maniera dinamica a seconda della dimensione temporanea del dizionario, in un implementazione a 16 bit ad esempio il bit-size utilizzato dovrà partire da unagrandezza di 9 bit fino a diventare di 16 bit in modo sequenziale in base alle dimensioni del dizionario raggiunte in ogni punto della compressione.
Bisogna realizzare in qualche modo delle procedure per ottenere questo risultato, il metodo più semplice è quello di creare un buffer di bit e scrivere i byte solo quando il buffer diventa multiplo di 8.

4)Le dimensioni del dizionario devono essere definite, il miglior metodo è quello di dare un limite al dizionario in base ad un bit-size, in questo modo non ci saranno informazioni sprecate nell'output compresso. Questo significa che se ad esempio utilizziamo 14 bit il numero massimo di simboli nel dizionario sarà
(2^14) - 1 = 16383 simboli.




5)Per evitare che la compressione degradi una volta che il dizionario è pieno si possono adottare 2 strade:
a) Si resetta il dizionario per tornare alla situazione iniziale nella quale si dispone di 256 simboli, è consigliabile riservare un simbolo nel dizionario per indicare al decompressore che il dizionario a partire dal simbolo speciale è stato resettato
b) Si analizza il rapporto di compressione e si resetta il dizionario ogni qualvolta questo degrada, questa tecnica è più raffinata della prima ma non porta benefici molto rilevanti. Nell'implementazione allegata a questo articolo viene utilizzatala soluzione a.

Autore dell'articolo:
Ugo Cirmignani






LZW Implementation by Ugo Cirmignani

FAC (Fast Archive Creator)

Sorgenti Linux


Tags: LZW in C - Comprimere i dati in c - Algoritmo base di compressione dati LZW - Implementazione LZW in C - Realizzare software come winzip - Compressione LZW - Comprimere LZQ - Comprimere LZW