LZSS + SHANNON FANO
Gianluca Costante & Alessio Scannapieco
Introduzione
Analisi iniziale
Suddivisione compiti
Comprensione algoritmi
Implementazione
LZSS
Shannon Fano
Analisi finale
Esecuzione test
Ottimizzazione
Analisi Iniziale
Suddivisione dei compiti
LZSS: Gianluca Costante
Shannon Fano: Alessio Scannapieco
L’ouput di LZSS sarà utilizzato da Shannon Fano come
input, in modo da sfruttare la ripetizione delle terne
LZSS – Intro
Lempel-Ziv-Storer-Szymanski
PCZip, ARJ, LHArc, ZOO
Miglioramento LZ77
no-match: 0 CHAR
match: 1 (length, offset)
LZSS –Codifica
1.
Imposta la posizione di codifica all’inizio dello stream di input
2.
Leggi una quantità MAX_MATCH di caratteri
3.
Trova il match più lungo nella finestra con il lookahead buffer:
•
P := puntatore al match
•
L := lunghezza del match
4.
È L >= LUNGHEZZA_MINIMA
•
SI: ritorna P e muovi la posizione di codifica L caratteri avanti
•
NO: ritorna il primo carattere del lookahead buffer e muovi la posizione di
codifica di un carattere avanti
5.
Se ci sono ancora caratteri nello stream di input, torna al passo 2
LZSS - Esempio
POS
1
2
3
4
5
6
7
8
9
10
11
CAR A
A
B
B
C
B
B
A
A
B
C
PASSO
POS
MATCH
OUTPUT
1
1
--
A
2
2
A
A
3
3
--
B
4
4
B
B
5
5
--
C
6
6
BB
(3. 2)
7
8
AAB
(7, 3)
8
11
C
C
LUNGHEZZA_MINIMA = 2
Implementazione - LZSS
Scelte compiute
Lettura a byte
Match massimo: 15 (4 bit => length)
Sliding-window: 4096 simboli (12 bit => offset)
Implementazione - LZSS
Problemi riscontrati
Compressione
Ricerca del match massimo nella sliding-window
Scrittura bits
Posizione flags
Decompressione
Lettura bits
Bits spuri alla fine del file compresso
Implementazione - LZSS
Problemi risolti
Compressione
Ricerca del match massimo => Bruteforce
Scrittura bits => Maschere
Decompressione
Lettura bits => Maschere
Implementazione - LZSS
Problemi aperti
Compressione
Posizione flags => (8 flags e 8 terne/caratteri)
Decompressione
Bits spuri alla fine del file compresso => (Sequenza finale)
Implementazione - LZSS
Strutture dati
Scelte:
Buffer di caratteri per la lettura di file
Struct per gestione terne
Array per sliding-window e lookahead buffer
Implementazione - LZSS
Sviluppi futuri
Compressione
Ricerca del match massimo => Liste? Hash?
Scrittura bits => Libreria bitfile
Decompressione
Lettura bits => Libreria bitfile
Implementazione – Shannon Fano
Problemi riscontrati
Compressione
Generazione albero ricorrenze
Bits spuri a fine file
Implementazione – Shannon Fano
Problemi risolti
Compressione
Generazione albero ricorrenze => Liste
Bits spuri a fine file => Informazioni nell’header
Implementazione – Shannon Fano
Strutture dati
Scelte:
Puntatori per Alberi e Liste
Array per conteggio simboli
Array per ordinamento in base alla frequenza
Array algoritmo generazione Albero
Implementazione – Shannon Fano
Sviluppi futuri
Decompressione
LZSS + SHANNON FANO
Gianluca Costante & Alessio Scannapieco
Beta - LZSS
Scelte finali
Sliding-window => variabile
Match massimo => variabile
Compressione
Ricerca match => bruteforce
Scrittura bits => Libreria bitfile
Posizione flags => pacchetto da 1 byte
Decompressione
Lettura bits => Libreria bitfile
Bits spuri => Sequenza finale
Analisi finale - LZSS
OFFSET_BITS = 8
LENGTH_BITS = 4
File
Dim.
Tempo
% Compressione
JPG
129 KB
0.163 s
-11.987 %
TEXT
3.7 MB
0.480 s
32.347 %
BMP
778 KB
0.241 s
35.265 %
EXCEL
50 KB
0.297 s
5.409 %
PDF
5.4 MB
6.592 s
-6.784 %
MEMORIA = 28 + 24 = 272 bytes
Analisi finale - LZSS
OFFSET_BITS = 8
LENGTH_BITS = 8
File
Dim.
Tempo
% Compressione
JPG
129 KB
0.182 s
-12.340 %
TEXT
3.7 MB
0.550 s
16.950 %
BMP
778 KB
0.524 s
32.359 %
EXCEL
50 KB
0.352 s
6.017 %
PDF
5.4 MB
6.549 s
-7.225 %
MEMORIA = 28 + 28 = 512 bytes
Analisi finale - LZSS
OFFSET_BITS = 12
LENGTH_BITS = 4
File
Dim.
Tempo
% Compressione
JPG
129 KB
2.376 s
-11.406 %
TEXT
3.7 MB
1.254 s
65.660 %
BMP
778 KB
3.471 s
54.839 %
EXCEL
50 KB
1.742 s
5.571 %
PDF
5.4 MB
91.124 s
-3.510 %
MEMORIA = 212 + 24 = 4112 bytes
Analisi finale - LZSS
OFFSET_BITS = 12
LENGTH_BITS = 8
File
Dim.
Tempo
% Compressione
JPG
129 KB
2.323 s
-15.169 %
TEXT
3.7 MB
1.249 s
57.954 %
BMP
778 KB
3.192 s
55.943 %
EXCEL
50 KB
1.508 s
7.612 %
PDF
5.4 MB
90.276 s
-6.904 %
MEMORIA = 212 + 28 = 4352 bytes
Analisi finale - LZSS
OFFSET_BITS = 12
LENGTH_BITS = 12
File
Dim.
Tempo
% Compressione
JPG
129 KB
2.552 s
-18.936 %
TEXT
3.7 MB
1.169 s
50.040 %
BMP
778 KB
3.564 s
49.634 %
EXCEL
50 KB
2.497 s
3.012 %
PDF
5.4 MB
99.218 s
-10.218 %
MEMORIA = 212 + 212 = 8192 bytes
Analisi finale - LZSS
Fattori importanti
Scelta della dimensione di offset e length
Dipende molto dalla tipologia di file
Algoritmo di ricerca in finestra
Bruteforce non efficiente, caso peggiore: 2bit_offset
Ottimizzazione - LZSS
Utilizzo dell’algoritmo Knuth-Morris-Pratt
OFFSET_BITS = 12
LENGTH_BITS = 4
File
Dim.
Tempo
% Compressione
JPG
129 KB
1.708 s
-11.406 %
TEXT
3.7 MB
0.873 s
65.660 %
BMP
778 KB
2.547 s
54.839 %
EXCEL
50 KB
0.438 s
5.116 %
PDF
5.4 MB
66.938 s
-3.510 %
MEMORIA = 212 + 24 = 4112 bytes
Closed Beta - ShannonFanoC
Shannon Fano Canonico
Facilita la decodifica
Informazioni dell’header
Lunghezza codici (0 a 255)
Bit da leggere dall’ultimo byte (256esimo)
Closed Beta – ShannonFanoC
Header di esempio
Closed Beta - ShannonFanoC
Problematiche
newline
Differenze sostanziali in quantità di peso per certi tipi di
file
.bmp, certi si, certi no
Altri tipi di file
Closed Beta - ShannonFanoC
Problematiche
newline
File .txt
Differenze sostanziali in quantità di peso per certi tipi di
file
Fase di debug
.bmp, certi si, certi no
Dovuto ad un errore di codifica o decodifica
Altri tipi di file
Analizzare l’output
Closed Beta – ShannonFanoC
DEMO
File di testo (text11.txt)
BMP funzionante (ImmagineTest.bmp)
Closed Beta – ShannonFanoC
Prossima fase
Risolvere le problematiche
Ottimizzare il programma
Documentare il codice
Grazie per l’attenzione