Nom du schéma d'encodage binaire pour les nombres entier

Question

J'ai une fois trouvé sur Wikipedia une belle technique pour codage de $ k \ in (2 ^ {n-1}, 2 ^ n) $ nombre de nombres entiers distribués uniformément distribué avecMoins de $ \ log_2n $ bits / symboles moyens, grâce à un code de longueur variable simple à calculer.Fondamentalement, il a utilisé $ \ log_2n $ pour certains symboles et $ \ log_2n - 1 $ pour d'autres.

Malheureusement, tout mon googling m'a échoué.Je me souviens de quelque chose de similaire à la "longueur variable binaire", mais je continue à finir sur VLQ qui sont une bête différente.Puisque je connais mieux votre mémoire que le mien, pouvez-vous m'aider?

Answer 1

L'idée technique est parfaitement décrite dans la réponse Yuval Filmus.Même s'il est légèrement différent, il s'appelle coding binaire tronqué à Wikipedia.Je ne pouvais pas trouver une source originale pour cela, mis à part une mention dans un brevet , dans ce Book ou dans ce Google API

Answer 2

Supposons $ k= 2 ^ {n-1} + t $ , où $ 0 \ leq t <2 ^ {n-1} $ . Utilisez ce qui suit pour coder $ z \ \ \ \ \ {0, \ ldots, k-1 \} $ :

• si $ z <2 ^ {n-1}-t $ est ensuite coder $ z $ comme sa propre $ (n-1) $ encodage -bit.
• Dans le cas contraire, écriture $ z= 2 ^ {n-1} -t + 2 \ delta + \ epsilon $ , où $ \ delta \ in \ {0, \ ldots, t-1 \} $ et $ \ epsilon \ in \ {0,1 \} $ . Encode $ Z $ à la $ (N-1) $ codage--bit de $ 2 ^ {n-1} -t + \ delta $ suivi de $ \ epsilon $ .

Voici un exemple. Laissez $ k= 11= 2 ^ 3 + 3 $ . Le codage est le suivant:

• 0 \ \ à 000 $ .
• 1 $ \ à 001 $ .
• $ 2 \ à 010 $ .
• $ 3 \ à 011 $ .
• 4 $ \ 100 $ .
• 5 $ \ à 1010 $ .
• 6 $ à 1011 $ .
• 7 \ à 1100 $ .
• 8 \ à 1101 $ .
• 9 $ \ à 1110 $ .
• 10 $ \ à 1111 $ .