Implementazione LZSS
Programmazione » Implementazione lzss
12/10/2012 - 367
Implementazione dell'algoritmo di compressione dati LZSS
Un implementazione dell'algoritmo LZSS
L'algoritmo
LZSS è un evoluzione dell'algoritmo di compressione dati
LZ77, il suo funzionamento è molto semplice, consiste nel sostituire parti di dati già incontrati con una coppia distanza e lunghezza rispetto la posizione attuale del cursore.
In questo algoritmo vengono utilizzati due buffer, uno contenente i dati da trattare e un altro buffer chiamato finestra contenente i dati già trattati, l'algoritmo ricerca per ogni stringa da trattare una corrispondenza nei dati già trattati nel caso di successo produce come output un indirizzo e una lunghezza al fine di far individuare al decompressore una stringa da ricopiare dal buffer dei dati già trattati altrimenti mette in output i dati senza comprimerli.
Per rendere possibile la decodifica il codificatore stampa anche due identificatori della grandezza di un solo bit: 0 oppure 1 per indicare se vi è un byte non comrpesso oppure una coppia indirizzo lunghezza.
Il decodificatore se riscontra una coppia indirizzo lunghezza non farà altro che ricopiare i dati già trattati a partire dall'indirizzo letto per la lunghezza indicata, altrimenti in caso contrario copierà semplicemente il byte dopo il bit 0.
Vediamo un esempio per comprendere meglio il funzionamento, stringa da comprimere
ABCDABCEABCDABC
1 | OUTPUT bit 0 A | BUFFER TRATTATO A | DA TRATTARE BCDABCEABCDABC
2 | OUTPUT bit 0 B | BUFFER TRATTATO AB | DA TRATTARE CDABCEABCDABC
3 | OUTPUT bit 0 C | BUFFER TRATTATO ABC | DA TRATTARE DABCEABCDABC
4 | OUTPUT bit 0 D | BUFFER TRATTATO ABCD | DA TRATTARE ABCEABCDABC
5 | OUTPUT bit 1 Indirizzo 0, lunghezza 3 | BUFFER TRATTATO ABCDABC | DA TRATTARE EABCDABC
6 | OUTPUT bit 0 E | BUFFER TRATTATO ABCDABCE | DA TRATTARE ABCDABC
7 | OUTPUT bit 1 Indirizzo 0, lunghezza 7 | | BUFFER TRATTATO ABCDABCEABCDABC | DA TRATTARE ''
Output finale: 0A 0B 0C 0D 1[0,3] 0E 1[0,7]
Le dimensioni della finestra (o buffer già trattato) devono necessariamente avere un limite, in sostanza per due motivi:
-Gli indirizzi per buffer troppo lunghi potrebbero far aumentare le dimensioni del file compresso degradando il livello di compressione, per ovviare a questo problema si dovrebbe quindi innalzare il numero di caratteri minimi per la compressione ma tuttavia in questo caso le prestazioni del compressore degraderebbero in maniera significativa, bisogna quindi trovare un giusto compromesso tra rapporto di compressione e velocità.
-I computer hanno una memoria limitata, la finestra non può essere quindi infinita e soprattutto bisognerebbe dimensionarla in modo tale da rendere il codice portabile anche su sistemi dotati di scarse risorse (CPU e RAM).
Per ovviare a questi problemi basta implementare una coda FIFO per il buffer dati già trattati scartando ad ogni lettura l'ultimo byte letto, e inserendo il nuovo in cima alla coda.
Scrivendo l'indirizzo si consiglia di indicare la distanza rispetto alla stringa precedente piuttosto che l'index della fifo iniziando a cercare la miglior corrispondenza a partire dalla prima posizione, questo accorgimento è molto utile per rendere gli indirizzi facilmente comprimibili come ad esempio con altri algoritmi di compressione come Huffman.
Ulteriori informazioni sul funzionamento
Durante la ricerca della stringa da trattare nella finestra bisogna cercare la miglior corrispondenza al fine di massimizzare la compressione, si consiglia però di limitare la ricerca delle corrispondenze per non rendere l'algoritmo troppo lento.
Dettagli dell'implementazione di LZSS
-Buffer dati trattati di 65535 bytes 16 bit
-Ricerca nel buffer tramite hash table
-Bit identificatori scritti a gruppi di 8 in anticipo al fine di evitare la scrittura dati con numero bit diverso da 8
-Lunghezza minima della parola di 4 byte
-Lunghezza massima della parola di 259 byte
Questa versione di
LZSS utilizza un algoritmo di Hash perfetto al fine di minimizzare l'uso di
CPU, questo accorgimento tecnico non lo rende adatto a computer con scarsa disponibilità di memoria RAM, in realtà la scelta è stata effettuata al fine di semplificare il codice.
L'algoritmo di hash potrebbe essere modificato con un minimo impatto nel codice.
Questo algoritmo riesce ad individuare una sequenza di 3 byte tramite la funzione:
F(h) = ((((HASH+byte n1) LeftShift 8)+byte n2) LeftShift 8) + byte n3
NB: Questa implementazione è da ritenersi per puro scopo educativo, l'uso di memoria la velocità non sono ottimizzate.
