Doskonała funkcja haszująca

Doskonała funkcja skrótu dla czterech pokazanych imion

Minimalna idealna funkcja skrótu dla czterech pokazanych nazw

W informatyce idealna funkcja haszująca $h$ dla zbioru $S$ to funkcja haszująca , która odwzorowuje różne elementy w $S$ na zbiór $liczb$ całkowitych bez kolizji . Z matematycznego punktu widzenia jest to funkcja iniekcyjna .

Doskonałe funkcje skrótu mogą być użyte do zaimplementowania tabeli przeglądowej ze stałym czasem dostępu w najgorszym przypadku. Idealna funkcja skrótu może, jak każda funkcja skrótu , zostać użyta do zaimplementowania tablic skrótów , z tą zaletą, że nie trzeba implementować rozwiązania kolizji . Ponadto, jeśli klucze nie są danymi i jeśli wiadomo, że zapytane klucze będą ważne, to klucze nie muszą być przechowywane w tabeli przeglądowej, co oszczędza miejsce.

Wadą doskonałych funkcji mieszających jest to, że $S$ musi być znane do budowy idealnej funkcji mieszającej. Niedynamiczne doskonałe funkcje mieszające muszą zostać zrekonstruowane, jeśli $S$ się zmieni. W przypadku często zmieniających się $S$ dynamicznych doskonałych funkcji skrótu można użyć kosztem dodatkowej przestrzeni. Zapotrzebowanie na miejsce do przechowywania idealnej funkcji skrótu wynosi $O (n)$ .

Ważnymi parametrami wydajnościowymi dla doskonałych funkcji mieszających są czas oceny, który powinien być stały, czas konstrukcji i rozmiar reprezentacji.

Aplikacja

Doskonałej funkcji skrótu z wartościami w ograniczonym zakresie można użyć do wydajnych operacji wyszukiwania, umieszczając klucze z $S$ (lub inne powiązane wartości) w tabeli przeglądowej indeksowanej przez dane wyjściowe funkcji. Następnie można sprawdzić, czy klucz jest obecny w $S$ , lub wyszukać wartość powiązaną z tym kluczem, szukając go w komórce tabeli. W najgorszym przypadku każde takie wyszukiwanie zajmuje stały czas . Dzięki doskonałemu haszowaniu powiązane dane można odczytywać lub zapisywać za pomocą jednego dostępu do tabeli.

Wykonywanie doskonałych funkcji mieszających

Ważnymi parametrami wydajności dla doskonałego haszowania są rozmiar reprezentacji, czas oceny, czas budowy, a dodatkowo wymagany zakres. ${\ displaystyle {\ frac {m} {n}}}$ . Czas oceny może być tak szybki jak $O (1)$ , co jest optymalne. Czas budowy musi wynosić co najmniej $O (n)$ , ponieważ każdy element w $S$ musi być rozważony, a $S$ zawiera $n$ elementów. Tę dolną granicę można osiągnąć w praktyce.

Dolna granica rozmiaru reprezentacji zależy od $m$ i $n$ . Niech $m = (1+ε) n$ i $h$ będą doskonałą funkcją mieszającą. Dobrym przybliżeniem dolnej granicy jest ${\ Displaystyle \ log e- \ varepsilon \ log {\ Frac {1+ \ varepsilon } {\ varepsilon}}}$ Bity na element. Dla minimalnego doskonałego mieszania, $ε = 0$ , dolna granica to $log e \approx 1,44$ bitów na element.

Budowa

Doskonałą funkcję mieszającą dla określonego zbioru $S$ , którą można oszacować w stałym czasie i z wartościami w małym zakresie, można znaleźć za pomocą losowego algorytmu w liczbie operacji proporcjonalnej do wielkości S. Oryginalna konstrukcja Fredman, Komlós i Szemerédi (1984) używają schematu dwupoziomowego do odwzorowania zbioru $S złożonego$ z $n$ elementów na zakres $O (n)$ indeksów, a następnie odwzorowania każdego indeksu na zakres wartości skrótu. Pierwszy poziom ich konstrukcji wybiera dużą liczbę pierwszą $p$ (większy niż rozmiar wszechświata, z którego narysowano $S ) oraz parametr$ $k$ i odwzorowuje każdy element $x$ z $S$ na indeks

{\ Displaystyle g (x) = (kx {\ bmod {p}}) {\ bmod {n}}.}

