GUIDA AGLI ALGORITMI

Gli algoritmi LZ77 e LZSS
26/02/2003
Dark Schneider 2003

La compressione è uno degli argomenti più avanzati nel campo del rom hacking. Io stesso per ora non ne ho mai avuto a che fare, ma mi sono un pò documentato sulla rete. In particolare, ho trovato un paio di documenti abbastanza ben fatti su quelli che sono gli algoritmi più usati al giorno d'oggi. Basti pensare che l'algoritmo LZSS è alla base della compressione ZIP.

Questo documento non è quindi frutto di mie scoperte o invenzioni, ma una traduzione. In futuro cercherò di ampliare la guida con alcuni esempi pratici, focalizzando l'attenzione su un gioco psx del quale mi sono recentemente interessato...

Termini usati negli algoritmi

• Stream di Input: la sequenza di caratteri da comprimere (stream significa "flusso");

• Carattere: l'elemento di base nello stream di input;

• Posizione di codifica: la posizione del carattere (nello stream di input) che sta per essere codificato (l'inizio del lookahead buffer);

• Lookahead buffer: la sequenza di caratteri che va dalla posizione di codifica alla fine del flusso di input;

• La Finestra di dimensione W contiene W caratteri dalla posizione di codifica all'indietro, cioè gli ultimi W caratteri elaborati;

• Un Puntatore punta al match (un match si ha quando due sequenze di caratteri combaciano) nella finestra e specifica inoltre la lunghezza del match stesso.

1.1 LZ77: Il principio di codifica

L'algoritmo cerca nella finestra il match più lungo con l'inizio del lookahead buffer e ritorna un puntatore a quel match. Poichè è possibile che neanche un match di un carattere venga trovato, l'output potrebbe contenere soltanto puntatori. LZ77 risolve il problema in questo modo: dopo ogni puntatore ritornato, ritorna anche il primo carattere nel lookahead buffer dopo il match. Se non ci sono match, ritorna un puntatore nullo e il carattere alla posizione di codifica.

1.2 LZ77: L'algoritmo di codifica

1. Imposta la posizione di codifica all'inizio dello stream di input;

2. trova il match più lungo nella finestra con il lookahead buffer;

3. ritorna la coppia (P,C) con il seguente significato:

   • P è il puntatore al match nella finestra;

   • C è il primo carattere nel lookahead buffer che non matcha (non combacia);

4. se il lookahead buffer non è vuoto, sposta la posizione di codifica (e la finestra) L+1 caratteri in avanti e ritorna al passo 2.

1.3 LZ77: Un esempio

Il processo di codifica è presentato nella Tabella 1.

• La colonna Passo indica il numero di passi di codifica. Si completa ogni volta che l'algoritmo di codifica emette un output. Con LZ77 questo avviene in ogni passo dopo il passo 3.

• La colonna Pos indica la posizione di codifica. Il primo carattere nello stream di input ha posizione di codifica 1.

• La colonna Match mostra il match più lungo trovato nella finestra.

• La colonna Car mostra il primo carattere nel lookahead buffer dopo il match.

• La colonna Output presenta l'output nel formato (B,L) C:

  • (B,L) è il puntatore (P) al Match. Questo dà la sequente istruzione al decodificatore: "Torna indietro di B caratteri nella finestra e copia L caratteri nell'output";

  • C è il Carattere esplicito.

1.4 LZ77: Decodifica

La finestra è mantenuta allo stesso modo della codifica. In ogni passo l'algoritmo legge una coppia (P,C) dall'input. In output ritorna la sequenza della finestra specificata da P e il carattere C.

1.5 LZ77: Caratteristiche pratiche

Il rapporto di compressione ottenuto con questo metodo è molto buono per molti tipi di dati, ma il processo di codifica può essere abbastanza dispendioso per quanto riguarda il tempo, poichè sono molti i confronti tra il lookahead buffer e la finestra. D'altro canto, la decodifica è molto semplice e veloce. Le richieste di memoria sono basse sia per la codifica che per la decodifica. L'unica struttura dati tenuta in memoria è la finestra, che in genere ha dimensioni tra 4 e 64 kilobytes.

2.1 LZSS: Differenze con LZ77

L'algoritmo LZ77 risolve il caso di non-match nella finestra ritornando un carattere esplicito dopo ogni puntatore. Questa soluzione contiene ridondanze: è ridondante il puntatore nullo, o il carattere extra che potrebbe essere incluso nel prossimo match. L'algoritmo LZSS risolve il problema in maniera più efficiente: il puntatore è ritornato soltanto se punta ad un match più lungo del puntatore stesso; altrimenti, vengono ritornati caratteri espliciti. Dato che ora l'output contiene un miscuglio di puntatori e caratteri, ognuno di essi deve avere un bit identificatore in più che permette di distinguerli.

2.2 LZSS: L'algoritmo di codifica

1. Imposta la posizione di codifica all'inizio dello stream di input;
2. trova il match più lungo nella finestra con il lookahead buffer:
   • P := puntatore a questo match;
   • L := lunghezza del match;
3. è L >= LUNGHEZZA_MINIMA?
   • SI: ritorna P e muovi la posizione di codifica L caratteri in avanti;
   • NO: ritorna il primo carattere del lookahead buffer e muovi la posizione di codifica un carattere in avanti;
4. Se ci sono ancora caratteri nello stream di input, torna al passo 2.

2.3 LZSS: Un esempio

Il processo di codifica è presentato nella Tabella 2.

• La colonna Passo indica il numero del passo di codifica. Si completa ogni volta che l'algoritmo di codifica ritorna un output. Con LZSS questo succede in ogni passo oltre il terzo.

• La colonna Pos indica la posizione di codifica. Il primo carattere nello stream di input ha posizione di codifica 1.

• La colonna Match indica il match più lungo trovato nella finestra.

• La colonna Output mostra l'output, che può essere uno dei seguenti:

  • Un puntatore al Match, nel formato (B,L). Questo dà al decodificatore le seguenti istruzioni: "Torna indietro di B caratteri nella finestra e copia L caratteri nell'output";

  • Il Match stesso in forma esplicita (se è lungo soltanto un carattere, dato che LUNGHEZZA_MINIMA è impostata a 2).

2.4 LZSS: Decodifica

La finestra scorre sullo stream di output allo stesso modo in cui scorre sullo stream di input. I caratteri espliciti sono ritornati direttamente, e, quando viene incontrato un puntatore, viene ritornata la stringa della finestra che esso punta.

2.5 LZSS: Confronto di prestazioni con LZ77

Con questo algoritmo generalmente si ottiene un maggior rapporto di compressione di quanto si ottenga con LZ77, avendo praticamente gli stessi requisiti di processore e memoria. La decodifica è ancora estremamente semplice e veloce. Questo è il motivo per cui LZSS è diventato la base di quasi tutti gli algoritmi di questo tipo più recenti.

2.6 LZSS: Implementazioni

Praticamente è implementato in quasi tutti gli archiviatori più popolari: PKZip, ARJ, LHArc, ZOO, ecc. (al tempo in cui è stato scritto questo documento, questi erano i compressori più popolari...). Naturalmente ciascun archiviatore implementa l'algoritmo con alcune differenze, che vanno dalla lunghezza del puntatore, alle dimensioni della finestra, e così via.

Bene, questo conclude la guida. Spero di modificarne il titolo chiamandola "Gli algoritmi LZ77 e LZSS applicati al romhacking" in futuro...

Dark Schneider 2003