Kompresowanie dwóch liczb całkowitych z pominięciem kolejności

Porównując parę uporządkowaną (x, y) z parą nieuporządkowaną {x, y} (zestaw), a następnie teoretycznie, różnica wynosi tylko jeden bit, ponieważ to, czy x jest pierwsze, czy y wymaga dokładnie jednego bitu do przedstawienia.

Więc jeśli otrzymamy zestaw {x, y}, gdzie x, y to dwie różne 32-bitowe liczby całkowite, czy możemy spakować je w 63 bitach (raczej 64)? Powinno być możliwe odzyskanie oryginalnych 32-bitowych liczb całkowitych z wyniku 63-bitowego, ale bez możliwości odzyskania ich kolejności.

Tak, można. Jeśli $x<y$ , zamapuj zestaw $\{x,y\}$ na liczbę

Łatwo jest wykazać, że $f$ jest bijectywny, a zatem można go jednoznacznie odkodować. Ponadto, gdy $0 \le x < y < 2^{32}$ , mamy $0 \le f(x,y) < 2^{63} - 2^{31}$ , więc mapuje to zestaw $\{x,y\}$ na 63-bitową liczbę $f(x,y)$ . Aby zdekodować, możesz użyć wyszukiwania binarnego na $y$ lub użyć pierwiastka kwadratowego: $y$ powinno wynosić około $\lfloor \sqrt{2 f(x,y)} \rfloor$.

Jako dodatek do odpowiedzi DW, zauważ, że jest to szczególny przypadek kombinatorycznego systemu liczb , który zwięźle odwzorowuje ściśle malejącą sekwencję liczb całkowitych nieujemnych c k > ⋯ > c 1 do $k$$c_k > \cdots > c_1$

Liczba ta ma prostą interpretację. Jeśli uporządkujemy te sekwencje leksykograficzne, wówczas zlicza liczbę mniejszych sekwencji.$N$

Aby zdekodować, po prostu przypisz największą wartość, taką jak i zdekoduj jako sekwencję .$c_k$$\binom{c_k}{k} \leq N$$N - \binom{c_k}{k}$$(k-1)$

Całkowita liczba nieuporządkowanych par liczb w zbiorze wynosi . Całkowita liczba nieuporządkowanych par odrębnych liczb wynosi . Potrzeba bitów do przedstawienia uporządkowanej pary liczb, a jeśli masz jeden bit mniej, możesz reprezentować elementy przestrzeni do . Liczba nieuporządkowanych niekoniecznie odrębnych par jest nieco większa niż połowa liczby uporządkowanych par, więc nie możesz zapisać trochę w reprezentacji; liczba nieuporządkowanych odrębnych par jest nieco mniejsza niż połowa, więc możesz trochę zaoszczędzić.$N$$N(N+1)/2$$N(N-1)/2$$2 \log_2(N) = \log_2(N^2)$$N^2/2$

Aby uzyskać praktyczny schemat, który jest łatwy do obliczenia, przy czym jest potęgą 2, możesz pracować z reprezentacją bitową. Weźmy gdzie jest operatorem XOR (bitowe wykluczenie lub). Pary można odzyskać z lub . Teraz szukamy sposobu na zaoszczędzenie jednego bitu w drugiej części i nadanie i symetrycznej roli, aby nie można było odzyskać kolejności. Biorąc pod uwagę powyższe obliczenia liczności, wiemy, że ten schemat nie zadziała w przypadku, gdy .$N$$a = x \oplus y$$\oplus$$\{x,y\}$$(a, x)$$(a, y)$$x$$y$$x=y$

Jeśli to jest trochę pozycji, w której się różnią. Napiszę dla tego bitu (tj. ), i podobnie dla . Niech przyjmie najmniejszą pozycję bitu, w której i różnią się: jest najmniejszą taką, że . jest najmniejszym takim, że : możemy odzyskać z . Niech będzie albo albo$x \ne y$$x_i$$i$$x$$x = \sum_i x_i 2^i$$y$$k$$x$$y$$k$$i$$x_i \ne y_i$$k$$i$$a_i = 1$$k$$a$$b$$x$$y$z tym bitem skasowanym (tj. lub ) - aby konstrukcja była symetryczna, wybierz jeśli i , i wybierz jeśli i . Użyj jako zwartej reprezentacji pary. Pierwotną parę można odzyskać, obliczając bit najniższego rzędu ustawiony w , wstawiając bit 0 w tej pozycji (uzyskując jeden z lub ) i biorąc xor tej liczby za pomocą$k$$b = \sum_{i<k} x_i 2^i + \sum_{i>k} x_i 2^{i-1}$$b = \sum_{i<k} y_i 2^i + \sum_{i>k} y_i 2^{i-1}$$x$$x_k=0$$y_k=1$$y$$x_k=1$$y_k=0$$(a,b)$$a$$b$$x$$y$$a$ (uzyskując drugi element pary).

W tej reprezentacji może być dowolną liczbą niezerową, a może być dowolną liczbą o połowie zakresu. Jest to kontrola rozsądku: otrzymujemy dokładnie oczekiwaną liczbę reprezentacji nieuporządkowanych par.$a$$b$

W Pseudokod, z ^, &, |, <<, >>, ~to C-like operatorów bitowe (XOR, AND, OR, lewy shift prawym zmianowych, dopełniacza):

encode(x, y) =
  let a = x ^ y
  let k = lowest_set_bit_position(a)
  let low_mask = (1 << k) - 1
  let z = if x & (1 << k) = 0 then x else y
  return (a, (z & low_mask) | (z & ~low_mask) >> 1)
decode(a, b) =
  let k = lowest_set_bit_position(a)
  let low_mask = (1 << k) - 1
  let x = (b & low_mask) | ((b & ~low_mask) << 1)
  return (x, a ^ x)

Niekonstruktywny dowód: istnieją nieuporządkowane pary różnych 32-bitowych liczb całkowitych.$(2^{32}\times 2^{32} - 2^{32})/2 = 2^{31}(2^{32}-1)<2^{63}$