Jeśli $k$ jest wybrane losowo, ten krok prawdopodobnie będzie miał kolizje, ale liczba elementów $n i$ , które są jednocześnie odwzorowane na ten sam indeks $i,$ prawdopodobnie będzie niewielka. Drugi poziom ich konstrukcji przypisuje każdemu indeksowi i rozłączne zakresy liczb $całkowitych$ $O (n i 2)$ . Używa drugiego zestawu liniowych funkcji modularnych, po jednej dla każdego indeksu $i$ , aby odwzorować każdy element $x$ z $S$ na zakres powiązany z $g (x)$ .

Jak pokazują Fredman, Komlós i Szemerédi (1984) , istnieje wybór parametru $k$ taki, że suma długości przedziałów dla $n$ różnych wartości $g (x)$ wynosi $O (n)$ . Dodatkowo dla każdej wartości $g (x)$ istnieje liniowa funkcja modularna, która odwzorowuje odpowiedni podzbiór $S$ na zakres powiązany z tą wartością. Zarówno $k$ , jak i funkcje drugiego poziomu dla każdej wartości $g (x)$ , można znaleźć w czasie wielomianowym , wybierając losowo wartości, aż do znalezienia takiej, która działa.

Sama funkcja haszująca wymaga przestrzeni dyskowej $O (n)$ do przechowywania $k$ , $p$ i wszystkich liniowych funkcji modułowych drugiego poziomu. Obliczenie wartości skrótu danego klucza $x$ można wykonać w stałym czasie, obliczając $g (x)$ , wyszukując funkcję drugiego poziomu powiązaną z $g (x)$ i stosując tę funkcję do $x$ . Zmodyfikowana wersja tego dwupoziomowego schematu z większą liczbą wartości na najwyższym poziomie może zostać wykorzystana do skonstruowania idealnej funkcji mieszającej, która odwzorowuje $S$ na mniejszy zakres długości $n + o (n)$ .

Nowsza metoda konstruowania idealnej funkcji skrótu została opisana przez Belazzougui, Botelho i Dietzfelbinger (2009) jako „hash, displace, and compress”. Tutaj funkcja skrótu pierwszego poziomu $g$ jest również używana do mapowania elementów na zakres $r$ liczb całkowitych. Element $x \in S$ jest przechowywany w zasobniku $B g(x)$ .

Następnie, w malejącej kolejności wielkości, elementy każdego zasobnika są haszowane przez funkcję mieszającą sekwencji niezależnych całkowicie losowych funkcji mieszających $(Φ 1, Φ 2, Φ 3, ...)$ , zaczynając od $Φ 1$ . Jeżeli funkcja haszująca nie generuje żadnych kolizji dla zasobnika, a wynikowe wartości nie są jeszcze zajęte przez inne elementy z innych zasobników, funkcja jest wybierana dla tego zasobnika. Jeśli nie, testowana jest następna funkcja skrótu w sekwencji.

Aby ocenić idealną funkcję haszującą $h (x)$ wystarczy zapisać odwzorowanie σ indeksu wiadra $g (x)$ na poprawną funkcję haszującą w sekwencji, w wyniku czego $h(x) = Φ σ(g(x))$ .

Wreszcie, aby zmniejszyć rozmiar reprezentacji, ( $σ(i)) 0 \leq i < r$ są skompresowane do postaci, która nadal umożliwia ocenę w $O (1)$ .

To podejście wymaga czasu liniowego w $n$ dla konstrukcji i stałego czasu oceny. Rozmiar reprezentacji jest w $O (n)$ i zależy od osiągniętego zasięgu. Na przykład, przy $m = 1,23 n$ Belazzougui, Botelho i Dietzfelbinger (2009) osiągnęli rozmiar reprezentacji między 3,03 bitów/klucz a 1,40 bitów/klucz dla podanego przykładowego zestawu 10 milionów wpisów, przy niższych wartościach wymagających dłuższego czasu obliczeń. Dolna granica miejsca w tym scenariuszu wynosi 0,88 bitów/klucz.

Pseudo kod

         algorytm  hash, displace, and compress  to  (1) Podziel S na segmenty  $B i := g -1 ({i})\capS,0 \leq i < r$  (2) Sortuj segmenty B _i w porządku malejącym według rozmiaru |B _ja | (3) Zainicjuj tablicę T[0...m-1] zerami (4)   dla wszystkich  i  ∈[r], w kolejności od (2),  wykonaj  (5)  dla  l  ←  1,2,... (6)  powtórne  tworzenie K _i ←  {  $Φ$ _l (x)|x  ∈        B _ja } (6)  aż do  |K _ja |=|B _ja |  i  K _i ∩{j|T[j]=1}=  ∅ (7)  niech  σ(i):= udane l (8)  dla wszystkich  j  ∈  K _i niech  T[j]:=  1 (9) Przekształć (σ _i ) _0≤i<r do postaci skompresowanej, zachowując dostęp   $O (1)$  .

