TIN066 Univerzální a perfektní hashování

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
Tato část je neúplná a potřebuje rozšířit. Univerzální hashování. Důkazy a tak

Univerzální hashování[editovat | editovat zdroj]

Naše hashovací funkce se pro některé vstupní množiny bude chovat dobře a pro jiné hůře. Abychom si vylepšili naše šance, zaveďme si místo toho obecnější třídu (rozumně různorodých) funkcí H; než začneme hashovat, vybereme z nich náhodnou funkci $ h \in H $ (ta se stane atributem konkrétní instance hashovací tabulky). Můžeme analyzovat chování přes celý prostor hashovacích funkcí H a nepotřebuji předpoklad rovnoměrně rozložených dat.

  • Abychom měli snadnější práci, funkce si očíslujeme: $ H = \{h_i|i \in I\}\colon U \to \{0,\ldots,m-1\} $
  • Systém funkcí H je c-univerzální pro U, pokud $ \forall x,y \in U, x \ne y: |\{h \in H|h(x) = h(y)\}| \le {c |H| \over m} $
    • ekvivalentně pomocí pravděpodobnosti pro náhodně zvolené h,x,y: $ P(h(x)=h(y)) \leq \frac{c}{m} $

Pro univerzální systém (= 1-univerzální) je pravděpodobnost kolize (= 1/m) stejná, jako kdybychom rozhodili x,y do přihrádek zcela náhodně.

Existuje takový systém? Pro $ a,b \in U $ mějme hašovací funkce dané předpisem:

  • $ h_{a,b}(x) = ((ax + b) \mod N) \mod m $

Těchto funkcí je $ N^2 $. Pro pevně daná různá $ x, y \in U $, kolik funkci zobrazí x, y na stejný prvek? Když se zobrazí na stejný prvek, znamená to, že existuje $ i \in \{0..m-1\} $ (hodnota h) a $ r, s \in \{0.. \lceil \frac{N}{m}\rceil-1 \} $ (násobky m) takové, že:

  • $ (a x + b) \mod N = r \cdot m + i $
  • $ (a y + b) \mod N = s \cdot m + i $

To představuje dvě lineární rovnice v tělese $ \mathbb{Z}_N $ s neznámými a, b. Matice je regulární a soustava má právě jedno řešení. Rovnice se mohu lišit pravou stranou, každá pravá strana určuje jedno řešení (a, b). Počet pravých stran (= počet různých hodnot i, r, s = počet funkcí, zobrazujících x,y na stejný prvek) je $ m \lceil \frac{N}{m}\rceil ^2 $. Tento systém je c-univerzální, pokud:

  • $ m \lceil \frac{N}{m}\rceil ^2 \leq {c |H| \over m} = c \cdot {N^2 \over m} $

Což platí pro hodnotu c :

  • $ c = \frac{ m \lceil \frac{N}{m}\rceil ^2 } { \frac{N^2}{m} } = \frac{ \lceil \frac{N}{m}\rceil ^2 } { \frac{N^2}{m^2} } $


Tato část je neúplná a potřebuje rozšířit. Důkazy. Různé další vlastnosti.

Očekávaný čas operací MEMBER, INSERT, DELETE je $ O(1+c\alpha) $.


Vybrat z H nějakou funkci nemusí být jednoduché, velikost $ |H| $ totiž dost rychle roste a tak to může začít být obtížné. Podívejme se, jaké nejmenší c-univerzální systémy dokážeme najít!

Můžeme snadno dokázat, že $ |I|\ge {m \over c}(\lceil\log_m N\rceil - 1) $, takže velikost systému roste alespoň s logaritmem velikosti univerza.

Dá se také dokázat existence 5-univerzálního systému, funkce vypadnouz takové zvláštní prvočíselné konstrukce.

Nakonec c se dá zdola odhadnout: $ c > 1 - m/N $

Perfektní hashování[editovat | editovat zdroj]

Máme předem danou množinu S a chceme vyrobit perfektní hashovací funkci h takovou, aby nikdy negenerovala pro prvky množiny kolize. Typicky potřebujeme hodně rychlý MEMBER a vůbec nepotřebujeme INSERT/DELETE. Samozřejmě chceme, aby h byla rychlá a malá (ne třeba další tabulka ;-). Při generování h si můžeme klidně dát trochu na čas.

Mějme univerzum $ U = \{ 0,\ldots,N-1 \} $ a soubor funkcí $ H\colon U \to \{0,\ldots,m-1\} $. H bude $ (N,m,n) $-perfektní, když $ \forall S \subseteq U: |S| = n $ existuje perfektní $ h \in H $.

Lze odhadnout, že: $ |H| \ge {{N \choose n} \over {m \choose n}(N/m)^n} $ $ |H| \ge {\log N \over \log m} $

Důkaz existence se provádí maticemi, logaritmy, páčidly a integrály.

