Uno dei più studiati problemi in Computer Science è quello di gestire nella maniera più efficiente una sequenza di n interi. A prima vista sembrerebbe un problema di scarso interesse, puramente teorico: al contrario, la gestione efficiente di una sequenza di n interi, quindi di un insieme più o meno ordinato di chiavi, è fortemente sentita, ad esempio, nella gestione delle ricerche tramite inverted index.

Nel corso di questo articolo, descriverò una delle tecniche più utilizzate per questa indicizzazione: l’algoritmo di Elias Fano, sviluppato indipendentemente da Peter Elias e Roberto Fano negli anni ’70.

Descrizione algoritmo compressione

Data una sequenza di interi S(n,u) dove n è il numero di interi della sequenza e u è il valore massimo della sequenza, possiamo scrivere ogni intero della sequenza in |log2(u)| bit. La rappresentazione di ogni intero può essere poi divisa in due parti: una high part di |log2(n)| bits e una low-part di l=|log2(u) -log2(n)| = |log2(u/n)| bits.  Abbiamo quindi due vettori: un vettore di low-parts L [l1,l2,….ln] che occupa n*|log2(u/n)| bits; un vettore di high bits H nel quale ciascun elemento viene rappresentato in negated unary coding seguendo il seguente procedimento:

• inseriamo tanti “0” quanti sono i possibili valori binari dei |log2(n)| bits, quindi n. L’ n-esimo “0” può essere indicato come stop bit per ciascuno dei possibili valori binari.
• leggendo in maniera ordinata la sequenza codificata in bit, settiamo nel vettore H il valore 1 in posizione h(i)+i, dove h(i) è il valore in intero della parte high corrispondente all’i-esimo intero.
• In questo modo il vettore H avrà 2n bits: n bits sono relativi agli stop bits e n agli “1” che rappresentano la sequenza.

Quindi, in pseudo codice, l’algoritmo è il seguente:

S := {S0,S1,…,Sn-1}

n:= len(S)

u = Sn-1

lowerBits={}

higherBits={2n}

for i = 0,…, 2n-1 do

  higherBits[i] = 0;

for i = 0,…, n-1 do

lowerBits[i] = li

higherBits[hi+1] = 1

Complessità

Lo spazio occupato per tale struttura è quindi 2n+n*(log2(u/n)) bits. 2n è infatti lo spazio del vettore High, mentre log2(u/n)*n è lo spazio del vettore Low. E’ un ottimo risultato, in quanto il lower bound per la complessità spaziale di un bit vector b(n,u) – vale a dire una sequenza di bit di lunghezza ncon u bits settati ad 1 – è n*log2(u/n)+O(n). Dal momento che la complessità spaziale è vicina al teorico lower bound, la struttura Elias Fano è inclusa in quelle che vengono definite quasi succint index

Esempio.

Consideriamo la sequenza ordinata 2,3,5,7,11,13,24. Essendo la sequenza lunga 7 e il numero massimo 24, ogni intero decodificato ha: una high part di |log2(7)|=3 bits e una low part di |log2(24)| – |log2(7)| = 5-3 =2 bits.

• 2 = 000 10
• 3 = 000 11
• 5 = 001 10
• 7 = 001 11
• 11 = 010 11
• 13 = 011 01
• 24 = 110 00

Il vettore di lowbits è il seguente: 10111011110100, vale a dire la concatenazione dei low bits dei singoli elementi della sequenza. Il vettore di high bits, invece, si ottiene in questo modo:

• si parte da un vettore di 2*7 bits settati a zero 00000000000000
• si esamina il primo high bit, pari a 000 e si setta 1 al valore 0 (hi+i: 0+0): 10000000000000
• si esamina il secondo high bit, pari a 000 e si setta 1 al valore 1 (hi+i: 0+1): 11000000000000
• si esamina il terzo high bit, pari a 001 e si setta 1 al valore 3 (hi+i: 1+2): 11010000000000

…così fino ad arrivare a 11011010100010