Nombre del esquema de codificación binaria para números enteros

Question

Una vez encontrado en Wikipedia una técnica agradable para codificar $ k \ in (2 ^ {n-1}, 2 ^ n) $ Distribuyen uniformemente números enteros conMenos entonces $ \ log_2n $ bits / símbolos promedio, gracias a un código de longitud variable simple para calcular.Básicamente, usó $ \ log_2n $ para algunos símbolos y $ \ log_2n - 1 $ para otros.

Desafortunadamente, todo mi googling me ha fallado.Recuerdo algo similar a "Binario de longitud variable", pero sigo terminando en VLQ, que son una bestia diferente.Ya que conozco tu memoria mejor que la mía, ¿puedes ayudarme?

Answer 1

La idea de la técnica se describe perfectamente en la respuesta de Filmus Yuval.Incluso si es ligeramente diferente, se llama codificación binaria truncada en Wikipedia.No pude encontrar una fuente original para eso, aparte de una mención en una patente , en este libro , o en este google api

Answer 2

Supongamos $ k= 2 ^ {n-1} + t $ , donde $ 0 \ leq t <2 ^ {n-1} $ . Use lo siguiente para codificar $ z \ in \ {0, \ ldots, k-1 \} $ :

• si $ z <2 ^ {n-1} -t $ luego codificar $ z $ como su propio $ (n-1) $ codificación -bit.
• de lo contrario, escribe $ z= 2 ^ {n-1} -t + 2 \ delta + \ epsilon $ , donde $ \ delta \ in \ {0, \ ldots, t-1 \ span> y $ \ epsilon \ in \ {0,1 \} $ . Codificar $ z $ en el $ (n-1) $ codificación -bit de $ 2 ^ {N-1 ^ ^ {N-1} -t + \ Delta $ seguido de $ \ epsilon $ .

Aquí hay un ejemplo. Deje que $ k= 11= 2 ^ 3 + 3 $ . La codificación es la siguiente:

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