Сжатие двоичного массива в C

Question

У меня есть двоичный массив в c, я хочу сжать массив, пожалуйста, предложите мне алгоритм сжатия двоичного массива.Я использовал алгоритм Лемпеля – Зива – Уэлча (LZW), но он мне не подходит, потому что в моих данных нет повторений.

Answer 1

Почему бы просто не использовать libz s deflate ? В качестве дополнительного бонуса libz доступна практически на любой существующей платформе.

Или новее LZMA ? Он превосходит bzip2 при сжатии двоичных данных.

Answer 2

Вы можете легко сократить пространство пополам!

Поскольку ваши двоичные данные не имеют повторений, ваши единственные опции - [0, 1], [1, 0]. Все, что больше, будет повторять либо ноль, либо единицу. Таким образом, вы можете просто представить первый набор с 0, а второй набор с 1. Кодировка будет выглядеть примерно так ...

encode [0, 1] = 0
encode [1, 0] = 1

И расшифровка будет ...

decode 0 = [0, 1]
decode 1 = [1, 0]

Извините за синтаксис haskell, в этом случае он намного более читабелен. Это превращает ваш массив из двух элементов в массив из одного элемента и может храниться в половине пространства! Магия.

EDIT: игнорируется тривиальный случай [0] и [1]. Если их необходимо обработать (хотя на самом деле вам не нужно сжимать 1 бит), получить степень сжатия лучше, чем 100%.

Answer 3

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

Если ваши данные фактически (или почти) распределяются случайным образом, то сжатие может привести к проблеме с дырочками Пиджина. Это говорит о том, что если у вас есть только X пиджинов и Y отверстий, чтобы вставить их, и X> Y, то у вас недостаточно места. В сжатии это означает, что вы не можете воспользоваться возможностью не хранить некоторые пиджины, которые являются идентичными близнецами одного уже в лунке, и просто оставить примечание алгоритму распаковки для клонирования этого пиджина. В кодировании Хаффмана все пиджины являются клонами пиджинов в библиотеке пиджинов. В некоторых других схемах сжатия некоторые пиджины могут быть мегапиджинами, составленными из других пиджинов.

Answer 4

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

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

Answer 5

В качестве альтернативы: ваши двоичные данные представляют определенные значения. Вы можете уменьшить количество битов всех значений. Вам нужно знать возможный диапазон, записывать и читать данные побитовым образом. Это может сэкономить много места, если вы, например, сохраняете значение в uint32, которому нужно всего несколько бит.

Answer 6

Если у вас есть двоичные данные, вы, скорее всего, будете воспринимать их как char[]. В своем вопросе и комментарии вы утверждаете, что повторения (почти) нет (это возможно только в том случае, если у вас не более 256 (char) элементов данных.

).

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

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