Codifica e decodifica con l'algoritmo Ziv-Lempel

Cari amici, dato che ho notato che il libro di Sandro Bellini non spiega l'algoritmo di Ziv-Lempel, e il libro in inglese di David Mac Kay (Information Theory, Inference, and Learning Algorithms) lo spiega in modo esauriente ma con pochi esempi, ho provato a fare un piccolo riassunto di come funziona l'algoritmo e, in particolare, vedere esempi concreti di codifica e decodifica.

ALGORITMO ZIV-LEMPEL

Il metodo di compressione consiste nel rimpiazzare una sottostringa con un puntatore ad una precedente occorrenza della stessa sottostringa.
Se la stringa è ad esempio 1011010100010. . . , la si divide in un dizionario ordinato di sottostringe che non sono comparse fino a quel momento nel modo seguente: (elemento vuoto espresso col simbolo lambda), 1, 0, 11, 01, 010, 00, 10,..
Dopo ogni separazione, viene considerata la parte della sequenza di input mancante fino a che non viene letta una sottostringa che non è stata ancora inserita nel "dizionario".
E' facile accorgersi del fatto che questa sottostringa è più lunga di 1 bit di un'altra precedentemente inserita nel dizionario: per questo motivo si può codificare ogni sottostringa fornendo un puntatore all'occorrenza della precedente sottostringa e quindi mandando il bit "extra" per il quale la nuova sottostringa nel dizionario differisce dalla precedente.
Se, al bit n-esimo, sono state enumerate s(n) sottostringhe, si può fornire il valore del puntatore con il primo intero maggiore o uguale a log2(s(n)) bit (logaritmo in base 2 di s(n)).

CODIFICA

Proviamo a codificare (separati nel momento in cui vengono incontrati per la prima volta):

1 0 11 01 010 00 10

I passi espliciti che l'algoritmo compie sono:

- Per prima cosa viene "incontrata" la sottostringa nulla, espressa col simbolo lambda (non so come scriverlo :P), che ha come s(n) 0, e la coppia (puntatore,bit) è nulla.
- Quindi viene incontrata per la prima volta la sottostringa 1, che ha come s(n) 1, pertanto il puntatore deve essere espresso con log(s(n)) (in base 2) = 0 bit, e il bit "extra" per cui la sequenza differisce da quella puntata (sequenza nulla) è 1. percui la coppia (puntatore,bit) è (,1).
- Viene incontrata la sequenza 0 : è facile accorgersi come tale sequenza possa espressa come la sequenza nulla con s(n)=0 e dal bit aggiuntivo 0. Dal momento che s(n)=2 il puntatore può essere espresso con log2=1 bit. La coppia (puntatore,bit) è dunque (0,0)
- Viene incontrata la sequenza 11 : si nota come tale sequenza possa espressa come la sequenza avente s(n)=1 (1) e dal bit aggiuntivo 1. Dal momento che s(n)=3 il puntatore può essere espresso con l'intero suepriore a log3, cioè 2 bit. La coppia (puntatore,bit) è dunque (01,1).
- Viene incontrata la sequenza 01 : si nota come tale sequenza possa espressa come la sequenza avente s(n)=2 (0) e dal bit aggiuntivo 1. Dal momento che s(n)=4 il puntatore può essere espresso con log4, cioè 2 bit. La coppia (puntatore,bit) è dunque (10,1).
- Viene incontrata la sequenza 010 : si nota come tale sequenza possa espressa come la sequenza precedentemente incontrata avente s(n)=4 (01) e dal bit aggiuntivo 0. Dal momento che s(n)=5 il puntatore può essere espresso con l'intero immediatamente superiore a log5, cioè 3 bit. La coppia (puntatore,bit) è dunque (100,0).
- Viene incontrata la sequenza 00 : si nota come tale sequenza possa espressa come la sequenza avente s(n)=2 (0) e dal bit aggiuntivo 0. Dal momento che s(n)=6 il puntatore può essere espresso con l'intero immediatamente superiore a log6, cioè 3 bit. La coppia (puntatore,bit) è dunque (010,0).
- Viene incontrata la sequenza 10 : si nota come tale sequenza possa espressa come la sequenza avente s(n)=1 (1) e dal bit aggiuntivo 0. Dal momento che s(n)=7 il puntatore può essere espresso con l'intero immediatamente superiore a log7, cioè 3 bit. La coppia (puntatore,bit) è dunque (001,0).
(scusate ma sono incasinati gli allineamenti...)


sottostringhe lambda 1 0 11 01 010 00 10
s(n) 0 1 2 3 4 5 6 6 7
s(n)binario 000 001 010 011 100 101 110 111
(puntatore,bit) (,1)(0,0) (01,1) (10,1) (100,0) (010,0)(001,0)



Per quanto riguarda l'operazione di decodifica bisogna compiere l'operazione contraria, cioè separare il codice in base alla logica per cui in posizione s(n) ci sarà una coppia (puntatore,bit) in cui il puntatore sarà espresso con un numero di bit equivalente all'intero immediatamente superiore o uguale log(in base 2) (s(n)) bit.
Utilizzando una tabella come quella vista sopra si può svolgere l'operazione in modo abbastanza facile e veloce.

una piccola precisazione... quando si scrive il puntatore ad una sequenza precedente, e si dice che va espresso in n bit, ovviamente si intende anche che sia espresso in forma binaria.
Se ad esempio la sequenza s(n)=4 equivale alla sequenza s(n)=3 a cui è aggiunto come bit extra 1, avverrà che:

il puntatore deve essere espresso con log4 (logaritmo in base 2) = 2 bit, e deve puntare a s(n)=3, che in forma binaria è 11.
Pertanto la coppia (puntatore,bit) sarà (11,1).