Member 13740691 Ответов: 7

Код C для сжатия и распаковки строки

Мне нужно сжать этот вывод :

AE9B56FC5845AC8298FFC57E307145A4

а потом мне нужно распаковаться, чтобы вернуться обратно.

Что я уже пробовал:

Мне нужно сжать этот вывод :

AE9B56FC5845AC8298FFC57E307145A4

а длина должна быть меньше 24 бит >>

enhzflep

zlib будет "сжимать" эти 16 байт до 19 байт.
Простое арифметическое кодирование создает 18 байт выходных данных
Хаффман с умным представлением дерева возвращает 11 байт выходных данных
*** Хаффман without включенное дерево возвращает 3 байта ***
winRar возвращает вам 91 байт.


TLDR; кажется, что вы пытаетесь толкнуть 💩 вверх по холму своим носом, ожидая, что он будет блестящим и пахнущим розами, когда вы достигнете вершины!



Хотя вы можете жестко закодировать дерево Хаффмана и получить обратно всего 3 байта-дерево будет отличаться для разных входных данных, так что эта идея в основном не является стартовой.
zlib может использовать заранее определенное дерево, но выход не будет таким маленьким, так как он строит полное дерево, а затем использует коды длиннее оптимального (для этого случая использования) из-за того, что он имеет 256 листовых узлов, а не только 16.

Посмотрите на puff.c от Марка Адлера, если вам нужен относительно простой источник hufman для просмотра. (он находится в источниках zLib) просто не ожидайте чудес!

7 Ответов

Рейтинг:
2

David O'Neil

Вы можете использовать сжатие "карты", которое по существу является:

char value;
if (input == "AE9B56FC5845AC8298FFC57E307145A4") value = 1;

...

if (value == 1) output "AE9B56FC5845AC8298FFC57E307145A4"


Но это немного нереалистично в реальном мире, хотя я уже давно превзошел ваше требование "24 бит".

Рейтинг:
1

OriginalGriff

Вы не можете или, скорее всего, не можете - вы не можете гарантировать, что результаты любого сжатия будут "меньше n бит", и поскольку вы начинаете с того, что выглядит как 32 шестнадцатеричные цифры, вам нужно 128 бит, чтобы сохранить его несжатым, что означает, что вы ищете примерно сжатие 1:5 - и на планете нет алгоритма, который гарантировал бы это для "случайных данных".

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

Maciej Los

5ed!

Рейтинг:
1

Patrice T

Это совершенно нереально.
Ваши примерные данные шестнадцатеричны, это означает, что каждый символ равен 4 битам.
Таким образом, "AE9B56FC5845AC8298FFC57E307145A4" является шестнадцатеричным числом 32*4=128 бит.
Без каких - либо знаний о том, что это за данные, нет никакого способа сжать их до 24 бит, он даже не уверен, что их вообще можно сжать.

Рейтинг:
1

KarstenK

Сжатие-это искусство, в основном вам нужна надежная декомпрессия. Если ваш текст является шестнадцатеричное представление вам нужно 4 бита для такого символа. Таким образом, первый символ получает 4 первых биты в байт. Лучше всего вы работаете с поразрядные операции сдвига .

// A => 11
// E => 15
buffer[0] = (11 << 4) + 15;
char high = buffer[0] >> 4;// high value
char low = buffer[0] & 15;// low value (flag low 4 bits)

Рейтинг:
1

steveb

Я дам тебе подсказку.
В строке "

AE9B56FC5845AC8298FFC57E307145A4
"
у вас есть 3 появления буквы А
2 е
2 из 9
5 из 5
3 Ф
3 с
3 из 4

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

Dave Kreskowiak

Да, но все равно невозможно выполнить ограничение "длина должна быть меньше 24 бит".

Рейтинг:
0

CPallini

Вообще говоря, вы не можете этого сделать.
Это шестнадцатеричное представление размером 16 байт. Если байты могут произвольно изменяться, то нет никакого способа уменьшить их до 3 единиц.
С другой стороны, если вы можете наложить на них ограничения, то вы, возможно, добьетесь успеха (например, если это "сообщение", и вы знаете, например, что у вас есть только 1000 различных "сообщений", то вы можете сжать их до 2 байт путем перечисления).
Пожалуйста, обратите внимание, что вы ничего не говорите о возможных ограничениях.

Maciej Los

5ed!

Рейтинг:
0

Jochen Arndt

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

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

Даже при более удобном для сжатия вводе вы, скорее всего, не получите конечную длину 24 бита (3 байта) от 16-байтового двоичного ввода или строки длиной 32.

Maciej Los

5ed!