Le moyen le plus efficace d’encoder 2 positions entre 0 et 64?

Question

Je souhaite compresser les valeurs 64 bits en exploitant le fait que seule une partie du milieu contient des données et qu'avant et après figurent des zéros.

Disons que les données réelles ont une longueur de 1 bit et sont complétées par n 0s à l'avant et m 0 à la fin de telle sorte que n + l + m = 64. Au lieu de transmettre / stocker 64 bits, je peux transmettre l bits plus besoin d'encoder la position des données dans l'intervalle de 64 bits.

Par exemple, disons que je stockais l, m et les bits de données, puis je restaurerais le modèle 64 bits original en lisant, en lisant l bits de données, en lisant m et en décalant les données m bits à gauche.

La plus petite surcharge que je puisse obtenir est deux fois 6 bits pour stocker deux des l, n et m (chacun pouvant être compris entre 0 et 64). Est-il possible de réduire ce nombre?

Answer 1

l peut être compris entre 0 et 64, donc n'envoyez pas l, envoyez n et m, car ils peuvent tous deux être zéro et ne doivent pas nécessairement aller jusqu'à 64 (ils doivent simplement pouvoir ajouter à 64).

Les l bits doivent commencer et se terminer par 1, ils n'ont donc pas besoin d'être transmis.

envoyer 6 bits pour n
envoie jusqu'à 6 bits pour m (voir ci-dessous)
calculer l = 64 - (n + m)
si l = 0, le nombre est 0, n'envoyez rien d'autre
si l = 1, le nombre est 1 * 2 ^ m, n'envoyez rien d'autre
si l = 2, le nombre est 3 * 2 ^ m, n'envoyez rien d'autre
envoie le milieu l - 2 bits.

Surcharge maximale = 10 bits.

La réduction des bits pour m est due au fait que
si n > 32 alors vous savez m & Lt; 32, donc seulement besoin de 5 bits
si n > 48 alors vous savez m & Lt; 16, alors seulement besoin de 4 bits
si n > 56 alors vous savez m & Lt; 8, alors seulement besoin de 3 bits
si n > 60 alors vous savez m & Lt; 4, donc seulement besoin de 2 bits
si n = 63 alors vous savez m < 2, donc seulement besoin de 1 bit

Answer 2

Votre analyse semble juste pour les célibataires. Mais si vous transmettez beaucoup de ces valeurs ensemble, un algorithme de codage d'entropie générique tel que gzip sera probablement plus performant, car il peut très bien éliminer les chaînes de zéros et exploiter les redondances dans les données.

Answer 3

Comme vous avez énoncé le problème, non, vous ne pouvez pas faire mieux que la solution que vous avez proposée.

Toutefois, si la distribution des zéros dans les nombres est asymétrique, vous pourrez peut-être obtenir une meilleure compression en moyenne en utilisant des codes de Huffman ou une technique similaire pour représenter les comptes. Une autre possibilité consiste à utiliser le codage delta si la distribution zéro est fortement corrélée d'une valeur 64 bits à la suivante.

Dans les deux cas, vous devrez utiliser un nombre variable de bits pour représenter le nombre de zéros. Et si vos hypothèses sur l’asymétrie ou la corrélation se révèlent fausses, vous risquez de vous retrouver avec plus de bits en moyenne que si vous l’aviez fait de manière simple.

Answer 4

Votre solution semble plutôt bonne.
Le le codage de Huffman est un autre moyen de compresser vos valeurs, en particulier s'il existe des valeurs très fréquentes.

Ce n’est pas très difficile à mettre en œuvre, mais cela peut être difficile si vous n’avez pas beaucoup de données à transmettre.

Answer 5

Il y a 64 des positions de départ possibles n de la séquence de unités et la longueur de la séquence l ne peut plus être alors 64 - n. Donc, il y a

r = sum(n = 0..63, 64 - n) + 1

séquences au total. Celui ajouté est pour une séquence de tous les zéros. Faire des calculs donne les résultats suivants.

r = 64 * 64 - (63 * 64) / 2 + 1
  = 2081

Représenter 2081 valeurs possibles nécessite log2(2081) = 11.023 bits. Votre suggestion de coder les informations en utilisant deux 6 nombres de bits nécessitant 12 bits au total est donc optimale (sous l'hypothèse de distributions égales de toutes les valeurs possibles).