Quelle est la manière la plus efficace de stocker une plage numérique?

Cette question concerne le nombre de bits requis pour stocker une plage. Ou, autrement dit, pour un nombre donné de bits, quelle est la plage maximale pouvant être stockée et comment?

Imaginez que nous voulons stocker une sous-plage dans la plage 0-255.

Ainsi, par exemple, 45-74.

Nous pouvons stocker l'exemple ci-dessus sous la forme de deux octets non signés, mais il me semble qu'il doit y avoir une certaine redondance d'informations. Nous savons que la deuxième valeur est plus grande que la première, donc dans le cas où la première valeur est grande, moins de bits sont nécessaires pour la deuxième valeur, et dans le cas où la deuxième valeur est grande, moins de bits sont requis pour la première .

Je soupçonne que toute technique de compression donnerait un résultat marginal, il serait donc préférable de demander "quelle est la plage maximale pouvant être stockée dans un octet?". Cela devrait être plus grand que ce qui est réalisable en stockant les deux nombres séparément.

Existe-t-il des algorithmes standard pour faire ce genre de choses?

Il suffit de compter le nombre de plages possibles. Il y a 256 plages avec borne inférieure 0 (0-0, 0-1, ... 0-254, 0-255), 255 plages avec borne inférieure 1, ... et enfin 1 plage avec borne inférieure 255 (255- 255). Le nombre total est donc (256 + 255 + ... + 1) = 257 * 128 = 32 896. Comme cela est légèrement supérieur à 2 ¹⁵ = 32 768, vous aurez toujours besoin d'au moins 16 bits (2 octets) pour stocker ces informations.

En général, pour les nombres de 0 à n-1, le nombre de plages possibles est n * (n + 1) / 2. C'est moins de 256 si n est 22 ou moins: n = 22 donne 22 * ​​23/2 = 253 possibilités. Ainsi , un octet suffit pour les sous-gammes de 0-21 .

Une autre façon d'examiner le problème est la suivante: le stockage d'une paire d'entiers compris entre 0 et n-1 équivaut presque au stockage d'une sous-plage de 0- (n-1) plus un seul bit qui détermine si le premier nombre est inférieur ou supérieur au second. (La différence vient du cas où les deux entiers sont égaux, mais cette chance devient de plus en plus petite à mesure que n grandit.) C'est pourquoi vous ne pouvez enregistrer qu'un seul bit avec cette technique, et probablement la principale raison pour laquelle elle est rarement utilisée.

Pour un si petit nombre de bits, il est impossible d'enregistrer de nombreux bits comme l' a souligné Glorfindel . Cependant, si le domaine que vous utilisez a quelques bits de plus, vous pouvez réaliser des économies importantes pour le cas moyen en encodant des plages avec la valeur de départ et un delta.

Supposons que le domaine soit les entiers, donc 32 bits. Avec l'approche naïve, vous avez besoin de 64 bits (début, fin) pour stocker une plage.

Si nous passons à un codage de (début, delta), nous pouvons construire la fin de la plage à partir de cela. Nous savons que dans le pire des cas, le début est 0 et le delta a 32 bits.

2 ^ 5 est 32, donc nous codons la longueur du delta en cinq bits (pas de longueur nulle, ajoutez toujours 1), et l'encodage devient (début, longueur, delta). Dans le pire des cas, cela coûte 32 * 2 + 5 bits, donc 69 bits. Donc dans le pire des cas, si toutes les plages sont longues, c'est pire que l'encodage naïf.

Dans le meilleur des cas, cela coûte 32 + 5 + 1 = 38 bits.

Cela signifie que si vous devez encoder un grand nombre de plages, et que ces plages ne couvrent chacune qu'une petite partie de votre domaine, vous finissez par utiliser moins d'espace en moyenne en utilisant cet encodage. Peu importe la façon dont les départs sont distribués, car le début prendra toujours 32 bits, mais la façon dont les longueurs des plages sont distribuées importe. Si plus vous avez de petites longueurs, meilleure est la compression, plus vous avez de plages couvrant toute la longueur du domaine, pire sera l'encodage.

