Mengompresi dua bilangan bulat dengan mengabaikan pesanan

Membandingkan pasangan berurutan (x, y) dengan pasangan yang tidak berurutan {x, y} (set), maka informasi secara teoritis, perbedaannya hanya satu bit, karena apakah x lebih dulu atau y membutuhkan tepat satu bit untuk diwakili.

Jadi, jika kita diberikan satu set {x, y} di mana x, y adalah dua bilangan bulat 32-bit yang berbeda, dapatkah kita mengemasnya menjadi 63 bit (bukan 64)? Seharusnya dimungkinkan untuk memulihkan bilangan bulat 32 bit asli dari hasil 63 bit, tetapi tanpa dapat memulihkan pesanan mereka.

Ya, bisa. Jika , petakan set ke nomor tersebut$x<y$$\{x,y\}$

Mudah untuk menunjukkan bahwa adalah kata sifat, dan dengan demikian ini dapat diterjemahkan secara unik. Juga, ketika , kita memiliki , jadi ini memetakan set ke nomor 63-bit . Untuk memecahkan kode, Anda dapat menggunakan pencarian biner pada , atau mengambil akar kuadrat: harus kira-kira .$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$

Sebagai tambahan untuk jawaban DW, perhatikan bahwa ini adalah kasus khusus dari Combinatorial Number System , yang memetakan secara ketat urutan bilangan bulat non-negatif ke c k > ⋯ > c 1 N = k ∑ i = 1 ( c $k$$c_k > \cdots > c_1$

Angka ini memiliki interpretasi sederhana. Jika kita memesan urutan ini secara leksikografis, maka menghitung jumlah urutan yang lebih kecil.$N$

Untuk mendekode, cukup berikan nilai terbesar sehingga dan dekode sebagai -setelahnya.( c $c_k$N- ( c$\binom{c_k}{k} \leq N$ (k-1$N - \binom{c_k}{k}$$(k-1)$

Jumlah total pasangan angka yang tidak berurutan dalam satu set adalah . Jumlah pasangan unordered dari yang berbeda angka adalah . Dibutuhkan bit untuk mewakili pasangan angka yang terurut, dan jika Anda memiliki lebih sedikit, Anda dapat mewakili elemen ruang hingga . Jumlah pasangan tidak-tidak-harus-tidak berurutan sedikit lebih dari setengah jumlah pasangan yang dipesan sehingga Anda tidak dapat menyimpan sedikit dalam representasi; jumlah pasangan berbeda yang tidak berurutan sedikit kurang dari setengah, sehingga Anda dapat menghemat sedikit.$N$$N(N+1)/2$$N(N-1)/2$$2 \log_2(N) = \log_2(N^2)$$N^2/2$

Untuk skema praktis yang mudah dihitung, dengan menjadi kekuatan 2, Anda bisa bekerja pada representasi bitwise. Ambil mana adalah XOR (bitwise eksklusif atau). Pasangan dapat dipulihkan dari atau . Sekarang kita akan mencari trik untuk menyimpan satu bit di bagian kedua, dan memberikan peran simetris ke dan sehingga pesanan tidak dapat dipulihkan. Dengan perhitungan kardinalitas di atas, kami tahu skema ini tidak akan berfungsi jika .$N$$a = x \oplus y$$\oplus$$\{x,y\}$$(a, x)$$(a, y)$$x$$y$$x=y$

Jika maka ada beberapa posisi bit di mana mereka berbeda. Saya akan menulis untuk bit ke- (yaitu ), dan juga untuk . Biarkan mengambil posisi bit terkecil di mana dan berbeda: adalah terkecil sehingga . adalah terkecil sehingga : kita dapat memulihkan dari . Biarkan menjadi ataux $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$dengan bit dihapus (yaitu atau ) - untuk membuat simetris konstruksi, pilih jika dan , dan pilih jika dan . Gunakan sebagai representasi kompak dari pasangan. Pasangan asli dapat dipulihkan dengan menghitung bit urutan terendah yang diatur dalam , memasukkan 0 bit pada posisi ini dalam (menghasilkan salah satu atau ), dan mengambil xor dari angka itu dengan$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$ (menghasilkan elemen pasangan lainnya).

Dalam representasi ini, bisa berupa bilangan bukan nol, dan dapat berupa bilangan apa saja dengan setengah kisaran. Ini adalah pemeriksaan kewarasan: kami mendapatkan persis jumlah yang diharapkan dari representasi pasangan tidak berurutan.$a$$b$

Dalam pseudocode, dengan ^, &, |, <<, >>, ~menjadi C-seperti operator bitwise (xor, dan, atau, kiri-shift, kanan-shift, pelengkap):

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)

Bukti nonkonstruktif: ada tidak berurutan pasang bilangan bulat 32-bit yang berbeda.$(2^{32}\times 2^{32} - 2^{32})/2 = 2^{31}(2^{32}-1)<2^{63}$