Set codificati Golomb: più piccoli dei filtri Bloom

Mentre leggevo l’interessantissimo Imperial Violet, il blog di Adam Langley, mi sono imbattuto in una nuova struttura dati di cui non avevo mai sentito parlare: i set codificati Golomb (GCS).

Si tratta di una struttura dati probabilistica concettualmente simile ai famosi filtri Bloom, ma con una rappresentazione in memoria più compatta e un tempo di interrogazione più lento.

Un filtro Bloom con il numero ottimale di funzioni hash (= bit per elemento) solitamente occupa uno spazio in memoria pari a N * log2(e) * log2(1/P) bit, dove N è il numero di elementi che si desidera memorizzare e P è la probabilità di falsi positivi. Per mettere le cose in prospettiva, supponiamo che tu voglia archiviare 100.000 elementi con 1 falso positivo ogni 8.000 elementi. Dato che log2(8K) ≈ log2(8192) = 13 e log2(e) ≈ 1,44, sono necessari 100K * 1,44 * 13 bit ≈ 1828 KiB ≈ 1,78 MiB.

Il minimo teorico per una struttura dati probabilistica simile sarebbe N * log2(1/P), quindi un filtro Bloom utilizza all’incirca il 44% di memoria in più rispetto a quella teoricamente necessaria (log(e) = 1,44). GCS è un modo per avvicinarsi a quel minimo.

GCS ben si adatta in situazioni in cui si vuole minimizzare l’occupazione di memoria e ci si può permettere un tempo di calcolo leggermente superiore, rispetto ad un filtro Bloom. Google Chromium, per esempio, lo utilizza per mantenere un set locale (client) di SSL CRL; preferiscono un’occupazione di memoria inferiore perché è particolarmente importante in scenari vincolati (ad esempio: dispositivi mobili) e possono permettersi che la struttura sia un po’ più lenta del filtro Bloom poiché è comunque molto più veloce di un handshake SSL (doppio andata e ritorno di rete).

Trasformare le parole in valori

GCS è in realtà abbastanza semplice e ti guiderò passo dopo passo. Innanzitutto, concordiamo un dizionario di parole che desideri inserire nel set, per esempio l’alfabeto NATO:

[‘alpha’, ‘bravo’, ‘charlie’, ‘delta’, ‘echo’, ‘foxtrot’, ‘golf’, ‘hotel’, ‘india’, ‘juliet’, ‘kilo’, ‘lima’, ‘mike’, ‘november’, ‘oscar’, ‘papa’, ‘quebec’, ‘romeo’, ‘sierra’, ‘tango’, ‘uniform’, ‘victor’, ‘whiskey’, ‘xray’, ‘yankee’,’zulu’]

Vogliamo creare una struttura dati per queste parole con una probabilità di falsi positivi 1 su 64. Ciò significa che ci aspettiamo di poter confrontare l’intero dizionario inglese con esso, e circa 1 parola ogni 64 risulterà presente anche se non lo è.

Calcoliamo una singola chiave hash per ogni diverso elemento, come numeri interi nell’intervallo [0, N*P). Poiché N=26 (la lunghezza dell’alfabeto NATO) e P=64, l’intervallo è [0, 1664]. Come nel caso dei filtri Bloom, vogliamo che questo hash sia distribuito uniformemente nel dominio, quindi un hash crittografico come MD5 o SHA1 è una buona scelta (e no, il fatto che ci siano attacchi pre-immagine su MD5 non ha importanza molto in questo scenario). Avremo bisogno di un modo per convertire un hash a 128 o 160 bit in un numero compreso nell’intervallo [0, 1664], ma l’equivalente morale del modulo è sufficiente per non influenzare la distribuzione. Calcoleremo quindi l’hash come segue:

def gcs_hash(w, (N,P)):
“””
Hash value for a GCS with N elements and 1/P probability
of false positives.
We just need a hash that generates uniformally-distributed
values for best results, so any crypto hash is fine. We
default to MD5.
“””
h = md5(w).hexdigest()
h = long(h[24:32],16)
return h % (N*P)

Se applichiamo questa funzione sulle parole di input, otteniamo questi valori hash:

[(‘alpha’, 1017L), (‘bravo’, 591L), (‘charlie’, 1207L), (‘delta’, 151L), (‘echo’, 1393L), (‘foxtrot’, 1005L), (‘golf’, 526L), (‘hotel’, 208L), (‘india’, 461L), (‘juliet’, 1378L), (‘kilo’, 1231L), (‘lima’, 192L), (‘mike’, 1630L), (‘november’, 1327L), (‘oscar’, 997L), (‘papa’, 662L), (‘quebec’, 806L), (‘romeo’, 1627L), (‘sierra’, 866L), (‘tango’, 890L), (‘uniform’, 1134L), (‘victor’, 269L), (‘whiskey’, 512L), (‘xray’, 831L), (‘yankee’, 1418L), (‘zulu’, 1525L)]

Ora prendiamo semplicemente i valori hash e ordiniamoli. Questo è il risultato:

[151L, 192L, 208L, 269L, 461L, 512L, 526L, 591L, 662L, 806L, 831L, 866L, 890L, 997L, 1005L, 1017L, 1134L, 1207L, 1231L, 1327L, 1378L, 1393L, 1418L, 1525L, 1627L, 1630L]

Ricordare che l’intervallo era [0, 1664). Dato che abbiamo utilizzato un hash crittografico, prevediamo che questi valori siano distribuiti uniformemente in tale intervallo. A prima vista sembrano così, e ovviamente migliora molto con i set di dati del mondo reale che sono molto più grandi.

Comprimiamo

Vogliamo ora comprimere questo insieme di numeri nel modo più efficiente. Algoritmi generici come zlib sono ovviamente la scelta sbagliata in questo caso, poiché funzionano trovando ripetizioni di stringhe e la codifica a 16 o 32 bit dei numeri di cui sopra sembrerebbe dati casuali a zlib. Alcune teorie sulla compressione vengono in soccorso: il modo migliore per comprimere un set di dati uniformi non ordinati è calcolare la serie di differenze, che sarà una distribuzione geometrica, e quindi utilizzare la codifica Golomb. Ti ho perso? Vediamolo un passo alla volta.

Se calcoliamo gli incrementi (differenze) tra un insieme di valori distribuiti uniformemente, il risultato è una distribuzione geometrica. Ricordiamo che inizialmente abbiamo deciso per un intervallo esattamente di 26*64, quindi abbiamo scelto 26 valori distribuiti uniformemente al suo interno. Se dovessi scommettere sulla distanza più probabile tra un valore e quello successivo, non diresti “64”? SÌ. E possiamo sostenere che la maggior parte delle distanze saranno numeri abbastanza vicini al valore 64, e valori molto più grandi sono estremamente improbabili. Questa intuizione coincide con la distribuzione geometrica (il cui corrispondente nel dominio continuo è la distribuzione esponenziale).

Nel nostro esempio, questa è la serie di differenze:

[151L, 41L, 16L, 61L, 192L, 51L, 14L, 65L, 71L, 144L, 25L, 35L, 24L, 107L, 8L, 12L, 117L, 73L, 24L, 96L, 51L, 15L, 25L, 107L, 102L, 3L]

Codifica Golomb

Vogliamo ora comprimere questo insieme di differenze con la codifica Golomb. Come dice Wikipedia, “gli alfabeti che seguono una distribuzione geometrica avranno un codice Golomb come codice prefisso ottimale, rendendo la codifica Golomb altamente adatta a situazioni in cui la presenza di piccoli valori nel flusso di input è significativamente più probabile rispetto a valori grandi”. Utilizzeremo infatti un sottocaso semplificato della codifica Golomb, in cui il parametro p è una potenza di 2 (come lo è 64 nel nostro caso). Questo sottocaso è chiamato codifica Rice.

Tornando all’intuizione: comprimeremo valori che molto probabilmente saranno piccoli quanto il valore 64 e molto difficilmente saranno molto più grandi; 128 è improbabile, 192 è molto improbabile, 256 è molto molto improbabile e così via. La codifica Golomb divide ciascun valore in due parti: il quoziente e il resto della divisione per il parametro. Dato ciò che abbiamo appena detto sulla somiglianza, devi aspettarti che il quoziente sia probabile 0 o 1, improbabile sia 2, molto improbabile sia 3, molto molto improbabile sia 4, ecc. D’altra parte, il resto è probabilmente è solo un numero casuale da cui non possiamo dedurre molto, è l’oscillazione ad alta frequenza che è impossibile da prevedere. La codifica Golomb (riso) codifica semplicemente il quoziente in base 1 (codifica unaria) e il resto in base 2 (codifica binaria). La codifica unaria potrebbe sembrare strana all’inizio, ma è davvero semplice.

