Zajmiemy się jednym z podstawowych problemów algorytmicznych: problemem słownika. W tym rozdziale omawiamy jedno z bardziej efektywnych podejść do tego problemu, zwane haszowaniem (warto wspomnieć, że problem słownika jest głównym, ale nie jedynym zastosowaniem haszowania). Przypomnijmy krótko na czym polega problem słownika.
Problem słownika
Należy opisać strukturę danych, która reprezentuje pewien zbiór elementów \(S\) i udostępnia następujące operacje:
- Lookup(\(x\)) -- czy \(x \in S\)?
- Insert(\(x\)) -- \(S:=S \cup \{x\}\)
- Remove(\(x\)) -- \(S:=S \setminus \{x\}\)
Zakładamy, że elementy zbioru \(S\) pochodzą z pewnego uniwersum \(U\), tzn. \(S\subseteq U\). W zastosowaniach elementy \(S\) są zwykle liczbami lub napisami. W dalszych rozważaniach będziemy przyjmować, że \(U\) jest zbiorem liczb naturalnych z ograniczonego zakresu, tzn. \(U=\{0,\ldots,|U|-1\}\). Nie jest to duże ograniczenie, gdyż w ten sposób możemy reprezentować także np. napisy o ograniczonej długości czy liczby wymierne o ograniczonej precyzji.
Będziemy również zakładać, że znana jest liczba \(n\) taka, że \(|S|\le n\).
Haszowanie: główny pomysł
W znanych nam drzewiastych rozwiązaniach problemu słownika, chcąc wyszukać element w strukturze danych, algorytm "błądzi" po strukturze danych podążając za kolejnymi wskaźnikami. W haszowaniu chcemy skrócić ten proces: z grubsza rzecz biorąc, dla każdego potencjalnego elementu \(x\) chcielibyśmy natychmiast (ewentualnie wykonując proste obliczenia w czasie stałym) poznać miejsce, w którym on się znajduje. W najprostszej wersji, mamy tablicę haszującą
\(T[0, \ldots, m-1],\)
oraz funkcję haszującą
\(h: U \longrightarrow \{0,\ldots,m-1\}.\)
Ponieważ nie chcemy, aby nasza struktura zajmowała istotnie więcej miejsca niż jest to konieczne, zwykle \(m = O(n)\), np. \(m = 2n\) lub \(m = n\). Potencjalnie \(h\) może być dowolną funkcją, choć dla nas użyteczne będą takie, których wartość możemy wyliczyć w czasie stałym. Generalnie, elementu \(x\in U\) będziemy szukać w komórce \(T[h(x)]\). Oczywiście zwykle uniwersum \(U\) jest dużo większe niż \(m\), więc niezależnie od tego jakiej funkcji haszującej \(h\) użyjemy, będzie się zdarzać, że dwa elementy \(x\) i \(y\) zostaną odwzorowane w tę samą komórkę tablicy \(T\), tzn. \(h(x)=h(y)\). Taką sytuację nazywamy konfliktem. Zaczynamy od najprostszego, ale całkiem skutecznego sposobu rozwiązywania konfliktów: haszowania przez łańcuchowanie.
Haszowanie przez łańcuchowanie
W haszowaniu przez łańcuchowanie dla każdego \(j\) tablica \(T\) w komórce \(T[j]\) zawiera listę takich elementów \(x\in S\), że \(h(x) = j\). Teraz możemy bardzo łatwo zaimplementować operacje słownikowe: dla danego \(x\) wykonujemy odpowiednią operację na liście \(T[h(x)]\) (Lookup -- sprawdzamy czy lista \(T[h(x)]\) zawiera element; Insert -- wstawienie elementu na listę \(T[h(x)]\); Remove -- usunięcie elementu z listy \(T[h(x)]\)).
W ten sposób czas wykonania operacji na elemencie \(x\) jest proporcjonalny do długości listy \(T[h(x)]\). Chcielibyśmy jakoś ograniczyć długość list elementów odwzorowanych w tę samą komórkę. Widać, że wszystko zależy od tego, jak dobrze dobierzemy funkcję \(h\). Niektóre funkcje \(h\) są w oczywisty sposób ,,złe'', np. funkcje stałe. Czy istnieją ,,dobre'' funkcje?
Gdybyśmy znali z góry zbiór \(S\) być może może udałoby się nawet sprawić, aby każdy element \(S\) został odwzorowany w inną komórkę tablicy \(T\) (w dalszej części wykładu zobaczymy, że istotnie jest to możliwe). Problem polega na tym, że w naszym problemie słownika to funkcję \(h\) ustalamy z góry, przed pojawieniem się ciągu operacji i chcielibyśmy, żeby w każdej chwili w przyszłości elementy \(S\) ,,w miarę jednostajnie'' rozproszyły się po \(\{0,\ldots,m-1\}\). Naturalnymi kandydatkami mogą być takie funkcje, które jednostajnie rozpraszają \(U\), tzn. dla dowolnych \(y_1,y_2\in\{0,\ldots,m-1\}\), \(|h^{-1}(y_1)| \approx |h^{-1}(y_2)|\), np. \(h(x) = x \mod m\). Widać, że takie funkcje działałyby dobrze dla losowych danych.
Często dane, które pojawiają się w praktyce są faktycznie zbliżone do losowych. My jednak stawiamy sobie za cel rozwiązanie, które będzie dobre niezależnie od danych. Od razu spotyka nas rozczarowanie. Zauważmy bowiem, że
Uwaga
Dla \(|U|\gg m\), każda funkcja \(h: U \mapsto \{0,\ldots,m-1\}\) jest zła, tzn. złośliwy przeciwnik, jeśli będzie znał \(h\), może tak dobierać elementy dodawane do \(S\), że \(h(x) = h(y)\) dla każdej pary \(x,y \in S\).
W 1977r Carter i Wegman wpadli na prosty pomysłem na poradzenie sobie z tym problemem. Mianowicie, funkcję haszującą będziemy losowali z pewnej rodziny funkcji -- w ten sposób przeciwnik będzie zmuszony się zabezpieczyć przed całym zbiorem funkcji, a to mu się nie uda. Z pewnym małym prawdopodobieństwem algorytm może wprawdzie dalej działać długo, jednakże to prawdopodobieństwo nie zależy od danych. W następnym rozdziale zastanowimy się, jakie warunki powinny spełniać takie rodziny funkcji i podamy kilka przykładów takich rodzin.
Uniwersalne i niezależne rodziny funkcji haszujących
Przykład 1
Załóżmy, że \(h\) jest losowana jednostajnie ze zbioru wszystkich funkcji, czyli z \(\{0,\ldots,m-1\}^U\). Odpowiada to wylosowaniu niezależnie dla każdego \(x \in U\) wartości \(h(x) \in \{0,\ldots,m-1\}\).
Zauważmy, że wówczas
\[
\mathbb{P}\left[h(x) = h(y) \right] = \left\{ \begin{array}{ll} 1& \mbox{gdy } x = y \\ \frac{1}{m} & \mbox{ gdy } x \neq y .\end{array} \right.
\]
Stąd, dla dowolnego \(x\in U\):
\[
\mathbb{E} |h(x)| = \mathbb{E}\left[\sum_{y \in S} \mathbf{1}_{h(x) = h(y)} \right]= \sum_{y \in S} \mathbb{P}\left[h(x) = h(y)\right] = \left\{ \begin{array}{ll} \frac{n}{m}& \mbox{gdy } x \notin S \\ 1+ \frac{n-1}{m} & \mbox{gdy } x \in S.\end{array} \right.
\]
W powyższych rachunkach korzystamy z liniowości wartości oczekiwanej; notacja \(\mathbf{1}_{A}\) oznacza indykator zdarzenia \(A\), tzn. zmienną losową, która przyjmuje wartość 1 gdy \(A\) się wydarzy i \(0\) w przeciwnym przypadku. Dla \(m = \Omega(n)\) otrzymane wyrażenie jest \(O(1)\), co daje oczekiwany czas stały wszystkich operacji słownikowych. Udało się więc przechytrzyć złośliwego przeciwnika. Ale czy na pewno?
Powstaje pytanie jak szybko wylosować taką funkcję oraz ile pamięci potrzeba, aby ją reprezentować. Pierwsze, co przychodzi do głowy to reprezentowanie \(h\) jako tablicy \(A[1 \ldots |U|]\) liczb od 0 do \(m-1\). Jeśli jednak mamy do dyspozycji tyle pamięci (i czasu na inicjalizację) to nie musimy używać haszowania -- słownik możemy zaimplementować jako tablicę bitową rozmiaru \(|U|\). Z drugiej strony, jeśli naprawdę uprzemy się, żeby \(h\) losować ze zbioru wszystkich funkcji, lepsze rozwiązanie nie istnieje: do przechowywania \(h\) potrzebujemy co najmniej \(|U|\log_2 m\) bitów (za pomocą mniej niż \(|U|\log_2 m\) bitów możemy reprezentować mniej niż \(2^{|U|\log_2 m}=m^{|U|}\) funkcji, czyli nie wszystkie).
Przyjrzyjmy się rachunkom z powyższego przykładu i zastanówmy się czy coś da się jeszcze z niego uratować. Zauważmy, że nie potrzebowaliśmy pełnej losowości, a jedynie własności \(\mathbb{P}\left[h(x) = h(y)\right] \leq \frac{1}m\) dla \(x \neq y\). Tę cechę dostrzegli w 1977 roku Carter i Wegman. Podali oni następującą definicję.
Definicja
Niech \(\mathcal{H} \subseteq \{0,\ldots,m-1\}^{U}\). Powiemy, że \(\mathcal{H}\) jest rodziną \((\alpha,k)\)-uniwersalną, gdy po wybraniu losowej funkcji \(h \in \mathcal{H}\) (tzn. jednostajnie, każdą z równym prawdopodobieństwem), dla dowolnych parami różnych \(x_1, x_2, \ldots, x_k \in U\) zachodzi
\[
\mathbb{P}[h(x_1) = h(x_2) = \ldots = h(x_k)] \leq \frac{\alpha}{m^{k-1}}.
\]
Rodzinę \((1,k)\)-uniwersalną nazywamy krótko $k$-uniwersalną, natomiast na rodzinę 2-uniwersalną mówimy jeszcze krócej: rodzina uniwersalna. Z naszych wcześniejszych rozważań wynika, że
Twierdzenie 2
Jeśli używamy haszowania łańcuchowego z funkcją haszującą \(h\) wybraną losowo z uniwersalnej rodziny funkcji haszujących, to oczekiwane czasy wszystkich operacji słownikowych są stałe.
Rozważmy jeszcze jedną naturalną definicję. Mówimy, że rodzina \(\mathcal{H}\) jest rodziną jednostajną, gdy po wybraniu losowej funkcji \(h \in \mathcal{H}\), dla dowolnego \(x \in U\) zmienna losowa \(h(x)\) ma rozkład jednostajny, tzn. dla każdego \(a \in \{0,\ldots,m-1\}\) zachodzi \(\mathbb{P}[h(x)=a] = \frac{1}{m}\). Widzimy, że jednostajność jest również cechą pożądaną, jednakże łatwo sobie uświadomić, że nie gwarantuje ona efektywności operacji słownikowych.
Zadanie
Podaj przykład jednostajnej rodziny funkcji haszujących \(\mathcal{H}\) oraz ciągu \(n\) operacji Insert oraz Lookup, który wykona się w czasie \(\Omega(n^2)\) niezależnie od tego, jaka funkcja haszująca \(h\) zostanie wylosowana z \(\mathcal{H}\).
W niektórych zastosowaniach wygodnie jest korzystać z rodzin funkcji posiadających jeszcze silniejsze własności niż rodziny uniwersalne.
Definicja
Niech \(\mathcal{H} \subseteq \{0,\ldots,m-1\}^{U}\).
Powiemy, że \(\mathcal{H}\) jest rodziną \(k\)-niezależną (lub silnie \(k\)-uniwersalną), gdy po wybraniu losowej funkcji \(h \in \mathcal{H}\), dla dowolnych parami różnych \(x_1, x_2, \ldots, x_k \in U\) i dowolnych \(y_1, y_2, \ldots , y_k \in \{0,\ldots,m-1\}\) zachodzi
$$
\mathbb{P}[h(x_1) = y_1 \wedge h(x_2) = y_2 \wedge \ldots \wedge h(x_k) = y_k] = \frac{1}{m^{k}}.
$$
Równoważnie możemy to wyrazić jako koniunkcję dwóch warunków (ćwiczenie: pokaż równoważność):
- (\(k\)-niezależność zmiennych) dla dowolnych parami różnych \(x_1, \ldots, x_k \in U\) zmienne losowe \(h(x_1), \ldots, h(x_k)\) są \(k\)-niezależne
- (jednostajność) \(\mathcal{H}\) jest jednostajna.
Zauważmy, że \(k\)-niezależność implikuje \(k\)-uniwersalność (zachęcamy Czytelnika do zweryfikowania tego faktu).
Podamy teraz konkretne przykłady rodzin \((\alpha,k)\)-uniwersalnych i \(k\)-niezależnych. Zauważmy, że rozważana w przykładzie 1 rodzina wszystkich funkcji jest \(k\)-uniwersalna, a nawet \(k\)-niezależna dla dowolnego \(k\). Przykłady, które za chwilę poznamy, będą jednak bardziej praktyczne, w szczególności będą umożliwiały szybkie wylosowanie funkcji, oraz szybkie obliczenie jej wartości w danym elemencie \(U\).