Esercizio - Famiglia universale mod p mod m - verifica esaustiva e controesempio

Teoria: Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprintHashing con catene e costo atteso 1+alfa; famiglie universali (probabilità di collisione al più 1/m) e costruzione h(x)=((ax+b) mod p) mod m con dimostrazione; hashing perfetto a due livelli (spazio lineare, ricerca O(1) nel caso peggiore); filtri di Bloom: falsi positivi (1-e^(-kn/m))^k e k ottimo (m/n) ln 2; fingerprint di stringhe e numero di bit necessari.Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint → (famiglie universali e la costruzione $((ax+b)\bmod p)\bmod m$), 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 →.

Testo. Sia $p=7$, $m=3$ e $\mathcal H=\{h_{a,b}\}$ con $h_{a,b}(x)=((ax+b)\bmod7)\bmod3$, $a\in\{1,\dots,6\}$, $b\in\{0,\dots,6\}$, chiavi $x\in\{0,\dots,6\}$.

1. Quante funzioni ha $\mathcal H$? Elencare quelle che fanno collidere le chiavi $1$ e $2$ e calcolare $P_h(h(1)=h(2))$.
2. Contare esattamente le collisioni per ogni coppia di chiavi e verificare $P\le\frac1m$. Spiegare il valore osservato con il conteggio delle coppie $(r,s)$, $r\ne s$, $r\equiv s\pmod 3$.
3. Se si ammette anche $a=0$ (così $a\in\{0,\dots,6\}$, $49$ funzioni) la famiglia resta universale?
4. Per la variante $g_{a,b}(x)=(ax+b)\bmod p$ con $a\in\{0,\dots,p-1\}$ (senza $\bmod m$) e $p=5$, verificare che per ogni $x\ne y$ la coppia $(g(x),g(y))$ è uniforme sulle $25$ coppie.

Soluzione

1. Funzioni e collisioni di $(1,2)$. $|\mathcal H|=6\cdot7=42$. Si ha $h(1)=((a+b)\bmod7)\bmod3$ e $h(2)=((2a+b)\bmod7)\bmod3$. Le coppie $(a,b)$ che le fanno coincidere sono $$(1,5),\ (3,0),\ (3,4),\ (3,5),\ (3,6),\ (4,0),\ (4,1),\ (4,2),\ (4,6),\ (6,1),$$ cioè $10$. Controlli a mano: $(1,5)$: $a+b=6\to6\bmod3=0$; $2a+b=7\to0\to0$. $(3,0)$: $3\to0$; $6\to0$. $(4,1)$: $5\to2$; $9\bmod7=2\to2$. $(6,1)$: $7\to0\to0$; $13\bmod7=6\to0$. Dunque $P=\frac{10}{42}=\boxed{\frac5{21}=0{,}238}\le\frac13$.

2. Tutte le coppie e il conteggio. L'enumerazione esaustiva sulle $\binom72=21$ coppie dà esattamente $10$ collisioni per ogni coppia. Spiegazione: la mappa $(a,b)\mapsto(r,s)=(ax+b\bmod7,\ ay+b\bmod7)$ è una biiezione tra le $42$ funzioni e le $42$ coppie ordinate con $r\ne s$ (dimostrazione nella teoria). Si ha collisione se $r\equiv s\pmod3$. I resti in $\{0,\dots,6\}$ modulo $3$ formano le classi $\{0,3,6\}$, $\{1,4\}$, $\{2,5\}$ di taglia $3,2,2$: le coppie ordinate $(r,s)$, $r\ne s$, nella stessa classe sono $3\cdot2+2\cdot1+2\cdot1=10$. Il limite generale è $p(\lceil p/m\rceil-1)=7\cdot2=14$ coppie, cioè $P\le\frac{14}{42}=\frac13$: qui è largo perché le classi non sono tutte di taglia $\lceil p/m\rceil=3$.

3. Con $a=0$ non è più universale. Per $a=0$ la funzione è costante in $x$: $h_{0,b}(x)=(b\bmod7)\bmod3$ fa collidere ogni coppia. Sono $7$ funzioni in più, quindi le collisioni di $(1,2)$ passano da $10$ a $10+7=17$ su $49$ funzioni: $P=\frac{17}{49}=0{,}347>\frac13=0{,}333$. La famiglia non è universale (la differenza è piccola ma basta a violare la definizione, e per $p$ piccolo rispetto a $m$ può essere grande). Per questo nella costruzione si impone $a\ne0$. Il caso di $a=0$ senza $\bmod m$, invece, è compatibile con la pairwise independence (punto 4).

4. Pairwise independence senza $\bmod m$. Per $p=5$ e ogni $x\ne y$ la mappa $(a,b)\mapsto(ax+b,\,ay+b)\bmod5$ da $\{0,\dots,4\}^2$ in sé è biiettiva: il sistema ha determinante $x-y\ne0$ invertibile mod $5$. Quindi ognuna delle $25$ coppie $(i,j)$ compare esattamente una volta e $P(g(x)=i,\,g(y)=j)=\frac1{25}$ per ogni $i,j$. L'enumerazione conferma, per tutte le $20$ coppie ordinate di chiavi distinte. Questa è una famiglia a coppie indipendente, più forte della universale; il $\bmod m$ finale poi riduce il campo ma non garantisce uniformità esatta (se $p$ non è multiplo di $m$ le classi hanno taglie diverse).

Codice di verifica

from collections import Counter

p, m = 7, 3
def h(a, b, x): return ((a * x + b) % p) % m

print([(a, b) for a in range(1, p) for b in range(p) if h(a, b, 1) == h(a, b, 2)])
cont = Counter(sum(h(a, b, x) == h(a, b, y) for a in range(1, p) for b in range(p))
               for x in range(p) for y in range(x + 1, p))
print(cont)                                           # tutte le 21 coppie: 10 collisioni su 42
print(sum(h(a, b, 5) == h(a, b, 6) for a in range(p) for b in range(p)), "su", p * p)  # con a = 0

q = 5                                                 # variante senza mod m
ok = all(Counter(((a * x + b) % q, (a * y + b) % q) for a in range(q) for b in range(q)).most_common(1)[0][1] == 1
         for x in range(q) for y in range(q) if x != y)
print(ok)

Risultato: la lista delle $10$ coppie, Counter({10: 21}), 17 su 49, True.