Quindi emettiamo tanti 1 quanto il numero che vogliamo codificare (il quoziente) seguito da uno zero. Quindi, emettiamo la codifica binaria del resto utilizzando esattamente 6 bit (poiché sarà un numero compreso tra 0 e 63). Pertanto, un numero compreso tra 0 e 63 sarà lungo esattamente 7 bit: 1 bit per il quoziente (0) e 6 bit per il resto. Un numero compreso tra 64 e 127 sarà lungo 8 bit (quoziente 10, più il resto); Un numero compreso tra 128 e 191 sarà lungo 9 bit (quoziente 110); e così via. I numeri più piccoli sono il più compatti possibile, i numeri più alti e improbabili diventano sempre più lunghi.

197 bit (25 byte riempiti) per codificare 26 parole di lunghezza arbitraria con un 1,5% di falsi positivi. Sono 7,57 bit per parola. Non male! Il numero minimo teorico di bit era 26 * log2(64) = 156, quindi siamo ancora un po’ fuori strada in questo esempio, ma comunque migliore di un filtro Bloom ottimale che richiederebbe 225 bit. L’esempio che ho scelto è ovviamente troppo piccolo e quindi risente molto delle parole specifiche e dell’output dell’MD5. Ho eseguito lo stesso algoritmo su un dizionario inglese di 640.000 parole con una falsa probabilità prevista 1/1024 e ho ottenuto un GCS di 7.405.432 bit, ovvero circa 11,58 bit per parola. Un filtro Bloom ottimale per lo stesso set richiederebbe 9.227.646 bit, mentre il minimo teorico sarebbe 6.396.530 bit. Un bel miglioramento, in effetti.

Miglioramenti alla decompressione e alle query

Allora come possiamo ora interrogare una parola per vedere se è nel set o no? Dobbiamo solo invertire tutti i passaggi.

Iniziamo a esaminare i bit. Estraiamo il quoziente Q semplicemente contando il numero di 1 consecutivi prima dello 0 finale; quindi estraiamo il resto di dimensione fissa R (esattamente P bit, 6 nel nostro esempio). Calcoliamo la differenza originale (Q*P+R) e la accumuliamo in un numero intero in modo da rigenerare l’insieme ordinato originale di valori hash, un elemento alla volta. Non abbiamo bisogno di espandere effettivamente l’intero set di memoria: mentre esaminiamo i bit e calcoliamo un valore hash alla volta, possiamo confrontarlo con quello che ci viene interrogato, per vedere se c’è una corrispondenza.

Dopo aver invertito i passaggi di codifica e differenza, il set di valori hash sottostante viene ordinato. Quindi scorrere il set in ordine lineare sembra più lento di quanto potrebbe essere. Si potrebbe pensare di eseguire una ricerca in due parti, ma non esiste un modo semplice per passare a un indice arbitrario nell’insieme codificato, poiché gli elementi codificati hanno dimensioni diverse in bit e possono essere decodificati solo uno alla volta in ordine lineare.

Ciò che possiamo fare per migliorare un po’ il tempo di interrogazione è calcolare un indice che permetta di cercare all’interno dell’insieme codificato. Ad esempio, se vuoi velocizzare i tempi di query 32 volte, puoi dividere il dominio originale [0…N*P) in 32 sottodomini di uguale dimensione N*P/32. Quindi, per ciascun sottodominio, trovi il valore hash più piccolo che fa parte del sottodominio e salvi il suo indice bit nel GCS codificato all’interno dell’indice. Poiché i valori hash sono distribuiti uniformemente, ogni sottodominio conterrà circa N/32 valori, quindi cercandolo durante l’esecuzione di query sarà necessario decodificare solo 1/32 dell’intero GCS, ottenendo così un aumento di velocità di 32 volte nel tempo di query. Nell’esempio del dizionario inglese completo citato sopra, un indice aggiuntivo composto da 32 indici di 32 bit ciascuno equivale a soli 1.204 bit di memoria aggiuntiva; rispetto ad un GCS da 7 milioni di bit, è un buon affare ottenere un aumento di velocità di 32 volte nel tempo di interrogazione!

Gioca con il codice

Il codice completo è disponibile su GitHub. Ho scritto sia un’implementazione Python che C++ che puoi confrontare. Il codice Python è pensato per essere davvero semplice e non realmente ottimizzato (ad esempio: trasmette anche il set dal disco quando si esegue una query). Il C++ è leggermente più ottimizzato, sebbene sia ancora per lo più un esempio accademico. Si noti che il codice non implementa l’indice per accelerare la decompressione. Anche se è un buon affare, ovviamente non è obbligatorio ed è solo un’ottimizzazione.