Compression de deux entiers sans tenir compte de l'ordre

20

En comparant une paire ordonnée (x, y) à une paire non ordonnée {x, y} (ensemble), puis en théorie, la différence n'est que d'un bit, car si x vient en premier ou y nécessite exactement un seul bit pour représenter.

Donc, si on nous donne un ensemble {x, y} où x, y sont deux entiers 32 bits différents, pouvons-nous les regrouper en 63 bits (plutôt 64)? Il devrait être possible de récupérer les entiers 32 bits d'origine à partir du résultat 63 bits, mais sans pouvoir récupérer leur ordre.

Troy McClure
la source

Réponses:

27

Oui, on peut. Si , mappez l'ensemble au nombre{ x , y }x<y{x,y}

f(x,y)=y(y1)/2+x.

Il est facile de montrer que est bijectif, et donc cela peut être décodé de manière unique. De plus, lorsque , nous avons , donc cela mappe l'ensemble à un nombre 63 bits . Pour décoder, vous pouvez utiliser la recherche binaire sur , ou prendre une racine carrée: doit être approximativement .0 x < y < 2 32 0 f ( x , y ) < 2 63 - 2 31 { x , y } f ( x , y ) y y f0x<y<2320f(x,y)<263231{x,y}f(x,y)yy2f(x,y)

DW
la source
1
comme 1 + 2 + 3 + ... + y + x sympa!
Troy McClure
1
une généralisation à n ints non ordonnés? :) après réflexion, de nombreux quadforms avec des dérivées partielles suffisamment grandes feront l'affaire
Troy McClure
4
Une autre réponse qui peut être intéressante pour son faible coût de calcul: si xet ysont différents, alors l'un x-y-1ou l' autre y-x-1(les deux mod , bien sûr) tient sur 31 bits. Si est petit, alors concatène et les 31 derniers bits de ; sinon concaténer et les 31 derniers bits de . Récupérez les deux nombres en prenant les 32 premiers bits comme un nombre et en ajoutant les 32 premiers bits, les 31 derniers bits et la constante 1 (mod ) comme l'autre. 2 32232x-y-1yx-y-1xy-x-1232
Daniel Wagner
1
votre méthode se généralise également bien pour ajouter plus de nombres, car le premier nombre est "juste là", donc vous pouvez enchaîner
Troy McClure
4
@DW: Pourriez-vous également indiquer comment vous en êtes arrivé à cette représentation? Sinon, il semble que vous l'ayez sorti de l'air.
Mehrdad
9

En complément de la réponse de DW, notez qu'il s'agit d'un cas particulier du système de nombres combinatoires , qui mappe de manière compacte une séquence strictement décroissante de entiers non négatifs à c k > > c 1 N = k i = 1 ( c ikck>>c1

N=i=1k(cii).

Ce nombre a une interprétation simple. Si nous ordonnons lexicographiquement ces séquences, alors compte le nombre de séquences plus petites.N

Pour décoder, attribuez simplement à la plus grande valeur telle que et décodez comme une séquence .ck(ckk)NN(ckk)(k1)

filipos
la source
4

Le nombre total de paires non ordonnées de nombres dans un ensemble de est . Le nombre total de paires non ordonnées de nombres distincts est . Il faut bits pour représenter une paire ordonnée de nombres, et si vous avez un bit de moins, vous pouvez représenter des éléments d'un espace allant jusqu'à . Le nombre de paires non ordonnées non nécessairement distinctes est légèrement supérieur à la moitié du nombre de paires ordonnées, vous ne pouvez donc pas enregistrer un peu dans la représentation; le nombre de paires distinctes non ordonnées est légèrement inférieur à la moitié, vous pouvez donc économiser un peu.NN(N+1)/2N(N1)/22log2(N)=log2(N2)N2/2

Pour un schéma pratique facile à calculer, étant une puissance de 2, vous pouvez travailler sur la représentation au niveau du bit. Prenez où est l'opérateur XOR (bitwise exclusif ou). La paire peut être récupérée à partir de ou . Nous allons maintenant chercher une astuce pour enregistrer un bit dans la deuxième partie, et donner un rôle symétrique à et afin que l'ordre ne puisse pas être récupéré. Étant donné le calcul de cardinalité ci-dessus, nous savons que ce schéma ne fonctionnera pas dans le cas où .Na=xy{x,y}(a,x)(a,y)xyx=y

Si alors il y a une position de bits où ils diffèrent. J'écrirai pour le ème bit de (ie ), et de même pour . Soit la plus petite position binaire où et diffèrent: est le plus petit tel que . est le plus petit tel que : on peut récupérer partir de . Soit soit soitxyxiixx=ixi2iykxykixiyikiai=1kabxyavec le ème bit effacé (ie ou ) - pour rendre la construction symétrique, choisissez si et , et choisissez si et . Utilisez comme représentation compacte de la paire. La paire d'origine peut être récupérée en calculant le bit de poids faible défini dans , en insérant un bit 0 à cette position en (donnant l'un de ou ) et en prenant le xor de ce nombre aveckb=i<kxi2i+i>kxi2i1b=i<kyi2i+i>kyi2i1xxk=0yk=1yxk=1yk=0(a,b)abxya (donnant l'autre élément de la paire).

Dans cette représentation, peut être n'importe quel nombre différent de zéro et peut être n'importe quel nombre avec la moitié de la plage. Il s'agit d'un test de cohérence: nous obtenons exactement le nombre attendu de représentations de paires non ordonnées.ab

En pseudocode, avec ^, &, |, <<, >>, ~étant C-like opérateurs binaires (XOR, et, ou, à décalage à gauche, décalage à droite, complément):

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- arrête d'être méchant'
la source
0

Une preuve non constructive: il y a non ordonné paires d'entiers 32 bits différents.(232×232232)/2=231(2321)<263

Martín-Blas Pérez Pinilla
la source