Есть ли название для этого алгоритма сжатия?

Question

Скажем, у вас есть четырехбайтовое целое число, и вы хотите сжать его до меньшего числа байтов.Вы можете сжать его, потому что меньшие значения более вероятны, чем большие значения (т. Е. Вероятность значения уменьшается с его величиной).Примените следующую схему, чтобы получить результат в 1, 2, 3 или 4 байта:

Обратите внимание, что в приведенном ниже описании (биты начинаются с единицы и идут от старшего к младшему)первый бит относится к старшему значащему биту, второй бит - к следующему старшему значащему биту и т. д.)в ноль

Если n> = 128 и n <16,384, вы используете двухбайтовое целое число.Вы устанавливаете первый бит на единицу, чтобы указать, а второй бит на ноль.Затем вы используете оставшиеся 14 бит для кодирования числа n.</li> Если n> 16,384 и n <2,097,152, вы используете трехбайтовое целое число.Вы устанавливаете первый бит на один, второй бит на один, а третий бит на ноль.Вы используете оставшиеся 21 бит для кодирования n. </li> Если n> 2 097 152 и n <268 435 456, вы используете четырехбайтовое целое число.Вы устанавливаете первые три бита в один и четвертый бит в ноль.Вы используете оставшиеся 28 бит для кодирования n.</li> Если n> = 268 435 456 и n <4 294 967 296, вы используете пятибайтовое целое число.Вы устанавливаете первые четыре бита на один и используете следующие 32-битные, чтобы установить точное значение n, как четырехбайтовое целое число.Остальная часть битов не используется. </li>

Есть ли название для этого алгоритма?

Answer 1

Это очень близко к величина переменной длины кодировка или base-128. Последнее название проистекает из того факта, что каждую 7-битную единицу в вашей кодировке можно считать цифрой от основания до 128.

Answer 2

это звучит очень похоже на целочисленное кодирование переменной длины Dlugosz

Answer 3

Код Хаффмана относится к использованию меньшего числа битов для хранения более общих данных в обмен на использование большего количества битов для хранения менее распространенных данных.

Answer 4

Ваша схема аналогична UTF-8, которая является схемой кодирования, используемой для текстовых данных Unicode.

Главное отличие состоит в том, что каждый байт в потоке UTF-8 указывает, является ли он опережающим или конечнымбайт, следовательно, последовательность может быть прочитана, начиная с середины.В вашей схеме отсутствующий ведущий байт сделает оставшуюся часть файла полностью нечитаемой, если ряд таких значений будет сохранен.И чтение такой последовательности должно начинаться с начала, а не с произвольного места.

Answer 5

Varint

Использование старшего бита каждого байта для обозначения «продолжить» или «останов», а оставшиеся биты (7 бит каждого байта в последовательности) интерпретируются как обычный двоичный код, который кодирует фактическое значение:

Это звучит как «Base 128 Varint», как используется в Буферы протокола Google .

связанные способы сжатия целых чисел

В итоге: этот код представляет собой целое число из 2 частей: Первая часть в унарном коде, которая указывает, сколько битов потребуется для чтения в оставшейся части значения, и вторая часть (указанной ширины в битах) в более или менее простом двоичном формате, который кодирует фактическое значение.

Этот конкретный код "связывает" унарный код с двоичным кодом, но другие, аналогичные коды сначала упаковывают полный унарный код, а затем двоичный код, такие как Elias гамма-кодирование .

Я подозреваю, что этот код относится к семейству "Старт / Стоп Коды" как описано в:

Стивен Голубь - Старт / Стоп Коды - Проц. Конференция по сжатию данных 2001, IEEE Computer Society Press, 2001.