Разъяснение кодирования переменного байта
Я очень плохо знаком с миром байта, кодирующего, поэтому извините меня (и любой ценой, исправьте меня), если я использую/выражаю простые понятия неправильным способом.
Я пытаюсь понять кодирование переменного байта. Я прочитал статью Wikipedia (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 битами вместо этого?
Заранее спасибо за разъяснения.
3 ответа
Способ сделать это - зарезервировать один из битов, означающий "я не закончил со значением". Обычно это старший бит.
Когда вы читаете байт, вы обрабатываете младшие 7 битов. Если старший бит равен 1, то вы знаете, что есть еще один байт для чтения, и повторяете процесс, добавляя следующие 7 битов к текущим 7 битам.
Формат MIDI использует именно такое кодирование для представления длительности событий MIDI следующим образом:
- ExpectedValue = 0
- byte=ReadFromFile
- ExpectedValue = ExpectedValue + (byte AND 0x7f)
- if byte > 127 then
- ExpectedValue = ExpectedValue SHL 7
- Goto 2
- Done
Например, значение 0x80 будет представлено байтами 0x81 0x00. Вы можете попробовать запустить алгоритм на этих двух байтах, и вы увидите, что получите правильное значение.
UTF-8 работает аналогично, но использует немного более сложную схему, чтобы сказать вам, сколько байт вы должны ожидать. Это позволяет исправить некоторые ошибки, поскольку вы можете легко определить, соответствуют ли получаемые байты заявленной длине. Википедия описывает их структуру достаточно хорошо.
Вы попали в самую точку.
Существует множество схем кодирования, таких как гамма и дельта, которые являются частными случаями кодирования Элиаса. Это коды битового уровня, в отличие от кода байтового уровня, который вы использовали, и они полезны, когда у вас есть сильный перекос в сторону малых чисел (что часто может быть достигнуто путем кодирования дельт вместо абсолютных значений).
Схемы кодирования на битовом уровне намного сложнее реализовать, чем схемы на уровне байтов, и дополнительная нагрузка на ЦП может перевесить время, сэкономленное за счет меньшего количества данных для чтения, хотя большинство современных ЦП имеют «самый высокий бит» и «самый низкий бит». bit "инструкции, которые значительно улучшают производительность кодеков битового уровня.Поскольку скорость ЦП продолжает опережать скорость ОЗУ, битовые схемы станут более привлекательными, хотя простота байтовых кодеков также является важным фактором.
Да, вы правы, вы экономите место, кодируя один байт вместо четырех. Как правило, вы экономите память, если значения кодируемые вами значения намного меньше максимального значения, которое могло бы поместиться в исходной кодировке с фиксированной шириной.