Komprimieren von zwei ganzen Zahlen ohne Berücksichtigung der Reihenfolge

Vergleicht man ein geordnetes Paar (x, y) mit einem ungeordneten Paar {x, y} (gesetzt), so beträgt die Differenz theoretisch nur ein Bit, da es genau eines einzelnen Bits bedarf, um darzustellen, ob x zuerst kommt oder y.

Wenn wir also eine Menge {x, y} haben, in der x, y zwei verschiedene 32-Bit-Ganzzahlen sind, können wir sie dann in 63 Bits (statt 64) packen? Es sollte möglich sein, die ursprünglichen 32-Bit-Ganzzahlen aus dem 63-Bit-Ergebnis wiederherzustellen, ohne jedoch deren Reihenfolge wiederherstellen zu können.

Ja, das kann man. Wenn , ordnen Sie die Menge der Zahl zu{ x , y $x<y$$\{x,y\}$

Es ist leicht zu zeigen, dass bijektiv ist und daher eindeutig dekodiert werden kann. Wenn , haben wir , daher wird die Menge auf eine 63-Bit-Zahl . Zum Dekodieren können Sie die binäre Suche für oder eine Quadratwurzel ziehen: sollte ungefähr .0 ≤ x < y < 2 32 0 ≤ f ( x , y ) < 2 63 - 2 31 { x , y } f ( x , y ) y y ⌊ $f$$0 \le x < y < 2^{32}$$0 \le f(x,y) < 2^{63} - 2^{31}$$\{x,y\}$$f(x,y)$$y$$y$$\lfloor \sqrt{2 f(x,y)} \rfloor$

Beachten Sie als Ergänzung zu DWs Antwort, dass dies ein besonderer Fall des kombinatorischen , das eine streng abnehmende Folge von nicht-negativen ganzen Zahlen zu kompakt abbildetc k > ⋯ > c 1 N = k ∑ i = 1 ( c $k$$c_k > \cdots > c_1$

Diese Nummer hat eine einfache Interpretation. Wenn wir diese Sequenzen lexikographisch ordnen, zählt die Anzahl der kleineren Sequenzen.$N$

zum Dekodieren einfach den größten Wert zu, so dass und dekodieren Sie als -Sequenz.( c $c_k$N- ( c$\binom{c_k}{k} \leq N$ (k-1$N - \binom{c_k}{k}$$(k-1)$

Die Gesamtzahl ungeordneter Zahlenpaare in einer Menge von ist . Die Gesamtzahl der ungeordneten Paare unterschiedlicher Zahlen beträgt . Es werden Bits benötigt, um ein geordnetes Zahlenpaar darzustellen. Wenn Sie ein Bit weniger haben, können Sie Elemente mit einem Leerzeichen von bis zu . Die Anzahl ungeordneter, nicht notwendigerweise unterschiedlicher Paare ist etwas mehr als die Hälfte der Anzahl geordneter Paare, sodass Sie in der Darstellung kein Bit speichern können. Die Anzahl der ungeordneten unterschiedlichen Paare ist etwas geringer als die Hälfte, sodass Sie ein wenig sparen können.$N$$N(N+1)/2$$N(N-1)/2$$2 \log_2(N) = \log_2(N^2)$$N^2/2$

Für ein praktisches Schema, das einfach zu berechnen ist und bei dem eine Zweierpotenz ist, können Sie an der bitweisen Darstellung arbeiten. Nehmen Sie wobei der XOR-Operator (bitweise exklusiv oder) ist. Das Paar kann entweder aus oder wiederhergestellt werden . Jetzt werden wir nach einem Trick suchen, um ein Bit im zweiten Teil zu speichern und und eine symmetrische Rolle damit die Reihenfolge nicht wiederhergestellt werden kann. Angesichts der obigen Kardinalitätsberechnung wissen wir, dass dieses Schema in dem Fall, in dem nicht funktioniert .$N$$a = x \oplus y$$\oplus$$\{x,y\}$$(a, x)$$(a, y)$$x$$y$$x=y$

Wenn gibt es eine Bitposition, an der sie sich unterscheiden. Ich schreibe für das te Bit von (dh ) und ebenso für . Es sei die kleinste Bitposition, an der und unterschiedlich sind: ist das kleinste so dass . ist das kleinste so dass : wir können von erholen . Sei entweder oder$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$mit dem ten Bit gelöscht (dh oder ) - um die Konstruktion symmetrisch zu machen, wähle wenn und , und wähle wenn und . Verwenden Sie als kompakte Darstellung des Paares. Das ursprüngliche Paar kann wiederhergestellt werden, indem das in gesetzte Bit niedrigster Ordnung berechnet wird , ein 0-Bit an dieser Position in eingefügt wird (was eines von oder ergibt ) und das xor dieser Zahl mit genommen wird$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$ (ergibt das andere Element des Paares).

In dieser Darstellung kann eine beliebige Zahl ungleich Null sein, und kann eine beliebige Zahl mit der Hälfte liegen. Dies ist eine Überprüfung der geistigen Gesundheit: Wir erhalten genau die erwartete Anzahl von Darstellungen ungeordneter Paare.$a$$b$

In Pseudo - Code, mit ^, &, |, <<, >>, ~wobei C-like bitweisen Operatoren (XOR, AND, OR, Linksverschiebung, Verschiebung nach rechts, Komplement):

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)

Ein nichtkonstruktiver Beweis: Es gibt ungeordnet Paare verschiedener 32-Bit-Ganzzahlen.$(2^{32}\times 2^{32} - 2^{32})/2 = 2^{31}(2^{32}-1)<2^{63}$