Nell'algoritmo di Huffman (come in tutte le tecniche di compressione statistica), occorre prima analizzare il testo da comprimere per calcolare la probabilità (frequenza) di occorrenza di ogni singolo simbolo. La necessità di conoscere le proprietà del file da comprimere fa spesso preferire alla compressione statistica, la compressione mediante sostituzione.
In estrema sintesi la tecnica si compone di due fasi: nella prima fase, vengono cercate le stringhe (cioè le sequenze di caratteri) che si ripetono nel testo e viene definito un dizionario nel quale memorizzarle; a ogni stringa associato un indice.
Nella seconda fase, si cercano nel testo le stringhe ripetute e viene sostituito ad ognuna un puntatore alla locazione occupata nel dizionario. Il puntatore è in pratica un numero che identifica la stringa all'interno di un elenco di tutte le stringhe presenti nel testo. Il principio di compressione si basa sul presupposto che un puntatore occupa meno spazio di una stringa di caratteri, inoltre quanto maggiori saranno le ricorrenze di stringhe identiche, tanto maggiore sarà la compressione del file.
Per capire meglio i vantaggi offerti dalla tecnica di compressione mediante sostituzione, supponiamo di voler comprimere il seguente testo:
"sopra la panca la capra campa sotto la panca la capra crepa"
Il dizionario risultante dalla scansione è il seguente:
- sopra
- la
- panca
- capra
- campa
- sotto
- crepa
Si è associato a ciascuna parola un indice in relazione all’ordine con il quale le parole sono state memorizzate nel dizionario. Il testo risultante dalla compressione, ottenuta sostituendo alle parole del dizionario che compaiono nella frase, l'indice o puntatore, è in definitiva:
| sopra | la | panca | la | capra | campa | sotto | la | panca | la | capra | crepa |
| 1 | 2 | 3 | 2 | 4 | 5 | 6 | 2 | 3 | 2 | 4 | 7 |
La compressione mediante sostituzione è lossless, in quanto consente di ricostruire facilmente il testo originale sostituendo ai puntatori le stringhe corrispondenti e preservando quindi la natura stessa dell’informazione contenuta nel file.
L77 e L88 sono due algoritmi che sono alla base dei moderni metodi di compressione (per esempio quelli usati dal formato zip). I nomi derivano dall'iniziale del cognome di Abraham Lempel, uno degli informatici che per primo sviluppò questi codici.
L'idea è simile a quella dell'algoritmo per sostituzione, solo che invece di creare un dizionario contenente tutte le "parole" del codice, si sostituisce direttamente ogni parola con un riferimento alla sua precedente posizione nella stringa da codificare.
Nel caso in cui l'algoritmo incontri un dato ripetuto, questo viene sostituito con un puntatore formato da una coppia di dati lunghezza-distanza, il quale indica essenzialmente di copiare una certa lunghezza di dati presi da una certa distanza (prima del dato corrente). Sia l'algoritmo di codifica che quello di decodifica devono tenere traccia di una certa quantità di dati incontrati. Questa viene in genere chiamata finestra e per questa l'LZ77 viene anche denominato compressione a finestra.
Facciamo un semplice esempio considerando di nuovo la frase "sopra la panca la capra campa sotto la panca la capra crepa". In questo caso notiamo che la sequenza di caratteri "la panca la capra" è ripetuta due volte:
sopra la panca la capra campa sotto la panca la capra crepa
Possiamo dunque sostituire la seconda occorrenza di tale sequenza con un puntatore alla prima, in questo modo:
sopra la panca la capra campa sotto (17,30) crepa
dove (17,30) indica che in quella posizione devono essere copiati 17 caratteri "la panca la capra" partendo da 30 caratteri prima della posizione corrente.
Chiaramente l'algoritmo risulterà tanto più efficiente quanto maggiori saranno le ripetizioni di una data sequenza.
Sito realizzato in base al template offerto da
http://www.graphixmania.it
