Уточнение кодировки переменных байтов

Question

Я очень новичок в мире байтового кодирования, поэтому, пожалуйста, извините меня (и обязательно исправьте меня), если я использую / выражаю простые понятия неправильно.

Я пытаюсь понять переменную байтовую кодировку. Я прочитал статью из Википедии (http://en.wikipedia.org/wiki/Variable-width_encoding), а также главу книги из учебника по поиску информации. Мне кажется, я понимаю, как кодировать десятичное целое число. Например, если я хотел бы предоставить Переменное байтовое кодирование для целого числа 60, я бы получил следующий результат:

1 0 1 1 1 1 0 0

(пожалуйста, дайте мне знать, если вышеприведенное неверно). Если я понимаю схему, то я не совсем уверен, как информация сжимается. Это потому, что обычно мы используем 32 бита для представления целого числа, чтобы представление 60 приводило к 1 1 1 1 0 0 с предшествующими 26 нулями, тратя впустую это пространство вместо представления его всего с 8 битами вместо этого?

Заранее благодарим за разъяснения.

Answer 1

То, как вы делаете это, резервируя один из битов, означающих «Я не закончил со значением». Обычно это самый важный бит.

Когда вы читаете байт, вы обрабатываете младшие 7 бит. Если старший бит равен 1, то вы знаете, что нужно прочитать еще один байт, и повторяете процесс, добавляя следующие 7 бит к текущим 7 битам.

В формате MIDI эта точная кодировка используется для представления длины событий MIDI следующим образом:

1. Ожидаемое значение = 0
2. байт = ReadFromFile
3. ExpectedValue = ExpectedValue + (byte AND 0x7f)
4. если байт> 127, то
   1. Ожидаемое значение = Ожидаемое значение SHL 7
   2. Перейти к 2
5. Готово

Например, значение 0x80 будет представлено с помощью байтов 0x81 0x00. Вы можете попробовать запустить алгоритм на этих двух байтах, и вы увидите, что получите правильное значение.

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

Answer 2

Вы ударили ноготь по голове.

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

Схемы кодирования на битовом уровне гораздо сложнее реализовать, чем схемы на байтовом уровне, и дополнительная нагрузка на ЦП может перевесить сэкономленное время из-за меньшего количества данных для чтения, хотя большинство современных ЦП имеют "старший бит" и "самый низкий бит" битовые инструкции, которые значительно улучшают производительность кодеков битового уровня. Поскольку скорости ЦП продолжают опережать скорости ОЗУ, схемы на битовом уровне станут более привлекательными, хотя простота кодеков на уровне байтов также является важным фактором.

Answer 3

Да, вы правы, вы экономите место путем кодирования, используя один байт вместо 4. Как правило, вы экономите память, если значения, которые вы кодируете, намного меньше максимального значения, которое поместилось бы в исходной кодировке с фиксированной шириной.