Формат бинарного файла для сортированных целых – как записывают инкремент?

Рейтинг: 1Ответов: 2Опубликовано: 06.12.2014

Сортированные по возрастанию массивы целых (4 байта) храню в бинарном файле.

Копейка сэкономленная – копейка заработанная. Ведь можно не все 4 байта для каждого записывать, а существенно уменьшить объём данных, сохраняя только первое значение целиком, а для последующих хранить инкременты, которые впишутся в 1-2-3 байта.

Наверняка всё сделано до нас. Как называется такая компрессия, и как её реализовать?

Конкретнее: как обозначать, сколько байт занимает следующий инкремент / как разделять записи?

Upd. улучшенный вариант, не опускаемся до битов. Только байты. После начального пишем целый байт - это 4 пары битов, каждый означает число байт в блоке:

01010101 01010101 01010101 01010101 - S - начальное значение
10110101                            - b - сколько байт в следующих 4 блоках
                                      (10 11 01 01 = 2, 3, 1, 1)
01010101 01010101                   - inc - прибавляем к предыдущему
01010101 01010101 01010101          - inc
01010101                            - inc
01010101                            - inc
                                      Следующий блок из 4 инкрементов:
10110101                            - b - сколько байт в следующих 4 блоках
                                      (11 01 11 01 = 3, 1, 3, 1)
01010101 01010101 01010101          - inc
01010101                            - inc
01010101 01010101 01010101          - inc
01010101                            - inc

...

P.s. Надо ли думать о контроле ошибок?

файлы format компрессия
Источник: Stack Overflow на русском

Ответы

▲ 1Принят

@Sergiks, приходит в голову схема с битовым префиксом инкремента, определяющим размер инкремента в битах. А инкремент вместе с префиксом пусть будет занимать целое число байт. (Чем-то напоминает UTF).

Смотрите на старшие биты в первом байте инкремента до нулевого бита -- 0 - 7 бит для значения инкремента (инкремент вместе с префиксом занимает 1 байт), 10 - 14 бит (2 байта), 110 - 21 бит (3 байта), 1110 - 28 бит (4 байта) и 11110 - либо следующие 4 байта само число, либо 32-бит инкремент (ну, как проще код получится).

И никаких блоков не надо. Недостаток -- только последовательный доступ.

▲ 1

В голову приходят такие реализации-
первые 5 бит блока указывают сколько бит занимает инкремент (5 бит перекроют 4 байта в пределе), указанное количество бит хранит сам инкремент.
Таким образом любой инкремент будет сжат в 6-37 бит.
Готовые реализации не знаю.
Но с отдельными битами не очень работать.

Еще вариант с хранением целыми байтами:
"Служебный" блок по два бита хранит сколько целых байт занимает инкремент (00-1, 01-2, 10-3, 11-4).
Если последние 2 бита у байта равны 10, то это конец служебного блока.
Соответственно, если нужно обозначить трехбайтовый инкремент в такой позиции, то приходится его сохранить в 4 байта, вместо желаемых трех.