Funkcja, która rozprowadza dane wejściowe

Chciałbym wiedzieć, czy istnieje funkcja od liczb n-bitowych do liczb n-bitowych, która ma następujące cechy: $f$

$f$ powinien być bijectywny
Zarówno i powinny być obliczalne dość szybko $f$ $f^{-1}$
$f$ powinien zwrócić liczbę, która nie ma znaczącej korelacji z wprowadzonymi danymi.

Uzasadnienie jest następujące:

Chcę napisać program działający na danych. Niektóre informacje o danych są przechowywane w drzewie wyszukiwania binarnego, w którym klucz wyszukiwania jest symbolem alfabetu. Z czasem dodałem kolejne symbole do alfabetu. Nowe symbole po prostu uzyskają następny bezpłatny numer. Dlatego drzewo zawsze będzie miało niewielkie odchylenie od mniejszych kluczy, co powoduje większe zrównoważenie, niż myślę, że powinno być potrzebne.

Moim pomysłem jest zmieszanie liczb symboli tak, aby były szeroko rozłożone w całym zakresie . Ponieważ liczby symboli mają znaczenie tylko na wejściu i wyjściu, co dzieje się tylko raz, zastosowanie takiej funkcji nie powinno być zbyt drogie. $f$ $[0,2^{64}-1]$

Myślałem o jednej iteracji generatora liczb losowych Xorshift, ale tak naprawdę nie wiem, jak to cofnąć, chociaż teoretycznie powinno to być możliwe.

Czy ktoś zna taką funkcję?
Czy to dobry pomysł?

binary-trees hash binary-arithmetic

— FUZxxl
źródło

Nie jestem ekspertem, ale chyba można użyć permutacji pseudolosowego (patrz na przykład szyfru Feistel )

— Vor

Jeśli zasadniczo obliczasz funkcję skrótu, dlaczego nie użyć skrótu?

— vonbrand

@vonbrand Hashing nie jest odwracalny. Patrz wymaganie nr 2

— FUZxxl,

Dlaczego musi być odwracalny? Co jest złego w tym, że jest odwracalne przez wyszukiwanie?

— vonbrand,

Możesz przechowywać (f (x), x) jako klucze.

— adrianN

Odpowiedzi:

Możesz użyć skrótu Fibonacciego , a mianowicie

. $\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot \frac{\sqrt{5} - 1}{2} \right\rfloor$

Dla dostać liczb parami-wyraźny (o) równomiernie w . Skalowanie do i zaokrąglanie (w dół) pozwala uzyskać równomierne rozłożenie liczb w tym przedziale. $k=1,\dots,n$ $n$ $[0,1]$ $[1..M]$

Na przykład są to skalowane do (lewa pierwotna sekwencja, prawa posortowana): $h_F(1), \dots, h_F(200)$ $[0..10000]$

wprowadź opis zdjęcia tutaj

Jest to przykład tego, co Knuth nazywa multiplikatywnym haszowaniem . Dla rozmiarze słowo komputera, niektóre całkowitą stosunkowo prime do i liczby adresów potrzebnych używamy $w$ $A$ $w$ $M$

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

jako funkcja mieszająca. Powyżej następuje (upewnij się, że możesz go obliczyć z wystarczającą precyzją). Chociaż działa to również z dowolną inną liczbą niewymierną poza, jest to jedna z dwóch liczb, które prowadzą do liczb „najbardziej równomiernie rozmieszczonych”. $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ $\phi^{-1}$

Znajdź więcej w The Art of Computer Programming , Tom 3 autorstwa Donalda Knutha (rozdział 6.4 ze strony 513 w drugim wydaniu). W szczególności dowiesz się, dlaczego uzyskane liczby są odrębne parami (przynajmniej jeśli ) i jak obliczyć funkcję odwrotną, jeśli użyjesz naturalnego i zamiast . $n \ll M$ $A$ $w$ $\phi^{-1}$

— Raphael
źródło

Jak skutecznie obliczyć

f^{- 1}

$f^{-1}$

— frafl

@frafl Mam nadzieję, że moja edycja w jakiś sposób rozwiązuje problem. Oczywiste jest jednak, że te techniki mieszania nie są specjalnie zaprojektowane, aby były skutecznie odwracalne.

— Raphael

Tak, zrobię to, głosuję za tym, jednak nie poleciłbym tego jako przyjętej odpowiedzi.

— frafl

Dla wejść bit ta funkcja działa: $k$

$\mathrm{hash}(n) = (n \bmod 2^{\lceil\frac{k}{2}\rceil})\cdot 2^{\lceil\frac{k}{2}\rceil} + n \,\mathrm{div}\, 2^{\lceil\frac{k}{2}\rceil}$

Jest to odwracalne, ponieważ , i ma pary niesekwencyjne , gdzie . Uwaga: dane wyjściowe i wejściowe mogą się korelować, zwłaszcza jeśli dane wejściowe są w $\mathrm{hash}(\mathrm{hash}(n)) = n$ $\{n,m\}, n < m$ $\mathrm{hash}(m) < \mathrm{hash}(n)$ . $\{1,\dots,2^{\lceil\frac{k}{2}\rceil}-1\}$

Ref: Odwracalna funkcja skrótu

— Reza
źródło

To wygląda prosto i ładnie. Zamierzam to przetestować.

— FUZxxl,

1

$1$

ρ

$\rho$

to całkiem jasne! dla 64-bitów (0x00000000FFFFFFFF) i powinieneś przesunąć (<<) 32 bity. Ta funkcja jest prosta, praktyczna i wystarczająco szybka w praktyce.

— Reza

x \in {1, \dots, 2^{32} - 1}

$x \in \{1,\dots,2^{32}-1\}$

2^{32} x

$2^{32}x$