Сжатие целых чисел

Цель статьи осветить state of the art методы сжатия целых чисел, чтобы сэкономить в будущем время исследования алгоритмов и терминологии. При этом описание части алгоритмов может быть упрощено для понимания. Сравнение алгоритмов тоже находится вне рамках этой статьи. Подробнее можно почитать в ссылках.

Многие из упомянутых ниже алгоритмов используются в прикладных задачах: сжатие битмап, обратных индексов, просто массивов данных.

Введение

Различные языки программирования предлагают типы целых чисел.

Типы данных:

Количество бит и поддержка отрицательных чисел определяют диапазон поддерживаемых значений.

Диапазоны значений:

Современные компьютеры имеют 64х разрядные шины данных, соответственно за один цикл можно передавать 64 бита.

Самым практичным типом является int32, потому что в него помещаются большинство значений, которыми оперируют программы. При этом часто 32 бита гораздо больше, чем необходимо для хранения информации.

Рассмотрим пример массива:

[1, 2, 3, 4, 5, 65536, 10]

Видно, что большинство чисел занимают тип int8, но из-за шестого элемента - 65536, тип массива должен быть int32.

Какие алгоритмы сжимают данные?

Run-length encoding

Если в массиве часто встречаются повторяющиеся значения, можно запомнить их количество. В магазинных чеках пишут одну строку - 10 яблок, а не десять строк “яблоко”.

Пример с оценками студентов по предметам:

Delta encoding

Бывает такое, что числа большие, но близкие, такие как 1000001 и 1000002. Разница между ними равна 1. Значит, можно сохранить первое число в массиве без изменений, а потом записать разницу от предыдущего числа. Для первого элемента используется тип, который необходим. Для остальных элементов берется тип поменьше (int8,…).

Пример:

Так же можно использовать Delta of delta encoding. Такой подход используется для кодирования времени: временные метки в системах мониторинга часто отличаются на какое-то фиксированное число с небольшими отклонениями, потому что период сбора данных примерно одинаковый.

Идея битового сжатия

Когда 32 бита много, использовать меньше.

Примеры:

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

Variable Byte (Varint, Group Varing Encoding, …)

История берет свое начало с 1990 года и Variable byte (varint) алгоритма. Базовый алгоритм использует 7 бит для значимой информации. Восьмой (старший) бит используется, как индикатор, является ли следующий байт продолжением предыдущего.

Примеры:

Подробнее рассмотрим первый пример. Последние 7 бит: 0000001 (младшие биты справа) становятся первыми битами в закодированном значении. Затем следующие 7 бит: 0000000, - вторым байтом. Оба байта в закодированном виде начинаются с единичного старшего бита, поэтому следующий байт продолжение предыдущего. Наконец старший значащий бит исходного числа находится на пятнадцатой позиции. Он запишется в младший бит третьего байта закодированного значения. У этого байта старший бит будет 0, значит, число закончилось.

Этот алгоритм широко известен. В частности, используется в формате Protobuf, который применяется в gRPC.

PforDelta (NewPforDelta, OptPforDelta)

Алгоритм состоит из нескольких шагов:

1. Посчитать все дельты.

2. Для каждого блока из 128 дельт найти такое количество бит B, которым можно закодировать до 90% всех чисел.

3. Перекодировать все числа, используя B.

4. Числа, которые нельзя закодировать B битами, записываются, как исключения в конце.

Пример:

Для краткости рассмотрим блок из 8 дельт. После преобразования достаточно 4х бит (десять - самое большое, это 1010) для хранения всех чисел, кроме первого. Первые 4 бита использовано, чтобы закодировать одно исключение на позиции 0. Дальше 4 бита пустые - как раз те, что на позиции ноль. Следующие четыре бита: 0001 - это единица из второй позиции исходного массива, затем двойка 0010 и т.д. Это иллюстрация, а не точная имплементация. Итого получим 13 байт вместо 64 байт.

Расширения алгоритма оптимизируют хранение исключений и поиск B.

Simple9b (Simple16b, Simple8b)

Этот алгоритм записывает как можно большее количество чисел в 32-битном слове. 4 бита используются для хранения состояния, 28 бит для данных.

Состояние - выбранный способ хранения данных в 28 битах, который зависит от того, сколько бит требуется для каждого числа.

Заранее составляются 9 комбинаций состояний: 281 бит (0001), 142 бита (0010), 93 бита (0011), 74 бита (0100), 5*5 бит (0101), и т.д. Комбинации фиксированы для алгоритма.

Пример:

Массив состоит из 7 значений по 3 бита, т.к. 5 - это 101. Используя допустимые комбинации, сохраняем 7 значений по 4 бита с маской 0100 в начале. Итого 4 байта против 28 байт.

В 4 битах можно закодировать 16 комбинаций, этим пользуется Simple16b. Simple8b использует 64х разрядное слово.

Roaring

Комбинированный алгоритм сжатия разделяет пространство положительных целых чисел на диапазоны [0, 65535], [65536, 65536 × 2 − 1], [65536 × 2, 65536 × 3 − 1] и т.д. По построению целые числа в каждом диапазоне имеют одинаковые два старших байта. В зависимости от того сколько чисел N попадает в диапазон выбирается один из двух вариантов хранения:

1. N > 4096, используется 65536 разрядная битмапа.

2. Иначе, сортированный массив int16.

Особенностью реализации roaring-алгоритма является то, что она поддерживает операции пересечения и объединения, которые можно использовать в поиске.

Выводы

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

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

Ссылки

• https://www.timescale.com/blog/time-series-compression-algorithms-explained/

• https://www.cs.purdue.edu/homes/csjgwang/pubs/SIGMOD17-Bitmap.pdf

• https://arxiv.org/pdf/1401.6399.pdf

• https://www.roaringbitmap.org/publications/

• https://github.com/powturbo/TurboPFor-Integer-Compression

• https://github.com/lemire/JavaFastPFOR