Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint

Una tabella hash (Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →) è veloce in media solo se i dati non sono scelti da un avversario contro la funzione hash. Con un'unica funzione fissa $h$ esistono insiemi di chiavi che finiscono tutte nello stesso bucket. Rimedio: scegliere $h$ a caso da una famiglia, indipendentemente dai dati. Il costo atteso si calcola sulla scelta di $h$, non sull'input: vale per ogni insieme di chiavi, come per gli algoritmi randomizzati di Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →. Prerequisiti: Palline e urne - compleanno, carico massimo e approssimazione di PoissonModello palline e urne (m palline, n urne, scelte indipendenti e uniformi): paradosso del compleanno con soglia sqrt(2 n ln 2), urne vuote attese n e^(-m/n), carico massimo ln n / ln ln n con dimostrazione (first moment e union bound), approssimazione di Poisson con il fattore e sqrt(m), potere delle due scelte (ln ln n / ln 2).Palline e urne - compleanno, carico massimo e approssimazione di Poisson →, Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →.

Catene e costo atteso

Si memorizzano $n$ chiavi in $m$ bucket, ognuno con una lista (separate chaining). Il fattore di carico è $\alpha=n/m$. Se $h$ fosse una funzione veramente casuale ($h(x)$ uniforme e indipendente per ogni $x$, cioè il modello palline e urne) la ricerca di una chiave assente confronterebbe in media $\alpha$ elementi (la lunghezza media di una lista), una ricerca riuscita $1+\frac{n-1}{2m}$. Ma una funzione casuale da un universo $U$ a $[m]$ richiede $|U|\log_2 m$ bit per essere memorizzata: inutilizzabile. Serve una famiglia piccola che dia la stessa garanzia sulle coppie di chiavi, che è tutto ciò che interessa per i confronti.

Famiglie universali

Definizione (famiglia universale). Una famiglia $\mathcal H$ di funzioni $U\to[m]$ è universale se per ogni coppia di chiavi $x\ne y$, scegliendo $h\in\mathcal H$ uniformemente a caso, $$P_h\bigl(h(x)=h(y)\bigr)\le\frac1m.$$

È la probabilità di collisione di una funzione casuale ideale, richiesta solo per le coppie.

Teorema (catene). Sia $\mathcal H$ universale, $S\subseteq U$ un insieme di $n$ chiavi e $h$ scelta a caso. Per una chiave $x$ il numero atteso di chiavi di $S\setminus\{x\}$ nel suo bucket è al più $\frac{n-1}m$ se $x\in S$ e $\frac nm$ se $x\notin S$. Quindi ricerca, inserimento e cancellazione costano in media $O(1+\alpha)$.

Dimostrazione. Gli indicatori $I_y=1$ se $h(y)=h(x)$, con $y\in S\setminus\{x\}$: $E[I_y]\le\frac1m$ per la definizione. Per la linearità (Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →), senza alcuna ipotesi di indipendenza, $E[\sum_yI_y]\le\frac{n-1}m$. Con la chiave stessa la lista ha $1+\frac{n-1}m$ elementi. $\square$

Lista più lunga. Se $L$ chiavi cadono nello stesso bucket, ci sono $\binom L2$ coppie in collisione; il numero atteso di coppie in collisione è $\le\binom n2\frac1m$. Con $m=n$ per Markov $P(\text{lista}\ge L)\le\frac{(n-1)/2}{L(L-1)/2}=\frac{n-1}{L(L-1)}$, che per $L=2\sqrt n$ vale circa $\frac14$. La sola universalità garantisce quindi liste massime $O(\sqrt n)$; per il $\Theta(\ln n/\ln\ln n)$ del modello ideale servono famiglie con più indipendenza (fuori programma).

La famiglia $((ax+b)\bmod p)\bmod m$

Teorema (costruzione). Siano $p$ un primo con $p\ge|U|$, chiavi $U=\{0,\dots,p-1\}$ e, per $a\in\{1,\dots,p-1\}$, $b\in\{0,\dots,p-1\}$, $$h_{a,b}(x)=\bigl((ax+b)\bmod p\bigr)\bmod m.$$ La famiglia $\mathcal H=\{h_{a,b}\}$, di $p(p-1)$ funzioni, è universale.

