Algoritmo base di compressione dati LZW

Programmazione » Algoritmo base di compressione dati LZW
01/01/1970 - 18

Implementazione dell'algoritmo LZW in C/C++

---

Implementazione LZW in C++

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 nei più noti formati esistenti, è un algoritmo libero da brevetti da non molti anni per questo motivo la sua diffusione è ancora piuttosto limitata rispetto gli algoritmi basati su LZ77.

Il suo vantaggio principale rispetto altri algoritmi è che utilizza un dizionario che viene costruito man mano durante la lettura di un file/stream di dati.

Il principio di funzionamento di un algoritmo a dizionario è molto banale, consiste nel sostituire un insieme di simboli ricorrenti con 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.
Ad esempio utilizzando 16bit potremmo disporre di ben 65535 parole nel nostro nuovo dizionario compresso, più che sufficienti per comporre un SMS con un linguaggio semplice.

Il risparmio di questo algoritmo immaginario in termini di dati sarebbe notevole, infatti ogni parola potrebbe occupare anche 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 molto superiore 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.

Pseudo codice compressione

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
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 256 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 257, 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 258

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 256 (il valore del simbolo AB) il nuovo simbolo inserito nel dizionario è: ABE con valore 259 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.

Pseudo codice decompressione


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ò essere lunghissimo.

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, bisogna quindi implementarle.

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.


Vediamo bene le soluzioni ai problemi citati:

1)Per limitare lo spazio occupato dal dizionario si può conservare in memoria solamente una lista di coppie di variabili per ogni simbolo del dizionario esattamente una coppia prefisso/ultimo carattere, mentre il codice dell'item nel dizionario non sarà altro che l'indice dell'array utilizzato.
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 che potrebbe essere lungo quanto il dizionario stesso.
Nel primo passo di memorizzazione dell'esempio precedente l'inserimento del simbolo AB nel dizionario diventa qualcosa del tipo: prefisso 65 carattere B, indice dell'array 256.

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 può avere un notevole costo, 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.

Una soluzione ottimale consiste nello sfruttare al massimo la struttura 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 255 per via dei principi di funzionamento dell'algoritmo.
Si può aggiungere quindi un array di 255 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, il costo della ricerca con questa struttura sarebbe sempre pari a 1.
Tuttavia anche questa soluzione comporta un uso di memoria eccessivo, gli array di puntatori possono essere ridotti per creare delle linked list.

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 256, il valore da scrivere dovrà occupare solamente 9 Bit di memoria e non 16bit anche se 16bit è nel nostro caso 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 una grandezza di 9 bit fino a diventare di 16 bit in modo sequenziale in base alle dimensioni del dizionario raggiunte in ogni punto della compressione.
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 255 simboli, è consigliabile riservare un simbolo nel dizionario per indicare alla routine di decompressione 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 sempre benefici molto rilevanti senza analizzare a priori il file da comprimere.
Nell'implementazione allegata a questo articolo viene utilizzata la soluzione a.

Autore dell'articolo:
Ugo Cirmignani

Repository GitHub:
https://github.com/kingk85/lzw

Progetti che utilizzano questa implementazione:

Pack (creatore di archivi)

RawDisk(software a basso livello per dischi e pen drive)

---

---