Как оптимально хранить в бинарном файле сортированные целые числа?

Question

[Сергей Соколов]

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

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

Вопросы:

1. наверняка есть известный формат/алгоритм сжатия подходящий для описанной ситуации – какой?
   
2. надо ли, и как - заморачиваться на контроль целостности данных?

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

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

                                      Следующий блок из 4 инкрементов:
11011101                            - b - (11 01 11 01 = 3, 1, 3, 1)
01010101 01010101 01010101          - inc
01010101                            - inc
01010101 01010101 01010101          - inc
01010101                            - inc
...

В конце файла блок нулевые длины инкрементов, если те лишние.

Answer 1

[maaGames]

Сперва хотел рассказать про хранение WAV файлов в формате PCM, но передумал. Вы собираетесь экономить на печеньках - не правильный подход.
Предлагаю оптимальный вариант + его модификацию.
1. Раз данные пишутся и читаются последовательно, то вам Бог велел использовать потоковое сжатие (это если файл в оперативную память весь не влезает, иначе тупо зиповать можно было бы). Не зная языка программирования не могу подсказать библиотеку. На C++ можно декорировать файловый поток архиватором, чтобы на лету данные паковать. Самому архиватор писать не стоит, лучше поищи готовую реализацию.
2. Так как числа упорядочены, то вы правильно предложили хранить разницу между соседними числами, это обеспечит очень много повторяющихся величин, которые должны отлично сжаться любым архиватором.

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

Comments

[Сергей Соколов]

Язык, pardon, php. Повторяющиеся инкременты, мм! Тогда понадобится «словарь», частотное распределение этих повторов — это отдельный прогон по всему набору..

[maaGames]

Сергей Соколов: Не-не-не, никакого распределения. Сохряняются инкременты для 32 битных чисел. Т.е. в большинстве случаев это будут малые числа. Даже зип такую последовательность хорошо пожмёт. Это на случайных данных такой алгоритм ничего не даст, но тут же упорядоченные. Т.е. доподлинно известно, что разница будет положительным числом или нулём, и дополнительный бит для знака не понадобится. Мне даже захотелось написать программку, чтобы проверить гипотезу о резком улучшении качества сжатия.)

[Сергей Соколов]

maaGames: про распределение я вспомнил в связи с кодом Хаффмана

[maaGames]

Сергей Соколов: Я на 100% уверен, что в php есть сжатие/распаковка потоковых данных чем-нибудь типа зипа. Код Хаффмана применённый непосредственно к последовательности данных будет мало эффективен, особенно, если кодировать по 32 битному числу. В том же зипе кодом Хаффмана кодируется только словарь (если не ошибаюсь), а данные кодируются прогрессивным алгоритмом (не помню названия), в котором кодируемые блоки постепенно увеличиваются в размере... В общем, я настоятельно не советую изобретать велосипед. php не для этого придумали, а чтобы использовать готовое.

[maaGames]

Сергей Соколов: Для эксперимента написал программку, которая генерирует 100 миллионов чисел, отсортировал по возрастанию и сохранил как есть и разницу между соседними. Получилось два 400 мегабайтных файла. Сжал зипом с настройками по умолчанию, получилось 115 мегабайт для полного файла и 81 мегабайт для файла с разницами. У меня была "плохая" случайность чисел, поэтому различие между полными числами и разницами не существенная. Чем больше у тебя объём данных и чем случайнее числа, тем больше будет разница между двумя вариантами. Так что я всё-таки рекомендую именно потоковое сжатие.

Если ты будешь как-то более хитро обрабатывать данные, например, сохранять разницу в виде 1-3 байтов и флаг того, сколько байтов используется (два бита), то ты лишь увеличишь энтропию и данные будут гораздо хуже сжиматься архиваторами. Без архивирования, в лучшем случае, получится каждый 32 битный int уменьшить до 10 бит. Т.е. на треть. В моём примере это было бы 133 мегабайта. При этом код будет сложным и медленным. И вообще, на php есть возможность работы на уровне битов?

[Сергей Соколов]

maaGames: спасибо за эксперимент! Я не рассматриваю отдельное зипование, т.к. идёт частое обращение к файлам и их изменение. php умеет работать с битами, но в паре с чтением/записью файлов предпочтительнее остановиться на байтах. Поэтому у меня рабочий вариант на сейчас – это писать первое значение, а дальше блоками по 4 инкремента: байт из 4-х двухбитных "длинн", а далее эти четыре блока байтов с оговоренными длинами.

[maaGames]

Сергей Соколов: Я потому и говорю о потоковом сжатии, а не об отдельном зиповании (для эксперимента это было быстрее и я всё-равно не знаю php). Я говорю об архивировании данных на лету, когда ты посылаешь байт в поток вывода, он не просто пишется на диск, а предварительно архивируется (т.е. в поток может и не попасть, пока хотя бы один байт не сформируется). Только не знаю, как это сделать на php и можно ли вообще так сделать.

Если есть много повторяющихся данных, то есть смысл попробовать RLE компрессию. Это когда сперва пишешь количество одинаковых чисел, а потом само число. При чтении они будут записаны нужное число раз. Но это сработает только если бОльшая часть чисел повторяется хотя бы по два раза. Мне опять стало интересно, я сейчас это на своём тестике проверю, что получится. У меня много повторяющихся чисел там.

[Сергей Соколов]

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

[Сергей Соколов]

maaGames: обновил ответ - получается как раз потоковое сжатие с блоком 4x4 байта.

[maaGames]

Сергей Соколов: Жаль, что не повторяются. Но! Раз данных много и числа не повторяются, то чем этих данных больше, тем меньше становится вариантов распределения разниц, между числами! В пределе, у тебя останется всего одна разница, равная "1".
Вариант из UPD обеспечит от почти никакого, до почти четырёхкратного сжатия, что само по себе неплохо. Но! Чем больше данных, тем меньше вариантов инкрементов. Так что для них вполне имеет смысл динамически строить дерево Хаффмана. Только я пока не сильно представляю, как его передавать в файле. Возможно, уменьшить блоки до трёх чисел и в свободном байте кодировать либо код Хаффмана, либо что реальные инкременты записываются. Тогда, чем больше будет размер файлов, тем более эффективно будет сжатие инкрементов работать. Опять же, в пределе, каждый блок из 3-4 чисел будет сжат в один бит. Это когда вся последовать будет различаться на единичку.)
На практике, твоего решения должно быть достаточно, если трёхкратное сжатие тебя устроит.