Dimostrazione. Fissate $x\ne y$. Si pone $r=(ax+b)\bmod p$ e $s=(ay+b)\bmod p$. (1) $r\ne s$: altrimenti $a(x-y)\equiv0\pmod p$, impossibile perché $p$ è primo e né $a$ né $x-y$ sono multipli di $p$. (2) La mappa $(a,b)\mapsto(r,s)$ è una biiezione tra le $p(p-1)$ coppie $(a,b)$ e le $p(p-1)$ coppie ordinate $(r,s)$ con $r\ne s$ (si risolve il sistema lineare in $\mathbb Z_p$: $a=(r-s)(x-y)^{-1}$, $b=r-ax$), quindi scegliere $(a,b)$ a caso equivale a scegliere $(r,s)$ a caso con $r\ne s$. (3) Si ha collisione se $r\equiv s\pmod m$. Per ogni $r$ i valori $s\ne r$ con $s\equiv r\pmod m$ sono al più $\lceil p/m\rceil-1\le\frac{p-1}m$ (i valori di $[0,p-1]$ nella stessa classe di resto di $r$ sono al più $\lceil p/m\rceil$, tolto $r$ stesso). Dunque le coppie in collisione sono al più $p\cdot\frac{p-1}m$ su $p(p-1)$: probabilità $\le\frac1m$. $\square$

Esempio ($p=17$, $m=5$, $a=3$, $b=4$). $h(x)=((3x+4)\bmod17)\bmod5$.

Collidono $2$ e $15$ (bucket $0$) e $8$ e $12$ (bucket $1$): su $6$ chiavi in $5$ bucket è inevitabile (principio dei cassetti). Verifica esaustiva con tutte le $p(p-1)$ funzioni: per $p=7$, $m=3$ la coppia $(1,2)$ collide in $10$ funzioni su $42$ ($0{,}238$) e il caso peggiore su tutte le coppie è $\frac5{21}=0{,}238\le\frac13$; per $p=17$, $m=5$ il caso peggiore è $\frac{21}{136}=0{,}154\le\frac15$. Il limite $\frac1m$ non è stretto ma regge sempre.

Per chiavi più grandi di $p$ (stringhe, interi a $64$ bit) si usa $p$ primo maggiore dell'universo, per esempio il primo di Mersenne $2^{61}-1$ nel codice sotto. La variante con $a\in\{0,\dots,p-1\}$ e senza il $\bmod m$ finale è a coppie indipendente: $(h(x),h(y))$ è uniforme su $\mathbb Z_p^2$, quindi vale anche $P(h(x)=i,\,h(y)=j)=1/p^2$.

Hashing perfetto (statico, due livelli)

Per un insieme fisso $S$ di $n$ chiavi si vuole una ricerca in tempo $O(1)$ nel caso peggiore con spazio $O(n)$.

Algoritmo (due livelli).

1. Primo livello. Si sceglie $h\in\mathcal H$ con $m=n$ bucket; il bucket $i$ contiene $n_i$ chiavi. Si ripete finché $\sum_in_i^2\le4n$.
2. Secondo livello. Per ogni bucket con $n_i\ge1$ si sceglie $h_i$ da una famiglia universale su $m_i=n_i^2$ celle, ripetendo finché è priva di collisioni sulle $n_i$ chiavi del bucket.
3. Ricerca di $x$: si calcola $i=h(x)$ e si guarda la cella $h_i(x)$ del bucket $i$: due accessi.

Analisi. Secondo livello: con $m_i=n_i^2$ il numero atteso di coppie in collisione è $\le\binom{n_i}2\frac1{n_i^2}<\frac12$, quindi per Markov $P(\text{almeno una collisione})<\frac12$: servono in media meno di $2$ tentativi. Primo livello: $\sum_in_i^2=n+2C$ con $C$ = numero di coppie in collisione, perché $n_i^2=n_i+2\binom{n_i}2$ e $\sum n_i=n$. Con $m=n$: $E[C]\le\binom n2\frac1n=\frac{n-1}2$, quindi $E[\sum n_i^2]\le n+(n-1)=2n-1$. Per Markov $P(\sum n_i^2\ge4n)\le\frac{2n-1}{4n}<\frac12$: anche qui meno di $2$ tentativi. Lo spazio è $n+\sum n_i^2\le5n$: lineare.

Esempio ($p=97$, $S=\{5,17,29,41,48,62,73,90\}$, $n=m=8$). Primo livello $h(x)=((3x+1)\bmod97)\bmod8$: $5\mapsto16\mapsto0$; $29\mapsto88\mapsto0$; $48\mapsto145\bmod97=48\mapsto0$; $62\mapsto187\bmod97=90\mapsto2$; $73\mapsto220\bmod97=26\mapsto2$; $41\mapsto124\bmod97=27\mapsto3$; $17\mapsto52\mapsto4$; $90\mapsto271\bmod97=77\mapsto5$. Bucket: $0:\{5,29,48\}$, $2:\{62,73\}$, $3:\{41\}$, $4:\{17\}$, $5:\{90\}$, gli altri vuoti. $\sum n_i^2=9+4+1+1+1=16\le32$. Secondo livello con $h_i(x)=((2x+1)\bmod97)\bmod m_i$: bucket $0$ ha $m_0=9$ e le posizioni $(11\bmod9,\ 59\bmod9,\ 97\bmod97\bmod9)=(2,5,0)$, tutte diverse; bucket $2$ ha $m_2=4$ e $62\mapsto125\bmod97=28\mapsto0$, $73\mapsto147\bmod97=50\mapsto2$. I bucket singoli usano una cella. Spazio totale $8+9+4+1+1+1=24$ celle per $8$ chiavi.

