Algoritmi di compressione indice - Unary Code, Variable byte, Gamma codes, Group Variable Integer Code, Simple-9

Compressione dell'indice

Il nostro obiettivo è di ridurre lo spazio necessario per memorizzare ogni docID nelle postings list. NOTIAMO CHE: un termine come "aracnofobia" occorre meno volte in media del termine "il" che occupa davvero poco spazio e quindi, ad esempio, 20 bits per posting sono eccessivi. Osserviamo che i posting di termini molto frequenti sono molto vicini tra loro. L'idea chiave è che i gap tra i postings sono piccoli e richiedono quindi poco spazio per essere memorizzati. Infatti i gap di termini frequenti come "the" e "for" sono solitamente 1. Al contrario i gap di parole che compaiono poche volte nella collezione possono essere prossimi ai DocID che le contengono. Per una rappresentazione parsimoniosa della distribuzione di questi gaps, abbiamo bisogno di un metodo di encoding variabile che usi pochi bit per gaps piccoli. Variable lenght encoding: L'obiettivo è di memorizzare ogni gap (quindi)

un intero) con meno bit possibile per quel numero.

Unary Code

Consiste nel rappresentare un numero N come una lunghezza N di “uno” con uno 0 finale. Ad esempio 4 diventa 11110. Questo metodo non sembra promettente, ma possiamo usarlo come parte della nostra soluzione futura.

Variable byte (compressione a livello bytes)

Variable byte (VB) encoding usa un numero intero di byte per codificare un gap. Gli ultimi 7 bits del byte sono il "payload" e codificano parte del gap. Il primo bit del byte è un continuation bit. Viene impostato a 1 per denotare l'ultimo byte della codifica del gap, 0 altrimenti. Per decodificare un variable byte code, si leggono tutti i byte consecutivi con continuation bit pari a 0 e l'ultimo byte con continuation bit pari a 1. Quindi si estraggono e si concatenano le varie parti da 7 bits. L'idea del VB encoding può essere applicata anche a unità diverse: parole da 32-bits, 16-bits o 4-bits. Per la maggior parte dei

sistemi IR il variable bytecodes offre un eccellente trade-off tra tempo e spazio.

Gamma Codes (compressione a livello bits)

Byte o bits? Il Variable byte codes usa un numero variabile di byte in base alla dimensione del gap. I bit-level codes adattano la lunghezza della codifica a livello dei bits. La più semplice codifica a livello bit è lacodifica unaria.

La codifica gamma implementa una codifica a lunghezza variabile dividendo la rappresentazione di un gapin due, lunghezza e offset.

- L'offset viene rappresentato in binario ma eliminando l'uno più significativo.

- La lunghezza rappresenta la lunghezza dell'offset e viene codificata in unario.

Esempio: per il numero 13, la lunghezza dell'offset è 3, in unario 1110, il gamma code di 13 è quindi1110101, la concatenazione di lunghezza 1110 e dell'offset 101.

Per decodificare un gamma code si legge il codice unario fino allo 0 poi si leggono tanti bit quanta lalunghezza decodificata

In unario, si aggiunge un uno all'inizio della sequenza.

Proprietà → ⌊ → ⌋ bits e la lunghezza è diG è codificato usando 2*⌊ log G + 1 bits. Infatti, l'offset è log G2 2⌊ ⌋ +1 bits;log G2