IR - 05 - Compression II

Avevamo terminato la precedente lezione descrivendo come è possibile ridurre il numero di bits utilizzato per le posting lists andando a memorizzare solamente il gaps tra i docID piuttosto che il loro valore assoluto. Così facendo però nasce un nuovo problema, che consiste nel capire, leggendo la codifica dei numeri, quando un numero finisce e il prossimo numero inizia. Tale problema è affrontato nella seguente lezione, che tratterà di variable length encoding.

Le codifice bit level lavorano, come ci suggerisce il nome, con i singoli bit. Dal punto di vista teorico queste codifice sono quelle che permettono di ottenere i migliori risultati in termine di compressione. Dato però che le macchine moderne non sono ottimizzate per lavorare con i singoli bits, ma preferiscono invece lavorare sui bytes, queste codifiche non vengono utilizzate molto spesso in quanto nella pratica non sono poi così efficienti.

Andiamo quindi a descrivere un paio di codifiche che lavorano a livello dei bit.

Lo unary code, o codifica unaria, rappresenta il numero \(n\) con \(n\) ripetizioni del simbolo \(1\) seguito da uno 0 finale. Segue una tabella di conversione con qualche esempio.

\[\begin{array}{c |l} n & \text{unary code for } n \\ \hline 3 & 1110 \\ 5 & 111110 \\ 7 & 11111110 \\ 10 & 11111111110 \\ \end{array}\]

Il gamma code rappresenta una gap value \(G\) come una coppia \((\text{length}, \text{offset})\) in cui:

  • L'offset è rappresentato dal valore di \(G\) in binario. Dato che escludendo il caso \(G = 0\) il bit più significativo di \(G\) è sempre uguale a \(1\) per definizione, tale bit non viene memorizzato.

  • La lunghezza invece è la lunghezza sintattica dell'offset, ovvero il numero di bit necessari per esprimere l'offset una volta che abbiamo rimosso il bit più significativo. Tale lunghezza viene espressa tramite una codifica unaria.

Esempio: Se vogliamo trovare il codice gamma per il numero \(13\), dobbiamo effettuare i seguenti passaggi:

  1. Calcoliamo l'offset per \(13\).

    \[(13)_{10} \longrightarrow (1101)_2 \longrightarrow (101)_2\]

  2. Calcoliamo la lunghezza di \(101\), che è \(3\), ed è quindi codificata in unario come \(1110\).

Segue quindi che il codice gamma di \(13\) è

\[\Gamma(13) = (\text{length}, \text{offset}) = (1110, 101) = 1110101\]

Altri esempi di conversione sono riportati nella seguenta tabella.

\[\begin{array}{c |l} n & \text{gamma code for } n \\ \hline 0 & \text{none} \\ 1 & 0 \\ 5 & 11001 \\ 9 & 1110001 \\ 13 & 1110101 \\ \end{array}\]

Notiamo che tramite la codifica gamma siamo in grado di codificare un valore \(G\) utilizzando

\[2 \cdot \lfloor \log_2 G \rfloor + 1\]

bits, che vengono divisi in:

  • La lunghezza dell'offset, che è \(\log_2 G\) bits;

  • La lunghezza della lunghezza dell'offset è \(log_2 G + 1\) bits;

I gamma codes ci permettono quindi di avere una codifica a lunghezza variabile in modo estremamente efficiente, in quanto per codificare il numero \(G\) necessito almeno di \(\log_2 G\) bits.

Osservazione: Come abbiamo già menzionato prima, in pratica i codici gamma raramente funzionano in quanto le architetture moderne sono ottimizzate per fare operazioni su numeri a 32/64 bits. Lavorare al livello di bit è quindi poco performante.

Al posto di fare una codifica a livello di bits quindi siamo interessati a trovare una codifica a livello di bytes. In altre parole vogliamo codificare il numero \(G\) con il più piccolo numero di bytes.

Per risolvere questo problema è stato introdotto il concetto di continuation bit \(c\). Tale bit è utilizzato come segue:

  • Se \(G \leq 127\), allora posso codificare \(G\) utilizzando solamente i primi \(7\) bits di un byte. In questo caso quindi l'ultimo bit, ovvero quello più significativo, il continuation bit \(c\), viene settato a \(c = 1\).

  • Se \(G > 127\), allora codifico i \(7\) bits più piccoli di \(G\) nel primo byte, mentre il continuation bit del byte è settato a \(c = 0\). La restante parte di \(G\) viene codificata con altri bytes, seguendo lo stesso schema. L'ultimo byte sarà quindi il byte che ha il continuation bit \(c\) settato a \(1\).

Questa famiglia di codifica prende il nome di Variabile Bytes codes (VB codes).

Utilizzando questa codifica posso memorizzare le posting lists come sequenze di bytes. I VB codes, e alcune loro estensioni, sono i codici effettivamente utilizzati nella pratica.

Tipo di codifica utilizzata da Google.

L'idea è quella di codificare più di un numero con un solo byte. Il paper in cui è stata introdotta questa tecnica può essere trovato.