Filtri di Bloom

Definizione (filtro di Bloom). Un vettore di $m$ bit, inizialmente $0$, e $k$ funzioni hash $h_1,\dots,h_k:U\to[m]$. Inserimento di $x$: si pongono a $1$ i bit $h_1(x),\dots,h_k(x)$. Interrogazione di $x$: si risponde "presente" se tutti i $k$ bit sono $1$, "assente" altrimenti.

Nessun falso negativo: un elemento inserito ha i suoi $k$ bit a $1$ per sempre. Può esserci un falso positivo: un elemento mai inserito i cui $k$ bit sono stati posti a $1$ da altri. Non si possono cancellare elementi (si userebbe un vettore di contatori). Occupa $m$ bit indipendentemente dalla lunghezza delle chiavi.

Teorema (falsi positivi). Dopo $n$ inserimenti, con $k$ funzioni indipendenti e uniformi,

• un bit specifico è ancora $0$ con probabilità $\bigl(1-\frac1m\bigr)^{kn}\approx e^{-kn/m}$;
• un elemento non inserito è un falso positivo con probabilità $f\approx\Bigl(1-e^{-kn/m}\Bigr)^k$.
• Per $m,n$ fissati $f$ è minima per $k=\frac mn\ln2$, e vale allora $f=2^{-k}=(0{,}6185)^{m/n}$.

Dimostrazione. Un bit non viene toccato da una data scelta con probabilità $1-\frac1m$, e ci sono $kn$ scelte indipendenti (da cui il primo punto, con $(1-\frac1m)^{kn}\approx e^{-kn/m}$). Sia $q=e^{-kn/m}$ la frazione attesa di bit a $0$. L'elemento è un falso positivo se tutti i suoi $k$ bit sono $1$: $\approx(1-q)^k$ (le posizioni nel filtro sono quasi indipendenti; la formula esatta sulla posizione dei bit è un po' più grande ma la differenza è trascurabile per $m$ grande). Per ottimizzare si scrive $k=-\frac mn\ln q$ e $$\ln f=k\ln(1-q)=-\frac mn\,\ln q\,\ln(1-q).$$ Il prodotto $\ln q\ln(1-q)$ è simmetrico in $q\leftrightarrow1-q$ e ha l'unico punto di massimo in $q=\frac12$, dove vale $\ln^22$. Quindi $f$ è minimo per $q=\frac12$, cioè per $e^{-kn/m}=\frac12$, $k=\frac mn\ln2$, e $\ln f=-\frac mn\ln^22$, cioè $f=2^{-(m/n)\ln2}=(0{,}6185)^{m/n}$. Con $k$ ottimo metà dei bit è a $1$. $\square$

Dimensionamento. Dal $f=2^{-k}$ ottimo si ricava $\frac mn=\log_2(1/f)/\ln2=1{,}44\log_2(1/f)$ bit per elemento: $4{,}79$ per $f=10\%$, $9{,}59$ per $1\%$, $14{,}38$ per $0{,}1\%$. Ogni bit in più per elemento moltiplica i falsi positivi per $0{,}6185$.

Esempio ($n=1000$, $m=10\,000$). Con $k=7$ ($\frac mn\ln2=6{,}93$): $f=(1-e^{-0{,}7})^7=0{,}00819$; una simulazione con $200\,000$ interrogazioni dà $0{,}0081$ e una frazione di bit a $1$ pari a $0{,}503$ (attesa $0{,}503$). Con $k=3$ sarebbe $0{,}0174$, con $k=5$ $0{,}0094$, con $k=8$ $0{,}0085$: il minimo è piatto e un $k$ intero vicino a $6{,}93$ basta.

Uso tipico: filtro davanti a un archivio lento, che si interroga solo se il filtro risponde "presente".

Fingerprint

Definizione (fingerprint). Una fingerprint di $b$ bit di un oggetto grande $x$ è $\phi(x)=h(x)\in\{0,1\}^b$ con $h$ scelta a caso; si usa $\phi(x)=\phi(y)$ come test (probabilistico) per $x=y$. Se $x=y$ le fingerprint coincidono sempre; se $x\ne y$ possono coincidere per caso (errore unilaterale, Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →).

