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

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

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

Введение

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

Типы данных:

8 бит

byte

int8

uint8

16 бит

short

int16

uint16

32 бита

integer

int32

uint32

64 бита

long

int64

uint64

128 бит

long long

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

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

Биты

signed

unsigned

8

-128 ... 0 … 127

0 … 255

16

-32768 … 0 … 32767

0 … 65535

32

-2147483648 … 2147483647

0 … 4294967295

64

-9223372036854775808 … 9223372036854775807

0 … 18446744073709551615

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

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

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

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

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

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

Run-length encoding

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

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

Студент

Урок 1

Урок 2

1

5

4

2

5

4

3

5

3

4

5

5

5

5

5

6

5

5

7

5

5

Массив

[5,5,5,5,5,5,5]

[4,4,3,5,5,5,5]

Размер массива

28 байт

28 байт

RLE

(5, 7)

[(4, 2), (3, 1), (5, 4)]

Размер после RLE

8 байт

24 байта

Delta encoding

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

Пример:

Массив до

Размер до

Массив после

Размер после

[10000000001, 10000000002, 10000000003, 10000000004, 10000000007, 10000000008, 10000000010, 10000000011]

int64[8], получаем 64 байта

10000000001, [1, 2, 3, 6, 7, 9, 10]

int64, int8[7], получаем 15 байт

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

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

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

Примеры:

Число

Биты int32

Удалили предшествующие нули

1

00000000000000000000000000000001

1

2

00000000000000000000000000000010

10

3

00000000000000000000000000000011

11

4

00000000000000000000000000000100

100

5

00000000000000000000000000000101

101

65536

00000000000000010000000000000000

10000000000000000

10

00000000000000000000000000001010

1010

28 bytes

28 bytes

4 bytes

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

Variable Byte (Varint, Group Varing Encoding, …)

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

Примеры:

Число

Битовое представление (int32)

VB encoded

Размер после

16385

00000000000000000100000000000001

10000001 10000000 00000001

3 байта

1

00000000000000000000000000000001

00000001

1 байт

1956

00000000000000000000011110100100

10100100 00001111

2 байта

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

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

PforDelta (NewPforDelta, OptPforDelta)

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

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

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

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

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

Пример:

Массив до

Массив дельт

Бинарный вид после алгоритма: 4 бита на дельту и одно 8 байтное исключение в конце.

[10000000001, 10000000002, 10000000003, 10000000004, 10000000007, 10000000008, 10000000010, 10000000011]

[10000000001, 1, 2, 3, 6, 7, 9, 10]

100000000001001000110110011110011010, 0000000000000000000000000000001001010100000010111110010000000001

Для краткости рассмотрим блок из 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), и т.д. Комбинации фиксированы для алгоритма.

Пример:

Массив

Слово после Simple9b

[5,5,5,5,5,5,5]

01000101010101010101010101010101

Массив состоит из 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-алгоритма является то, что она поддерживает операции пересечения и объединения, которые можно использовать в поиске.

Выводы

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

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

Ссылки