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

20

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.

information-theory data-compression

— Troy McClure
źródło

27

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

f (x, y) = y (y - 1) / 2 + x .

$f(x,y) = y(y-1)/2 + x.$

Ł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$ .

— DW
źródło

1

tak jak 1 + 2 + 3 + ... + y + x fajnie!

— Troy McClure

1

jakieś uogólnienie na nieuporządkowane ints? :) z drugiej strony, wiele quadform z wystarczająco dużymi częściowymi pochodnymi wykona zadanie

— Troy McClure

4

Inna odpowiedź, która może być atrakcyjna ze względu na niski koszt obliczeń: jeśli xi ysą różne, to jeden x-y-1lub y-x-1(oba mod

, oczywiście) mieści się w 31 bitach. Jeśli jest mały, to konkatenuj i ostatnie 31 bitów ; w przeciwnym razie konkatenuje i ostatnie 31 bitów . Odzyskaj dwie liczby, biorąc pierwsze 32 bity jako jedną liczbę i dodając pierwsze 32 bity, ostatnie 31 bitów i stałą 1 (mod

) jako drugą.

2^{32}

$2^{32}$ x-y-1yx-y-1xy-x-1

2^{32}

$2^{32}$

— Daniel Wagner,

1

twoja metoda również ładnie uogólnia dodawanie kolejnych liczb, ponieważ pierwsza liczba jest „właśnie tam”, więc może zostać połączona

— Troy McClure

4

@DW: Czy możesz również dodać, jak wymyśliłeś tę reprezentację? W przeciwnym razie wygląda na to, że wyciągnąłeś go z powietrza.

— Mehrdad

9

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 do $k$ $c_k > \cdots > c_1$

N = \sum_{i = 1}^{k} (\binom{c_{i}}{i}) .

$N = \sum_{i=1}^k \binom{c_i}{i}.$

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)$

— filipos
źródło

4

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)

— Gilles „SO- przestań być zły”
źródło

0

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}$

— Martín-Blas Pérez Pinilla
źródło