Dolne granice przestrzeni

Użycie $O (n)$ słów informacji do przechowywania funkcji Fredmana, Komlósa i Szemerédiego (1984) jest prawie optymalne: każda doskonała funkcja mieszająca, którą można obliczyć w stałym czasie, wymaga co najmniej liczby bitów, która jest proporcjonalna do rozmiar $S.$ _

Dla minimalnych doskonałych funkcji mieszających dolna granica teoretycznej przestrzeni informacyjnej wynosi

{\ Displaystyle \ log _ {2} e \ około 1,44}

bity/klucz.

Dla doskonałych funkcji mieszających zakłada się najpierw, że zakres $h$ jest ograniczony przez $n$ jako $m = (1+ε) n$ . Ze wzorem podanym przez $rozmiar$ $, U | = u$ Botelho i Dietzfelbinger (2009) oraz dla wszechświata | dąży do nieskończoności, dolna granica przestrzeni wynosi

{\ Displaystyle \ log _ {2} e- \ varepsilon \ log {\ Frac {1+ \ varepsilon} {\ varepsilon}}}

bity/klucz, minus $log(n)$ bitów ogółem.

Rozszerzenia

Tożsamość adresu pamięci

Trywialny, ale wszechobecny przykład doskonałego mieszania jest niejawny w (wirtualnej) przestrzeni adresowej pamięci komputera. Ponieważ każdy bajt pamięci wirtualnej jest odrębnym, unikalnym, bezpośrednio adresowalnym miejscem przechowywania, wartość adresu (początkowego) dowolnego obiektu przechowywanego w pamięci można uznać za de facto doskonały skrót tego obiektu w całym zakresie adresów pamięci.

Dynamiczne doskonałe mieszanie

Używanie idealnej funkcji skrótu jest najlepsze w sytuacjach, w których często sprawdzany jest duży zestaw $S$ , który jest rzadko aktualizowany. Dzieje się tak, ponieważ jakakolwiek modyfikacja zbioru $S$ może spowodować, że funkcja skrótu nie będzie już idealna dla zmodyfikowanego zbioru. Rozwiązania, które aktualizują funkcję skrótu za każdym razem, gdy zestaw jest modyfikowany, są znane jako dynamiczne doskonałe mieszanie , ale metody te są stosunkowo skomplikowane do wdrożenia.

Minimalna doskonała funkcja skrótu

$0$ Minimalna doskonała funkcja mieszająca to idealna funkcja mieszająca, która odwzorowuje $n$ kluczy na $n$ kolejnych liczb całkowitych - zwykle liczby od do $n - 1$ lub od $1$ do $n$ . Bardziej formalny sposób wyrażenia tego jest następujący: Niech $j$ i $k$ będą elementami jakiegoś skończonego zbioru $S$ . Wtedy $h$ jest minimalną idealną funkcją mieszającą wtedy i tylko wtedy, gdy $h (j) = h (k)$ implikuje $j = k$ ( iniektywność ) i istnieje liczba całkowita $a$ taka , że zakres $h$ wynosi $a .. a + | S | - 1$ . Udowodniono, że minimalny idealny schemat skrótu ogólnego przeznaczenia wymaga co najmniej $lg e \approx 1,44$ bitów/klucz. Chociaż to ograniczenie przestrzenne zostało osiągnięte dzięki pracom teoretycznym, w praktyce najbardziej znane schematy minimalnego doskonałego mieszania wymagają około 1,56 bitów na klucz, jeśli mają wystarczająco dużo czasu.

k-idealne mieszanie

Funkcja mieszająca jest $k$ -idealna, jeśli co najwyżej $k$ elementów z $S$ jest odwzorowanych na tę samą wartość w zakresie. Algorytm „hash, displace, and compress” może być użyty do konstruowania $k$ -perfekcyjnych funkcji mieszających, dopuszczając do $k$ kolizji. Zmiany niezbędne do osiągnięcia tego celu są minimalne i zostały podkreślone w dostosowanym pseudokodzie poniżej:

          (4)  dla wszystkich  i  ∈[r], w kolejności od (2),  wykonaj  (5)  dla  l  ←  1,2,... (6)  powtórz  tworzenie K _i ←  {  $Φ$ _l (x)|x  ∈  B _i } (6)  aż do  |K _i |=|B _i |  i  K _ja ∩ {j|  T[j]=k  }=  ∅ (7)  niech  σ(i):= udane l (8)  dla wszystkich  j  ∈     K _i ustaw  T[j]←T[j]+1