Cependant, si vous disposez de nombreuses plages regroupées autour de points de départ similaires (par exemple, parce que vous obtenez des valeurs d'un capteur), vous pouvez réaliser des économies encore plus importantes. Vous pouvez appliquer la même technique à la valeur de départ et utiliser un biais pour compenser la valeur de départ.

Disons que vous avez 10000 plages. Les plages sont regroupées autour d'une certaine valeur. Vous encodez le biais avec 32 bits.

En utilisant l'approche naïve, vous auriez besoin de 32 * 2 * 10 000 = 640 000 bits pour stocker toutes ces plages.

L'encodage de la polarisation prend 32 bits, et l'encodage de chaque plage prend alors dans le meilleur des cas 5 + 1 + 5 + 1 = 12 bits, pour un total de 120 000 + 32 = 120 032 bits. Dans le pire des cas, vous avez besoin de 5 + 32 + 5 + 32 bits, donc 74 bits, pour un total de 740 032 bits.

Cela signifie que, pour 10 000 valeurs sur un domaine qui prend 32 bits à coder, nous obtenons

• 120 032 bits avec le codage delta intelligent dans le meilleur des cas
• 640 000 bits avec le début naïf, le codage final, toujours (pas le meilleur ou le pire des cas)
• 740 032 bits avec le codage delta intelligent dans le pire des cas

Si vous prenez l'encodage naïf comme référence, cela signifie soit des économies allant jusqu'à 81,25%, soit jusqu'à 15,625% de coûts supplémentaires.

Selon la façon dont vos valeurs sont réparties, ces économies sont importantes. Connaissez votre domaine d'activité! Sachez ce que vous voulez encoder.

En tant qu'extension, vous pouvez également modifier le biais. Si vous analysez les données et identifiez des groupes de valeurs, vous pouvez trier les données dans des compartiments et encoder chacun de ces compartiments séparément, avec son propre biais. Cela signifie que vous pouvez appliquer cette technique non seulement aux plages regroupées autour d'une seule valeur de départ, mais également aux plages regroupées autour de plusieurs valeurs.

Si vos points de départ sont répartis également, cet encodage ne fonctionne pas vraiment bien.

Cet encodage est évidemment extrêmement mauvais à indexer. Vous ne pouvez pas simplement lire la valeur x-ème. Il ne peut quasiment être lu que séquentiellement. Ce qui est approprié dans certaines situations, par exemple le streaming sur le réseau ou le stockage en vrac (par exemple sur bande ou disque dur).

Évaluer les données, les regrouper et choisir le biais correct peut être un travail considérable et peut nécessiter un réglage fin pour des résultats optimaux.

Ce type de problème fait l'objet de l'article fondateur de Claude Shannon, Une théorie mathématique de la communication , qui a introduit le mot «bit» et a plus ou moins inventé la compression de données.

L'idée générale est que le nombre de bits utilisés pour coder une plage est inversement proportionnel à la probabilité que cette plage se produise. Par exemple, supposons que la plage 45-74 apparaisse environ 1/4 du temps. Vous pouvez dire que la séquence 00 correspond à 45-74. Pour encoder la plage 45-74, vous sortez "00" et vous vous arrêtez là.

Supposons également que les plages 99-100 et 140-155 apparaissent chacune environ 1/8 du temps. Vous pouvez encoder chacun d'eux avec une séquence de 3 bits. Tous les 3 bits feront l'affaire tant qu'ils ne commencent pas par «00», qui a déjà été réservé pour la plage 45-74.

00: 45-74
010: 99-100
101: 140-155

Vous pouvez continuer de cette manière jusqu'à ce que chaque plage possible ait un encodage. La plage la moins probable peut nécessiter plus de 100 bits. Mais ce n'est pas grave car cela apparaît rarement.

Il existe des algorithmes pour trouver le codage optimal. Je n'essaierai pas de les expliquer ici, mais vous pouvez en trouver plus en visitant le lien ci-dessus ou en recherchant «Théorie de l'information», «Codage Shannon-fano» ou «Codage Huffman».

Comme d'autres l'ont souligné, il est probablement préférable de stocker le numéro de début et la différence entre le numéro de début et le numéro de fin. Vous devriez utiliser un codage pour le début et un autre pour la différence, car ils ont des distributions de probabilité différentes (et je suppose que ce dernier est plus redondant). Comme l'a suggéré polygnome, le meilleur algorithme dépend de votre domaine.

Pour développer la réponse de @Glorfindel:

Comme n → ∞, (n - 1) → n. Ainsi, Ω (plages) → n² / 2 et log (Ω (plages)) → (2n - 1). Comme le codage naïf prend 2n bits, la compression maximale asymptotique n'enregistre que 1 bit.

Il existe une réponse similaire, mais pour obtenir une compression optimale, vous avez besoin de:

1. Une méthode d'encodage entropique optimale (lire sur le codage arithmétique et les ANS essentiellement équivalents (même taux de compression, un peu plus rapide mais aussi plus difficile à saisir) )
2. Autant d'informations que possible sur la distribution des données. Surtout, cela n'implique pas seulement de «deviner» la fréquence d'apparition d'un numéro, mais vous pouvez souvent exclure certaines possibilités à coup sûr. Par exemple, vous pouvez exclure les intervalles de taille négative et éventuellement de taille 0, selon la façon dont vous définissez un intervalle valide. Si vous avez plusieurs intervalles à coder à la fois, vous pouvez les trier, par exemple, par ordre décroissant de largeur ou en augmentant la valeur de début / fin, et exclure un grand nombre de valeurs (par exemple, si vous garantissez un ordre en diminuant la largeur, l'intervalle précédent avait une largeur de 100, et la valeur de départ pour le suivant est 47, il suffit de considérer les possibilités jusqu'à 147 pour les valeurs finales).

Plus important encore, le numéro 2 signifie que vous voulez coder les choses de telle manière que les valeurs les plus informatives (par bit codé) viennent en premier. Par exemple, alors que j'ai suggéré de coder une liste triée "telle quelle", il serait généralement plus intelligent de la coder comme un "arbre binaire" - c'est-à-dire si elles sont triées par largeur et que vous avez des lenéléments, commencez par coder l'élément len/2. Disons qu'il avait une largeur w. Maintenant, vous connaissez tous les éléments avant qu'il ait une largeur quelque part dans [0, w], et tous les éléments après lui ont une largeur quelque part dans [w, val max que vous acceptez]. Répéter de manière récursive (subdiviser à nouveau chaque demi-liste en deux, etc.) jusqu'à ce que vous ayez couvert les lenéléments (à moins qu'il ne soit fixe, vous voudrez encoderlenvous n'avez donc pas besoin de vous soucier de terminer les jetons). Si "max val you accept" est vraiment ouvert, il peut être judicieux de coder d'abord la valeur la plus élevée qui apparaît réellement dans vos données, c'est-à-dire le dernier élément, puis de faire le partitionnement binaire. Encore une fois, tout ce qui est le plus informatif par bit en premier.

De plus, si vous encodez d'abord la largeur de l'intervalle et que vous connaissez la valeur maximale possible à laquelle vous avez affaire, vous pouvez évidemment exclure toutes les valeurs de départ qui le feraient déborder ... vous avez l'idée. Transformez et ordonnez vos données de manière à pouvoir déduire autant que possible le reste des données au fur et à mesure que vous les décodez, et un algorithme de codage entropique optimal vous assurera de ne pas gaspiller des informations de codage de bits que vous "connaissez déjà". .