Название бинарной схемы кодирования для целочисленных чисел

Question

Я когда-то обнаружил, что в Wikipedia приятная техника кодирования $ k \ in (2 ^ {n-1}, 2 ^ n) $ равномерно распределенные целыми числами сМенее тогда $ \ log_2n $ Средние биты / символ, благодаря простому вычислительному коду переменной длины.В основном он использовал $ \ log_2n $ для некоторых символов и $ \ log_2n - 1 $ для некоторых других.

К сожалению, все мои густоты не подвели меня.Я вспоминаю что-то похожее на «Длина переменной длины», но я продолжаю заканчиваться на VLQ, которые являются разным зверям.Так как я знаю, что ваша память лучше, чем моя, вы можете мне помочь?

Answer 1

Техника идея идеально описана в youval Finkeus Ответ.Даже если немного по-другому, это называется Усеченная двоичная кодировка в Википедии.Я не смог найти оригинальный источник для этого, кроме упоминания в Патент , В этом Книга или в этом Google API

Answer 2

Предположим, $ k= 2 ^ {n-1} + t $ , где $ 0 \ leq t <2 ^ {N-1} $ . Используйте следующее для кодирования $ Z \ in \ {0, \ ldots, k-1 \} $ :

.
• Если $ z <2 ^ {n-1} -T $ затем кодирует $ z $ В качестве собственного $ (N-1) $ кодировка -bit.
• в противном случае, напишите $ Z= 2 ^ {N-1} -t + 2 \ Delta + \ epsilon $ , где $ \ delta \ in \ {0, \ ldots, t-1 \} $ и $ \ epsilon \ in \ {0,1 \} $ Кодировать $ Z $ на $ (N-1) $ -BIT CHARDING of $ 2 ^ {n - 1} -t + \ delta $ , а затем $ \ epsilon $ .

Вот пример. Пусть $ k= 11= 2 ^ 3 + 3 $ . Кодировка выглядит следующим образом:

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