Zachowanie porządku

Minimalna doskonała funkcja mieszająca $F$ zachowuje kolejność , jeśli klucze są podane w jakiejś kolejności $a 1, a 2, ..., a n$ i dla dowolnych kluczy $a j$ i $a k$ , $j < k$ implikuje $_F (a j) < F (ak)$ . W tym przypadku wartość funkcji jest po prostu pozycją każdego klucza w posortowanej kolejności wszystkich kluczy. Prostą implementacją zachowujących porządek minimalnie doskonałych funkcji mieszających ze stałym czasem dostępu jest użycie (zwykłej) idealnej funkcji mieszającej lub haszowanie z kukułką do przechowywania tabeli przeglądowej pozycji każdego klawisza. Jeśli klucze, które mają być haszowane, są same przechowywane w posortowanej tablicy, możliwe jest przechowywanie niewielkiej liczby dodatkowych bitów na klucz w strukturze danych, której można użyć do szybkiego obliczenia wartości skrótu. Zachowujące porządek minimalne doskonałe funkcje mieszające wymagają koniecznie $Ω (n log n)$ bitów do reprezentacji.

Powiązane konstrukcje

Prostą alternatywą dla idealnego haszowania, która umożliwia również dynamiczne aktualizacje, jest haszowanie kukułkowe . Ten schemat odwzorowuje klucze na dwie lub więcej lokalizacji w zakresie (w przeciwieństwie do idealnego mieszania, w którym każdy klucz jest odwzorowywany na jedną lokalizację), ale robi to w taki sposób, że klucze można przypisać jeden do jednego do lokalizacji, do których zostały mapowane. Wyszukiwania z tym schematem są wolniejsze, ponieważ należy sprawdzić wiele lokalizacji, ale mimo to zajmują stały czas w najgorszym przypadku.

Dalsza lektura

Richard J. Cichelli. Minimalne doskonałe funkcje skrótu są proste , Komunikacja ACM, tom. 23, nr 1, styczeń 1980.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie trzecie. MIT Press, 2009. ISBN 978-0262033848 . Sekcja 11.5: Idealne mieszanie, s. 267, 277–282.
Fabiano C. Botelho, Rasmus Pagh i Nivio Ziviani. „Doskonałe haszowanie w aplikacjach do zarządzania danymi” .
Fabiano C. Botelho i Nivio Ziviani . „Zewnętrzne doskonałe mieszanie dla bardzo dużych zestawów kluczy” . 16th ACM Conference on Information and Knowledge Management (CIKM07), Lizbona, Portugalia, listopad 2007.
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh i Sebastiano Vigna. „Monotoniczne minimalne doskonałe mieszanie: przeszukiwanie posortowanej tabeli z dostępem O (1)” . W materiałach z 20. dorocznego sympozjum ACM-SIAM poświęconego matematyce dyskretnej (SODA), Nowy Jork, 2009. ACM Press.
Marshall D. Mózg i Alan L. Tharp. „Niemal idealne mieszanie dużych zestawów słów” . Oprogramowanie — praktyka i doświadczenie, tom. 19(10), 967-078, październik 1989. John Wiley & Sons.
Douglas C. Schmidt, GPERF: doskonały generator funkcji skrótu , raport C++, SIGS, tom. 10, nr 10, listopad/grudzień 1998.

Linki zewnętrzne

gperf to doskonały generator skrótów Open Source C i C++ (bardzo szybki, ale działa tylko dla małych zestawów)
Minimal Perfect Hashing (algorytm bob) autorstwa Boba Jenkinsa
cmph : C Minimal Perfect Hashing Library, implementacje open source dla wielu (minimalnych) doskonałych skrótów (działa dla dużych zestawów)
Sux4J : open source, monotonne, minimalne, doskonałe mieszanie w Javie
MPHSharp : doskonałe metody mieszania w C#
BBHash : minimalna idealna funkcja skrótu w C++ tylko nagłówkowym
Perfect::Hash , doskonały generator skrótów w Perlu, który tworzy kod w C. Ma sekcję „wcześniejszy stan techniki”, na którą warto zwrócić uwagę.