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

Question

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

Злиб сжимает его примерно до 25% от его первоначального размера. Это хорошо, но я не думаю, что его алгоритм особенно хорошо подходит для этой проблемы. Кто-нибудь знает библиотеку сжатия или простой алгоритм, который мог бы работать лучше для этого типа информации?

Обновление: zlib после преобразования его в массив xor deltas сокращает его примерно до 20% от исходного размера.

Answer 1

Если большинство целых чисел действительно совпадают с предыдущими, и различие между символами обычно может быть выражено как однобитное отражение, это звучит как работа для 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-разрядных целых числах и все еще может кодировать совершенно другое целое число, появляющееся в потоке. Вы избавлены от беспокойства, связанного с упаковкой битов самостоятельно, так как все остается в большом количестве.

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

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

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

Answer 2

Рассматривали ли вы Кодирование длин серий ?

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

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

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

Answer 3

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

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

Zlib реализует форму кодирования Лемпеля-Зива. JPG и многие другие используют кодирование Хаффмана для своего бэкэнда. Кодирование длин серий популярно для многих специальных применений. И т.д. и т.п. ...

Answer 4

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

1. Разбейте ваши целые по 4 байта, поэтому я ₀ , я ₁ , я ₂ , ..., я _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} , b _{n, 3} . Затем запишите все b _{i, 0} s, затем b _{i, 1} s, b _{i, 2} s и b _{i , 3} s. Если в большинстве случаев ваши числа отличаются только на бит или два, вы должны получить хорошие длинные серии повторяющихся байтов, которые должны действительно хорошо сжиматься, используя что-то вроде Run-length Encoding или zlib. Это мой любимый метод, который я представляю.

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

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

Answer 5

"Злиб сжимает его примерно в 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.

Answer 6

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

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

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

Если существует более 4 разрядов, сохраните целое число.

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

Answer 7

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

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