Důkaz, že $ |H| \ge {\log N \over \log m} $ je poměrně jednoduchý (analýza ve skriptech je náročnější). Nechť pro spor platí, že $ |H| \le {\log N \over \log m} $, potom $ |H| \log m \le \log N $ a když se zbavíme logaritmů, dostanem $ m^{|H|} \le N $. Z přihrádkového principu plyne, že musí existovat alespoň dva prvky z $ S $, které všechny funkce z $ H $ nahašují do jednoho políčka a to je spor s tím, že $ H $ je perfektní systém.

Konstrukce[editovat | editovat zdroj]

Tato část je neúplná a potřebuje rozšířit. Důkazy; neměly by ale zamlžit princip, možná by bylo lepší mít podrobnou konstrukci se všemi odvozeními na zvláštní stránce

Kterak sobě perfektní funkci poříditi? Existuje mnoho různých způsobů, ukazují se tři:

Velikánská tabulka, malá funkce, rychle nalezená[editovat | editovat zdroj]

Nechť N je prvočíslo, zavedeme si

  • sadu funkcí $ h_k(x) = (kx \mod N) \mod m\quad k=1,\ldots,N-1 $
  • počet kolizí $ b_i^k = |\{ x | h_k(x)=i\}| $ (trochu hloupá symbolika)
  • "míru" kolizí $ B_m^k = \sum_{i=0}^{m-1} (b_i^k)^2 $

Takže pokud funkce $ h_k $ není perfektní, nějaké $ b_i^k \ge 2 $ a tedy $ B_m^k \ge n + 2 $.

Co potřebuji? Najít (m,k) takové, aby $ h_k $ vedoucí do tabulky velikosti m byla perfektní. Potřebujeme odhadnout m, o kterém toto umíme dokázat, to se dělá přes nějaké omezení shora míry kolizí. Dojdeme k tomu, že platí:

  • Pro $ m=n(n-1)+1 $ existuje deterministický algoritmus, který v $ O(nN) $ nalezne perfektní k. (Prostě zkouší všech N možností, ověřit jednu trvá O(n).)
  • Pro $ m=2n(n-1) $ existuje pravděpodobnostní algoritmus, který v $ O(n) $ nalezne perfektní k s pravděpodobností alespoň 1/4. (Prostě střelíme náhodné $ k $ a v průměru po čtyřech pokusech se trefíme.)

Malá tabulka, velká funkce, celkem rychle nalezená[editovat | editovat zdroj]

Výše popsaný postup je fajn, ale potřebuje fakt velkou (kvadraticky velkou) tabulku. Půjdeme na to tedy trochu jinak; před chvílí jsme ve skutečnosti dostali ještě dva výsledky:

  • Pro $ m=n $ existuje deterministický algoritmus, který v $ O(nN) $ nalezne k takové, že $ B_m^k < 3n $
  • Pro $ m=n $ existuje pravděpodobnostní algoritmus, který v očekávaném čase $ O(n) $ nalezne k takové, že $ B_m^k < 4n $

BÚNO konstruujme deterministický algoritmus. Najdeme k, aby $ B_m^k < 3n $. Mějme:

  • Množinu kolidujících prvků $ S_i = \{s \in S|h_k(s) = i\} $
  • Velikost segmentu tabulky $ c_i = |S_i|(|S_i|-1)+1 $

Teď stačí pro každou neprázdnou $ S_i $ najít perfektní funkci $ h_{k_i} $ a naskládat segmenty pro všechny i za sebe a vyrobíme odpovídající perfektní funkci.

Ok, cílová tabulka je $ m<3n $, časová složitost $ O(nN) $. Teď ale zase máme problém, že si musíme pamatovat hashovací funkce pro všechny segmenty, to je $ O(n \log N) $ (druhý člen je prostor potřebný pro samotné číslo jedné funkce).

Malá tabulka, malá funkce, za dlouho nalezená[editovat | editovat zdroj]

Nechť $ \phi_p(x) = x \mod p $ pro prvočíslo p. Platí, že pro každou n-prvkovou S existuje prvočíslo p nejvýše $ O(n^2\ln N) $ takové, že funkce $ \phi_p $ je perfektní. (To je celkem těžké, ale dokazuje se.)

Deterministický algoritmus prostě zkusí všechna možná p. Ověřit, že nějaká $ \phi_p $ je perfektní, trvá $ O(n\log n) $ (duplicity odhalím setříděním všech nabytelných hodnot). Najít prvočíslo trvá málo (Rabin-Miller $ O(\log^3 p) $). Takže celkem to bude trvat $ O(n^3\log n\log N) $. Pravděpodobnostní algoritmus (střílí p náhodná) to zvládne v očekávaném čase $ O(n\log n(\log n + \log\log N)) $.

Tato část je neúplná a potřebuje rozšířit. Chybí algoritmus

Dynamické perfektní hashování[editovat | editovat zdroj]

Dynamizace pravděpodobnostních algoritmů.

Přístup přes hypergrafy.