Nome do esquema de codificação binária para números inteiros

Question

Eu uma vez encontrado na Wikipedia uma boa técnica para codificar $ k \ in (2 ^ {N-1}, 2 ^ n) $ números inteiros uniformemente distribuídos comMenos, em seguida, $ \ log_2n $ bits / símbolo médio, graças a um simples para calcular o código de comprimento variável.Basicamente, usado $ \ log_2n $ para alguns símbolos e $ \ log_2n - 1 $ para alguns outros.

Infelizmente todo meu googling falhou comigo.Lembro-me de algo semelhante ao "binário de comprimento variável", mas continuo terminando no VLQ, que são uma besta diferente.Desde que eu conheço sua memória melhor que a minha, você pode me ajudar?

Answer 1

A ideia da técnica é perfeitamente descrita na resposta do filme yuval.Mesmo que ligeiramente diferente, é chamado codificação binária truncada na Wikipedia.Eu não consegui encontrar uma fonte original para isso, além de uma menção em um patente , neste livro , ou neste Google API

Answer 2

suponha $ k= 2 ^ {n-1} + t $ , onde $ 0 \ leq t <2 ^ {n-1} $ . Use o seguinte para codificar $ z \ in \ {0, \ lDOTS, K-1 \} $ :

• se $ z <2 ^ {n-1} -t $ codifique $ z $ como sua própria $ (n-1) $ -bit codificação.
• caso contrário, escrever $ z= 2 ^ {n-1} -t + 2 \ delta + \ epsilon $ , onde $ \ delta \ in \ \ \ {0, \ ldots, t-1 \} $ e $ \ epsilon \ in {0,1 \} $ . Codificar $ z $ na $ (n-1) $ codificação de $ 2 ^ {N-1} -t + \ Delta $ seguido por $ \ epsilon $ .

Aqui está um exemplo. Deixe $ k= 11= 2 ^ 3 + 3 $ . A codificação é a seguinte:

• $ 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 $ .