Quanti bit. Con $n$ oggetti distinti e fingerprint a $b$ bit non devono esserci due collisioni: è il compleanno con $2^b$ urne (Palline e urne - compleanno, carico massimo e approssimazione di PoissonModello palline e urne (m palline, n urne, scelte indipendenti e uniformi): paradosso del compleanno con soglia sqrt(2 n ln 2), urne vuote attese n e^(-m/n), carico massimo ln n / ln ln n con dimostrazione (first moment e union bound), approssimazione di Poisson con il fattore e sqrt(m), potere delle due scelte (ln ln n / ln 2).Palline e urne - compleanno, carico massimo e approssimazione di Poisson →), e per l'union bound $$P(\text{una collisione tra i }n)\le\binom n2 2^{-b}<\frac{n^2}{2^{b+1}}.$$ Per $n=10^6$ documenti e probabilità di errore $\le10^{-3}$ serve $2^b\ge\frac{10^{12}}{2\cdot10^{-3}}=5\cdot10^{14}$, cioè $b=49$ bit ($b=48$ dà $0{,}0018$). Con $b=64$ l'errore è $2{,}7\cdot10^{-8}$; con $b=32$ la collisione è praticamente certa.

Fingerprint di una stringa. Per $s=s_0s_1\dots s_{\ell-1}$ e $p$ primo si sceglie $x\in\mathbb Z_p$ a caso e si pone $\phi(s)=\sum_is_ix^i\bmod p$ (valutazione in $x$ del polinomio che ha come coefficienti i caratteri). Se $s\ne t$ della stessa lunghezza $\ell$, $\phi(s)-\phi(t)$ è un polinomio non nullo di grado $<\ell$ che ha al più $\ell-1$ radici in $\mathbb Z_p$, quindi $P(\phi(s)=\phi(t))\le\frac{\ell-1}p$ (lemma di Schwartz-Zippel in una variabile, Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici →). Per $\ell=10^6$ e $p=2^{61}-1$: $\le4{,}3\cdot10^{-13}$.

import random
from math import log

P = (1 << 61) - 1                       # primo di Mersenne, maggiore di ogni chiave

def scegli_hash(m):
    """Un elemento a caso della famiglia h(x) = ((a x + b) mod P) mod m."""
    a, b = random.randrange(1, P), random.randrange(P)
    return lambda x: ((a * x + b) % P) % m

class Bloom:
    def __init__(self, m, k):
        self.m, self.bits = m, bytearray(m)
        self.h = [scegli_hash(m) for _ in range(k)]   # k funzioni indipendenti
    def aggiungi(self, x):
        for h in self.h:
            self.bits[h(x)] = 1
    def contiene(self, x):                            # False: certamente assente
        return all(self.bits[h(x)] for h in self.h)   # True: forse presente

if __name__ == "__main__":
    n, eps = 10_000, 0.01
    m = round(n * log(1 / eps) / log(2) ** 2)         # m/n = 1,44 log2(1/eps)
    k = round(m / n * log(2))
    f = Bloom(m, k)
    dentro = [random.getrandbits(60) for _ in range(n)]
    for x in dentro:
        f.aggiungi(x)
    falsi = sum(f.contiene(random.getrandbits(60)) for _ in range(100_000))
    print(m, k, all(f.contiene(x) for x in dentro), falsi / 100_000)

Con $n=10\,000$ e $\varepsilon=1\%$ il programma usa $m=95\,851$ bit e $k=7$ e osserva una frequenza di falsi positivi di circa $0{,}0098$ (quattro esecuzioni: da $0{,}0095$ a $0{,}0101$), senza nessun falso negativo.

Domande d'esame

1. Dimostra che la famiglia $((ax+b)\bmod p)\bmod m$ è universale. Per $x\ne y$ la mappa $(a,b)\mapsto(r,s)$ è una biiezione sulle coppie con $r\ne s$; per ogni $r$ ci sono al più $\lceil p/m\rceil-1\le\frac{p-1}m$ valori $s\ne r$ con $s\equiv r\pmod m$; quindi la probabilità è $\le\frac1m$.
2. Una tabella con $n=2000$ chiavi in $m=1000$ bucket e hash universale: lunghezza attesa della lista di una chiave presente? Al più $1+\frac{n-1}m=2{,}999$, per linearità degli indicatori di collisione.
3. Perché nell'hashing perfetto il secondo livello usa $n_i^2$ celle e il primo si accetta se $\sum n_i^2\le4n$? Con $n_i^2$ celle le coppie in collisione attese sono $<\frac12$, quindi un tentativo riesce con probabilità $>\frac12$; $E[\sum n_i^2]\le2n-1$ e per Markov $\sum n_i^2<4n$ con probabilità $>\frac12$; spazio totale $\le5n$.
4. Un filtro di Bloom con $m/n=10$ bit per elemento: $k$ ottimo e tasso di falsi positivi? $k=10\ln2=6{,}93\to7$ e $f=(1-e^{-0{,}7})^7=0{,}0082$.