Сжатие для уникального потока данных

Вы пробовали для этого bzip2? http://bzip.org/

У меня он всегда работал лучше, чем zlib.

Вы считали Кодирование длин серий?

Или попробуйте следующее: вместо хранения самих чисел вы сохраняете различия между числами. 1 1 2 2 2 3 5 становится 1 0 1 0 0 1 2. Теперь большинство чисел, которые вам нужно кодировать, очень маленькие. Чтобы сохранить небольшое целое число, используйте 8-битное целое число вместо 32-битного, которое вы будете кодировать на большинстве платформ. Это коэффициент 4 прямо здесь. Если вам действительно нужно быть готовым к большим пропускам, чем это, обозначьте старший бит 8-битного целого числа, чтобы сказать: «это число также требует следующих 8 бит».

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

Ни один из этих вариантов не является особенно сложным для реализации, и все они работают очень быстро и с очень небольшим объемом памяти (в отличие, скажем, от bzip).

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

1. Разделите свои интервалы на 4 байта, так что i₀, i₁, i₂, ..., i_n становится b_0,0, b_0,1, b_0,2, b_0,3, b_1,0, b_1,1, b_1,2, ... Затем запишите все b_1,3, а затем b_n,0, b_n,1 и b_n,2. Если в большинстве случаев ваши числа отличаются только на бит или два, вы должны получить хорошие длинные серии повторяющихся байтов, которые должны действительно хорошо сжиматься, используя что-то вроде Run-length Encoding или zlib. Это мой любимый из представленных мной методов.

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

3. Если у вас есть разные биты, у вас все равно могут быть большие различия, но если у вас больше шансов иметь большие числовые различия, которые соответствуют (обычно) одному или двум разным битам, вам может быть лучше со схемой, в которой вы создаете ahebyte array - используйте первые 4 байта для кодирования первого целого числа, а затем для каждой последующей записи используйте 0 или более байтов, чтобы указать, какие биты должны быть перевернуты - сохраняя 0, 1, 2, ... или 31 в байте, с часовым (скажем, 32), чтобы указать, когда вы закончите. Это может привести к тому, что необработанное количество байтов, необходимое для представления, и целое число, в среднем будет близким к 2, причем большинство байтов поступает из ограниченного набора (0–32). Запустите этот поток через zlib, и, возможно, вы будете приятно удивлены.

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

В вашем случае zlib - это метод побайтного сжатия, но ваши данные представляют собой (32-битные?) Целые числа. Вам не нужно переопределять zlib самостоятельно, но вам нужно прочитать, как он работает, чтобы вы могли понять, как представить его с легко сжимаемыми данными или вообще подходит ли это для ваших целей.

Zlib реализует форму кодирования Lempel-Ziv. JPG и многие другие используют кодирование Хаффмана для своего внутреннего интерфейса. Кодирование длин серий популярно во многих случаях. И т. Д. И т. Д ...

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

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

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

Если различаются более чем на 4 бита, сохраните целое число.

Эта схема может не подойти, если у вас также много совершенно разных кодов, поскольку теперь они будут занимать по 5 байтов вместо 4.

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

Возьмите входной поток, например:

1101
1101
1110
1110
0110

и вывод:

1101
0000
0010
0000
1000

немного псевдокода

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

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

Когда вы хотите распаковать:

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

Это также имеет то преимущество, что это простой алгоритм, который будет работать очень, очень быстро, поскольку это просто XOR.

«Zlib сжимает его примерно в 4 раза». означает, что файл размером 100 КБ теперь занимает 300 КБ отрицательный; это впечатляет по любому определению :-). Я предполагаю, что вы имеете в виду, что он уменьшает его на 75%, то есть до 1/4 от исходного размера.

Одна из возможностей оптимизированного сжатия заключается в следующем (предполагается, что 32-битное целое число и не более 3 битов меняются от элемента к элементу).

• Выведите первое целое число (32 бита).
• Выведите количество изменений битов (n = 0–3, 2 бита).
• Выведите n битовых спецификаторов (0–31, по 5 бит).

Худший случай для этого сжатия - 3-битные изменения в каждом целом числе (2 + 5 + 5 + 5 бит), что будет иметь тенденцию к 17/32 от исходного размера (46,875% сжатия).

Я говорю «стремится к», поскольку первое целое число всегда 32 бита, но для любого массива приличного размера это первое целое число будет незначительным.

В лучшем случае это файл с идентичными целыми числами (без изменения бит для каждого целого числа, только 2 нулевых бита) - это будет иметь тенденцию к 2/32 исходного размера (сжатие 93,75%).

Если вы усредняете 2 бита для каждого последовательного целого числа (как вы говорите, это ваш общий случай), вы получите 2 + 5 + 5 бит на целое число, что будет иметь тенденцию к сжатию 12/32 или 62,5%.

Ваша точка безубыточности (если zlib дает сжатие 75%) составляет 8 бит на целое число, что будет

• однобитовые изменения (2 + 5 = 7 бит): 80% переходов.
• двухбитовые изменения (2 + 5 + 5 = 12 бит): 20% переходов.

Это означает, что ваше среднее значение должно быть 1,2 битных изменений на целое число, чтобы это было оправдано.

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

Я заметил (во всяком случае, для моего материала) он выполняет много лучше, чем WinZip на платформе Windows, поэтому он также может превзойти zlib.