Количество переменной длины
Величина переменной длины ( VLQ ) — это универсальный код , который использует произвольное количество двоичных октетов (восьмибитных байтов ) для представления произвольно большого целого числа . По сути, VLQ представляет собой представление целого числа без знака по основанию 128 с добавлением восьмого бита для обозначения продолжения байтов. VLQ идентичен LEB128, за исключением порядка байтов . См. пример ниже.
Приложения и история
[ редактировать ]Сжатие Base-128 известно под многими названиями — VB (Variable Byte), VByte , Varint , VInt , EncInt и т. д. [1]
Величина переменной длины ( VLQ ) была определена для использования в стандартном MIDI-файла . формате [2] для экономии дополнительного места для системы с ограниченными ресурсами, а также используется в более позднем Extensible Music Format (XMF) .
Base-128 также используется в кодировке ASN.1 BER для кодирования номеров тегов и идентификаторов объектов . [3] Он также используется в среде WAP , где называется беззнаковым целым числом переменной длины или uintvar . Формат DWARF отладки [4] определяет вариант под названием LEB128 (или ULEB128 для беззнаковых чисел), где наименее значимая группа из 7 бит кодируется в первом байте, а наиболее значимые биты находятся в последнем байте (поэтому фактически это аналог с прямым порядком байтов ВЛК). Google Буферы протокола используют аналогичный формат для компактного представления целочисленных значений. [5] как и Oracle (POF). формат переносимых объектов [6] и Microsoft .NET Framework «7-битное целое число» в классах BinaryReader и BinaryWriter . [7]
Он также широко используется в веб-браузерах для сопоставления источников, которые содержат множество сопоставлений целочисленных строк и номеров столбцов, чтобы свести размер карты к минимуму. [8]
Целые числа переменной ширины в LLVM используют аналогичный принцип. Фрагменты кодирования имеют прямой порядок байтов и не обязательно должны иметь размер 8 бит. В документации LLVM описано поле, которое использует 4-битный фрагмент, причем каждый фрагмент состоит из 1-битного продолжения и 3-битной полезной нагрузки. [9]
Преимущества
[ редактировать ]- Компактность. Одним из основных преимуществ кодирования VLQ является его компактность. Поскольку для кодирования целого числа используется переменное количество байтов, меньшие целые числа могут быть представлены с использованием меньшего количества байтов, что приводит к меньшему общему размеру файла. Это особенно полезно в сценариях, где пространство для хранения ограничено, например, во встроенных системах или мобильных устройствах.
- Эффективность: кодирование VLQ — эффективный способ хранения и передачи данных. Поскольку меньшие целые числа представляются с использованием меньшего количества байтов, это уменьшает объем данных, которые необходимо передать, что, в свою очередь, уменьшает время и полосу пропускания, необходимые для передачи данных.
- Гибкость. Еще одним преимуществом кодирования VLQ является его гибкость. Поскольку количество байтов, используемых для представления целого числа, зависит от его величины, кодирование VLQ может обрабатывать целые числа разных размеров. Это означает, что кодировку VLQ можно использовать для представления целых чисел любого размера: от маленьких 8-битных целых чисел до больших 64-битных целых чисел.
Общая структура
[ редактировать ]Кодирование предполагает октет (8-битный байт), где старший бит (MSB), также известный как знаковый бит , зарезервирован для указания того, следует ли за ним другой октет VLQ.
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 |
| А | Б н | ||||||
Если A равно 0, то это последний октет VLQ целого числа. Если A равно 1, то следует еще один октет VLQ.
B — 7-битное число [0x00, 0x7F], а n — позиция октета VLQ, где B 0 — наименее значимый . Октеты VLQ располагаются наиболее значимыми первыми в потоке .
Варианты
[ редактировать ]Общая кодировка VLQ проста, но в базовой форме она определена только для целых чисел без знака (неотрицательных, положительных или нулевых) и является несколько избыточной, поскольку добавление октетов 0x80 в начало соответствует заполнению нулями. Существуют различные представления чисел со знаком для обработки отрицательных чисел и методы устранения избыточности.
Групповое кодирование Varint
[ редактировать ]Компания Google разработала групповое кодирование Varint (GVE) после того, как заметила, что традиционное кодирование VLQ требует большого количества ветвей ЦП во время распаковки. GVE использует один байт в качестве заголовка для четырех значений uint32 переменной длины. Байт заголовка содержит 4 2-битных числа, представляющих длину хранения каждого из следующих 4 uint32. Такая компоновка устраняет необходимость проверять и удалять биты продолжения VLQ. Байты данных можно копировать непосредственно в пункт назначения. Такая схема уменьшает количество ветвей ЦП , что делает GVE быстрее, чем VLQ на современных конвейерных ЦП. [10]
PrefixVarint — аналогичная конструкция, но с максимумом uint64. Говорят, что его «изобретали несколько раз независимо». [11] Можно изменить на цепную версию с бесконечным количеством продолжений.
Числа со знаком
[ редактировать ]Знаковый бит
[ редактировать ]Отрицательные числа можно обрабатывать с помощью знакового бита , который должен присутствовать только в первом октете.
В формате данных для пакетов Unreal, используемом Unreal Engine , используется количественная схема переменной длины, называемая компактными индексами. [12] используется. Единственное отличие в этом кодировании состоит в том, что в первом октете VLQ зарезервирован шестой бит, указывающий, является ли закодированное целое число положительным или отрицательным. Любой последовательный октет VLQ соответствует общей структуре.
| Первый октет VLQ | Другие октеты VLQ | ||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 | 2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 |
| А | Б | С 0 | А | Сп ( > п 0) | |||||||||||
Если A равно 0, то это последний октет VLQ целого числа. Если A равно 1, то следует еще один октет VLQ.
Если B равно 0, то VLQ представляет собой положительное целое число. Если B равен 1, то VLQ представляет собой отрицательное число.
C — кодируемый фрагмент номера, а n — позиция октета VLQ, где C 0 — наименее значимый . Октеты VLQ располагаются наименее значимыми первыми в потоке .
Зигзагообразное кодирование
[ редактировать ]Альтернативный способ кодирования отрицательных чисел — использовать младший бит в качестве знака. В частности, это сделано для буферов протокола Google и известно как зигзагообразное кодирование для целых чисел со знаком . [13] Числа можно закодировать так, чтобы закодированный 0 соответствовал 0, 1 - -1, 10 - 1, 11 - -2, 100 - 2 и т. д.: при подсчете чередуются неотрицательные (начиная с 0) и отрицательные (поскольку каждый шаг меняет младший бит (отсюда и знак), отсюда и название «зигзагообразное кодирование». Конкретно, преобразуйте целое число как (n << 1) ^ (n >> k - 1) для фиксированных k -битных целых чисел.
Дополнение до двух
[ редактировать ]LEB128 использует дополнение до двух для представления чисел со знаком. В этой схеме представления n бит кодируют диапазон от −2 н до 2 н − 1, и все отрицательные числа начинаются с 1 в старшем бите. В Signed LEB128 вход расширяется по знаку , так что его длина кратна 7 битам. Далее кодирование продолжается как обычно. [14]
В LEB128 поток располагается сначала по наименее значимому. [14]
Удаление избыточности
[ редактировать ]С помощью описанного выше кодирования VLQ любое число, которое может быть закодировано с помощью N октетов, также может быть закодировано с помощью более чем N октетов, просто путем добавления дополнительных октетов 0x80 в качестве дополнения нулями. Например, десятичное число 358 может быть закодировано как 2-октетный VLQ 0x8266, число 0358 может быть закодировано как 3-октетный VLQ 0x808266, или 00358 как 4-октетный VLQ 0x80808266 и так далее.
Однако формат VLQ, используемый в Git [15] удаляет эту предварительную избыточность и расширяет представимый диапазон более коротких VLQ, добавляя смещение к VLQ в 2 или более октетов таким образом, что наименьшее возможное значение для такого ( N + 1)-октетного VLQ становится ровно на один больше максимального возможное значение для N -октетного VLQ. В частности, поскольку 1-октетный VLQ может хранить максимальное значение 127, минимальному 2-октетному VLQ (0x8000) присваивается значение 128 вместо 0. И наоборот, максимальное значение такого 2-октетного VLQ (0xFF7F) составляет 16 511 вместо 16 383 . Аналогично, минимальный 3-октетный VLQ (0x808000) имеет значение 16 512 вместо нуля, что означает, что максимальный 3-октетный VLQ (0xFFFF7F) равен 2 113 663 вместо просто 2 097 151 .
Таким образом, существует одна и только одна кодировка каждого целого числа, что делает его биективной нумерацией по основанию 128 .
Примеры
[ редактировать ]
Вот разработанный пример для десятичного числа 137 :
- Представьте значение в двоичной записи (например, 137 как 10001001).
- Разбейте его на группы по 7 бит, начиная с младшего значащего бита (например, 137 как 0000001 0001001). Это эквивалентно представлению числа по основанию 128.
- Возьмите младшие 7 бит, и это даст вам младший байт ( 0 000 1001). Этот байт идет последним.
- Для всех остальных групп по 7 бит (в примере это 000 0001) установите MSb равным 1 (что в нашем примере дает 1 000 0001). Таким образом, 137 становится 1 000 0001 0 000 1001, где биты, выделенные жирным шрифтом, — это то, что мы добавили. Эти добавленные биты обозначают, следует ли следовать еще одному байту или нет. Таким образом, по определению, самый последний байт целого числа переменной длины будет иметь 0 в качестве MSb .
Другой способ взглянуть на это — представить значение в системе счисления с основанием 128, а затем установить старший бит всех цифр, кроме последней цифры с основанием 128, равным 1.
Спецификация формата стандартного MIDI-файла дает больше примеров: [2] [16]
| Целое число (десятичный) |
Целое число (двоичное) | Количество переменной длины (двоичное) | Целое число (шестнадцатеричный) |
Переменная длина количество (шестнадцатеричный) |
|---|---|---|---|---|
| 0 | 00000000 00000000 00000000 00000000 |
00000000 |
00000000 | 00 |
| 127 | 00000000 00000000 00000000 01111111 |
01111111 |
0000007F | 7F |
| 128 | 00000000 00000000 00000000 10000000 |
10000001 00000000 |
00000080 | 81 00 |
| 8192 | 00000000 00000000 00100000 00000000 |
11000000 00000000 |
00002000 | С0 00 |
| 16 383 | 00000000 00000000 00111111 11111111 |
11111111 01111111 |
00003FFF | ФФ 7F |
| 16 384 | 00000000 00000000 01000000 00000000 |
10000001 10000000 00000000 |
00004000 | 81 80 00 |
| 2 097 151 | 00000000 00011111 11111111 11111111 |
11111111 11111111 01111111 |
001FFFFF | ФФ ФФ 7F |
| 2 097 152 | 00000000 00100000 00000000 00000000 |
10000001 10000000 10000000 00000000 |
00200000 | 81 80 80 00 |
| 134 217 728 | 00001000 00000000 00000000 00000000 |
11000000 10000000 10000000 00000000 |
08000000 | С0 80 80 00 |
| 268 435 455 | 00001111 11111111 11111111 11111111 |
11111111 11111111 11111111 01111111 |
0FFFFFFFF | ФФ ФФ ФФ 7F |
Ссылки
[ редактировать ]- ^ Цзяньго Ван; Чунбин Лин; Яннис Папаконстантину; Стивен Суонсон. «Экспериментальное исследование сжатия растровых изображений по сравнению со сжатием инвертированного списка» . 2017. дои : 10.1145/3035918.3064007 .
- ^ Перейти обратно: а б Формат MIDI-файла: переменные величины .
- ^ «Рекомендация ITU-T X.690» (PDF) . Международный союз электросвязи. 2002.
- ^ Стандарт ГНОГОВ .
- ^ Буферы протокола Google .
- ^ Формат переносимых объектов Oracle (POF) .
- ^ Метод System.IO.BinaryWriter.Write7BitEncodedInt(int) и метод System.IO.BinaryReader.Read7BitEncodedInt() .
- ^ Введение в карты исходного кода JavaScript .
- ^ «Формат файла битового кода LLVM», раздел «Целые числа переменной ширины» . Доступ 01.10.2019.
- ^ Джефф Дин. «Проблемы создания крупномасштабных информационно-поисковых систем» (PDF) . п. 58 . Проверено 30 мая 2020 г.
- ^ Олесен, Якоб Стоклунд (31 мая 2020 г.). "стоклунд/варинт" . Архивировано из оригинала 19 ноября 2020 года . Проверено 9 июля 2020 г.
- ^ «Нереальные пакеты» . 21 июля 1999 г. Архивировано из оригинала 20 августа 2010 г. Проверено 29 августа 2021 г.
- ^ Буферы протокола: Кодирование: целые числа со знаком .
- ^ Перейти обратно: а б Группа свободных стандартов (декабрь 2005 г.). «Спецификация формата отладочной информации DWARF, версия 3.0» (PDF) . п. 70 . Проверено 19 июля 2009 г.
- ^ «Git – быстрая, масштабируемая, распределенная система контроля версий» . 28 октября 2021 г.
- ^ Стандартная спецификация формата MIDI-файла. 1.1 .
Внешние ссылки
[ редактировать ]- Ассоциация производителей MIDI (MMA) — источник англоязычных спецификаций MIDI.
- Ассоциация индустрии музыкальной электроники (AMEI) - источник спецификаций MIDI на японском языке.