Компактные системы числового кодирования ⇐ Васина Википедия

[wiki_en]

«Компактное числовое кодирование» относится к классу методов сериализации данных, предназначенных для представления числовых значений с использованием минимального объема памяти или возможной полосы пропускания передачи. В отличие от кодировок фиксированной ширины (таких как стандартные 32-битные или 64-битные целые числа), компактные кодировки адаптируют размер хранилища в зависимости от величины или статистического распределения данных.

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

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

=== Количество переменной длины (VLQ) ===
Количество переменной длины | Системы VLQ используют переменное количество байтов для представления целого числа. Наиболее распространенная реализация использует «Старший значащий бит (MSB)» каждого байта в качестве «бита продолжения», чтобы указать, является ли следующий байт частью того же числа.

* '''LEB128 (Little-Endian Base 128):''' Широко используется в формате отладки DWARF и WebAssembly.
* '''Варинц'''. Краеугольный камень формата протокольных буферов (Protobuf), разработанного Google.

=== Универсальные коды битового уровня ===
Универсальный код (сжатие данных) | Универсальные коды не совпадают с границами байтов; вместо этого они представляют целые числа в виде битовых последовательностей, префикс которых позволяет декодеру определить длину.

* '''Кодирование Элиаса:''' Включает кодирование Гамма, Дельта и Омега. Гамма-кодирование особенно эффективно для небольших целых чисел.
* '''Кодирование Голомба:''' Оптимизировано для данных, имеющих геометрическое распределение, часто используется при сжатии изображений и аудио без потерь (например, FLAC).

=== Упаковка и система координат (FOR) ===
Эти системы используются для одновременного кодирования блоков чисел, что часто встречается в столбчатых базах данных и базах данных временных рядов (TSDB).

* '''Simple8b / Simple16:''' Эти алгоритмы упаковывают несколько целых чисел в одно 64-битное слово на основе максимального значения в наборе.
* '''PFOR (исправленная система отсчета):''' Этот метод сохраняет «базовое» значение для блока и кодирует только смещения. Выбросы (исключения) сохраняются отдельно для обеспечения высокой степени сжатия.

== Обработка целых чисел со знаком ==
Представление отрицательных чисел в компактных форматах представляет собой проблему, поскольку традиционное дополнение до двух приводит к образованию большого количества ведущих чисел. Чтобы решить эту проблему, используется «кодирование ZigZag». Он сопоставляет целые числа со знаком с целыми числами без знака, чередуя положительные и отрицательные числа:
Это гарантирует, что значения с небольшими абсолютными величинами приведут к небольшим закодированным варинтам.

== Десятичная и финансовая кодировки ==
Для приложений, требующих высокой точности без ошибок двоичного округления, используются специализированные десятичные кодировки.

* '''Двоично-десятичное число (BCD):''' Представляет каждую десятичную цифру четырьмя битами.
* '''Плотно упакованные десятичные числа (DPD):''' Метод, используемый в версии IEEE 754-2008|стандарте IEEE 754-2008, который сжимает три десятичные цифры в 10 бит.

== Приложения ==
* '''Среды сериализации:''' Apache Thrift, Apache Avro и протокольные буферы используют компактные кодировки для уменьшения размера полезной нагрузки в микросервисах.
* '''Блокчейн:''' Биткойн и Эфириум используют различные формы Varints для минимизации размера транзакций, хранящихся в реестре.
* '''Поисковые системы:''' Инвертированные индексы используют дельта-кодирование для сжатия списков идентификаторов документов.

== См. также ==
* Сжатие данных
* Энтропийное кодирование
* Саморазграничивающий код

== Дальнейшее чтение ==
* Лемир Д. и Бойцов Л. (2015). «Декодирование миллиардов целых чисел в секунду посредством векторизации». «Программное обеспечение: практика и опыт».
* Шолер Ф., Уильямс Х.Э., Яннис Дж. и Зобель Дж. (2002). «Сжатие инвертированных индексов».

Сжатие данных
Компьютерная арифметика
Кодировка символов

Подробнее: https://en.wikipedia.org/wiki/Compact_N ... ng_Systems