Как хранить отсортированный набор целых чисел в двоичном файле?
Большие наборы 32-битных целочисленных значений, отсортированные по возрастанию, только уникальные значения, сохраняются для последовательного чтения. Исходные файлы имеют большой размер, не помещаются в оперативную память, читаются блок за блоком. Пока я просто сохраняю их как двоичные файлы, 4 байта на значение.
По мере роста системы необходимо оптимизировать пространство хранения / резервного копирования, и я считаю, что существует большой потенциал для эффективного сжатия таких данных, учитывая их сортировку.
Я придумал, чтобы сохранить начальное значение, а затем приращения, которые, как правило, становятся меньшими значениями по мере роста числа значений в наборе. Округляя их размер до полных байтов, я предлагаю оставить только значащие байты на приращение, поэтому вместо 4 может быть 1-2-3 байта на приращение. И чтобы сигнализировать о количестве используемых байтов, я бы использовал заголовок 2 бита на приращение.
Поток будет выглядеть так:
01010101 01010101 01010101 01010101 - initial value
Four increments block start
10110101 - b bytes used: four 2-bit pairs
(10 11 01 01 = 2, 3, 1, 1)
01010101 01010101 - inc
01010101 01010101 01010101 - inc
01010101 - inc
01010101 - inc
Four increments block start
11011101 - b (11 01 11 01 = 3, 1, 3, 1)
01010101 01010101 01010101 - inc
01010101 - inc
01010101 01010101 01010101 - inc
01010101 - inc
...
Я пытаюсь изобрести колесо здесь? Может ли сжатие потока быть здесь более эффективным, оставаясь работающим на довольно небольших блоках?
Решение
Это называется целые числа переменной длины или величины переменной длины. Возможно, более эффективный подход для вашего приложения в зависимости от распределения ваших различий, а также более быстрый, а также избегающий работы с потоком битов, заключается в кодировании конца целого числа в старшем бите каждого байта с использованием оставшихся семи битов. каждый байт для целочисленных битов. Так, например, старший бит 1 может указывать конец целого числа, причем целочисленные биты сначала сохраняют старшие значащие биты. Тогда 0..127 сохраняется как байты 0x80..0xff. Если первый байт равен 0x01..0x7f, то у вас есть старшие семь битов числа, и вы переходите к следующим байтам для следующих семи битов, пока не получите старший бит, равный единице.
Это также имеет свойство, что начальный байт 0x00 не разрешен, так что вы можете использовать это, чтобы указать конец потока.
Ваша схема может быть более эффективной, если, например, различия в диапазоне 128 .. 255 очень распространены. В этом случае ваша схема использует десять битов для тех, где описанный выше использует 16. С другой стороны, если различия в диапазоне 0.127 являются наиболее распространенными, приведенное выше может быть наилучшим, поскольку кодирует их как восемь битов. где твой использует десять.
После кодирования вы можете получить дополнительное сжатие, применив стандартную процедуру сжатия, такую как Zlib.
Другие решения
Других решений пока нет …