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

Question

Для последовательного чтения сохраняются большие наборы 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 

... 

я пытаюсь изобрести колесо здесь? Может ли сжатие потока быть более эффективным здесь, оставаясь работоспособным на довольно небольших блоках?

Answer 1

Это называется variable-length integers or variable-length quantities. Возможно, более эффективный подход для вашего приложения в зависимости от распределения ваших различий и более быстрый, а также избежание работы с потоком бит, заключается в том, чтобы закодировать конец целого числа в верхнем бите каждого байта, используя оставшиеся семь бит каждый байт для целых битов. Так, например, вы могли бы иметь высокий бит из 1, указывающий конец целого числа, причем биты с целым числом сначала запоминают наиболее важные биты. Тогда 0..127 сохраняется как байты 0x80..0xff. Если первый байт равен 0x01..0x7f, тогда у вас есть семь стартовых разрядов, и вы переходите к следующим байтам для следующих семи бит, пока не получите высокий бит.

Это свойство также имеет свойство, что начальный байт 0x00 не разрешен, поэтому вы можете использовать его для указания конца потока.

Ваша схема может быть более эффективной, если, например, различия в диапазоне 128..255 очень распространены. В этом случае ваша схема использует десять бит для тех, где используется описанная выше. С другой стороны, если различия в диапазоне 0..127 являются наиболее распространенными, вышеприведенное может быть лучше, поскольку оно кодирует их как восемь бит , где ваш использует десять.

Проведя кодирование, вы можете получить дальнейшее сжатие, применяя стандартную процедуру сжатия, такую ​​как zlib.