Я использовал этот код HuffmanCode, чтобы сжать этот текст.
И когда это произойдет, когда мы позволим кольцу свободы, когда мы позволим кольцу свободы из каждой деревни и каждой деревушки, из каждого штата и каждого города, мы сможем ускорить тот день, когда все Божьи дети, чернокожие и белые, евреи и язычники, протестанты и католики, смогут взяться за руки и петь на словах старую негритянскую духовность.
Когда я сохраняю этот текст в текстовом файле, размер файла составляет 1 КБ (исходный файл). Затем я сохранил вывод алгоритма Хаффмана, который представляет сжатые данные, в другом текстовом файле (я скопировал вывод из командной строки, а затем вставил его в файл), я обнаружил, что размер закодированных данных в файле составляет 3 КБ!
Это сжатые данные, которые следует использовать в decode_file()
для получения исходных данных.
0110001111100101111110001100111010100001011100100001110111000111000110011100010111110001100111011111100110110111011010011 1111111000011100100010101001111010011011111110110000111110001100111011111100101110010100111101000110111111011000011110000110 10011110110011001110000110000011001101111011101111011100001001101111001011001100111000011000000001100000000111011111101101110010101111 0000110100111101100110011100001100000001010101101101010011011111001011001100111000011000000000110111101000000111111001111101 111011101111001010011011100101011100101001000010110001100100010101100001100011010000111011010010111010000011111000110011101 101101110110100111100000010001000101011000100010000011000101111011010100111001110110010101111010000110110011111110110011101 101111001011111100010111101010011110110011100110010110011111001011011110010100001001001110101001111011100001000001011001101 0010101000010101011011110101000101101111001010000101011011010000101001011011100001100101111110111101110110110111001010001101 1101110010101110001101101001000110101100110010001111110011010001110111100101001001101110111100101011010010011111110110000011 1111010100001100111110100001101010010010011110010100001100010010110101011001001001100000011010000101100010111100110111101001 100001101101101101
Как мне правильно обращаться со сжатыми данными, чтобы получить размер меньше исходного размера файла? вычислить
CR = original data / compressed data
Потому что я пытаюсь рассчитать степень сжатия, но нелогично, что размер сжатых данных больше, чем размер исходных данных. Любые советы, пожалуйста?
Обновлять:
Чтобы вычислить степень сжатия:
int input[] = {1,2,3,4,1,2,3,1,2,3,4,5,2};
int inputsize = 13 * sizeof(int);
symbol :1 freq : 3
symbol :2 freq : 4
symbol :3 freq : 3
symbol :4 freq : 2
symbol :5 freq : 1
(1 * 3) + (2 * 4) + (3 * 4) + (4 * 2)+(5*1)
3+ 8 + 12 + 8 + 5 = 36 bits/8 = ~5 bytes.
int outputsize = 5;
CRatio = inputsize /outputsize
Будет ли этот метод правильным?
Да, я добавил сжатые данные в свой вопрос. Итак, как я могу получить размер закодированных данных?
Сжать в необработанные байты. Кстати, если вы используете символы 0 и 1, гарантируется, что сжатие Хаффмана не будет выполнять фактическое сжатие, потому что для каждого символа используется по крайней мере один бит (а обычно и больше).
Байт содержит 8 бит. Кажется, вы конвертируете каждый бит в свой собственный байт, чтобы вы могли его отобразить. Если вы разделите длину своего вывода на 8 (и округлите в большую сторону), то столько фактических байтов получится в результате кодирования. Вы сжали с 278 байт до 1246 бит, что уместится в 156 байт.
Вы понимаете, что это "кодирование" закодированных данных? Вы сопоставили произвольные 8-битные символы с переменным числом только 0 и 1 8-битных символов, поэтому, конечно, размер файла больше. Фактические, «сырые» сжатые данные не будут текстом, который вы можете скопировать и вставить.
Пожалуйста, что вы предлагаете мне сделать, чтобы получить правильный размер закодированных данных? Можете ли вы объяснить больше, пожалуйста?
Вы читали мой комментарий?
@paddy, да, теперь, если я правильно понимаю, я вычисляю степень сжатия таким образом, это правильно? int sizeoriginalinput = str.size(); float Compratio = ((float)(nbEle))/(encodedString.size()/8);
Вроде правильно. encodedString.size()
— целочисленное значение, поэтому при делении на 8 оно будет усечено. Неясно, нужно ли вам точное количество битов или количество битов, округленное до минимального количества байтов, которое его удержит. Вы на самом деле не делаете ни того, ни другого. Вариант A (точные биты -- масштабировать исходный размер до битов): float ratio = (float)(origSize * 8) / encodedSize;
. Вариант B (округление закодированных битов до ближайшего целого байта): float ratio = (float)origSize / ((encodedSize + 7) / 8);
Большое спасибо @paddy. У меня есть еще один вопрос, если я использую массив int в качестве входных данных для алгоритма и вычисляю отношение таким образом, правильно ли это? int input[] = {1,2,3,4,5,6,7,8,1,3,1}; строка encodedSize; int nbEle = sizeof(input)/sizeof(input[0]); float Compratio = (float)(nbEle * sizeof(int)) / ((encodedSize.size() + 7)/8) ;
Если вам нужен только размер, на самом деле вам не нужно формировать всю сжатую форму, вы можете добавить длины кода, соответствующие входным символам (а затем выполнить это деление на 8, округленное)
Ваш ввод составляет 278 символов, а вывод — 1246 бит. Если вы предполагаете, что каждый символ занимает восемь бит, то вы сжали ввод до 56% от исходного размера. Кажется, это правильно. (Хотя см. примечание ниже.)
Если вы измеряете свой вывод как один байт для каждого 0 и каждого 1, то он действительно будет казаться расширенным. Но только потому, что вы неправильно храните результат. Вам нужно хранить один бит на бит (восемь битов в каждом байте), а не один бит на байт.
Хотя выходная длина выглядит подходящей для кодирования Хаффмана, в ней нет всего, что потребуется декодеру для декодирования битов. Чтобы получить реальную меру сжатия, вам необходимо включить описание кода Хаффмана, а также закодированные данные. Это может занять порядка еще 300 бит.
Спасибо за ваш ответ. если я вычислю степень сжатия, как я сделал в вопросе об обновлении, это правильно?
Ваш размер ввода зависит от того, как он представлен. Эти целые числа не требуют четырех байтов каждое. Если это то, на что обычно похожи ваши целые числа, то вы можете закодировать их по одному байту каждое. Или даже по три бита каждый.
Выходной размер вычисляется правильно, за исключением моего ответа, вам нужно добавить к выходу представление кода Хаффмана.
извините, еще одна вещь, которую я не мог понять в этом предложении «вам нужно добавить представление кода Хаффмана к выводу», как это сделать?
Есть много способов. Я рекомендую сначала написать декодер для ваших кодов Хаффмана. Вы обнаружите, какую информацию вам нужно расшифровать.
Являются ли «закодированные данные», которые вы скопировали, текстовой строкой, состоящей из буквенных символов
0
и1
?