Задача - сжать данные. Для этого буду использовать какой-то стандартный алгоритм, например DEFLATE (gzip). Однако у меня есть какие-то знания сжимаемых данных, и я могу их дополнительно сжать перед тем как сжимать DEFLATE'ом. Например мне надо сжимать строку с английскими буквами, я могу оставить только 5 двоичных разрядов на символ, Или например мне надо сжать массив чисел, я могу закодировать их в big-endian так чтобы у них была переменная длина в байтах (7 bit encoded integer). Однако у меня почему-то есть опасения, что мой_алгоритм+DEFLATE будет сжимать данные хуже, чем просто DEFLATE. Разубедите меня что это не так
Естественно хуже. У тебя энтропия станет близкой к единице. Как пример попробуй что-нить заархивировать 2 раза на максимальном сжатии. В большинстве случаев архив больше станет.
так и будет скорее всего... по этой же причине например данные сначала архивируются, а потом шифруются... чем ближе энтропия к максимально, тем меньше избыточность и тем меньше коэффициент сжатия... ты кстати можешь попробовать утилиту ENT, чтобы посмотреть энтропию и потенциальный коэффициент сжатия данных... ну чтобы просто прикинуть, что и как...
Допустим DEFLATE сожмет исходные данные в 2 раза. Мой алгоритм сожмет в 1.5 раза, DEFLATE после моего алгоритма сожмет данные в 1.5раза, получится 1.5*1.5=2.25 раза. DEFLATE сжимает без потерь, значит если в исходных данных есть избыточная информация, то и в сжатых данных будет эта избыточная информация которая будет занимать лишние биты. Почему бы ее не выкинуть заранее, если я о ней знаю?
Вообще да, 7 bit encoded integer это плохая идея. Такое кодирование не только повышает энтропию за счет избавления от нулевых разрядов, но и понижает ее за счет добавления разрядов конца числа. Тогда у меня все сводится к вопросу "следует ли значения полей структуры хранить в байтах, или их надо хранить в битовых полях, если я знаю их максимально возможные значения". что лучше сожмется struct Foo { byte Field_1 : N1; byte Field_2 : N2; ... byte Field_k : Nk; } или struct Foo { byte Field_1; byte Field_2; ... byte Field_k; }
GoldFinch А зачем разубеждать? Проведи эксперименты и выложи здесь результаты другие возьмут на заметку Имхо результат предсказать трудно - в некоторых случаях комбинация сжатий будет лучше, в других хуже. Это будет зависеть и от типа данных и от методов предварительного и окончательного сжатий.
А на энтропию не загоняйся Например если возьмёшь любой фрактальный рисунок и заархивируешь его любым стандартным архиватором, то получишь высокую энтропию при весьма посредственном сжатии, что вовсе не означает что там нет избыточной информации ) ведь на самом деле этот рисунок развёрнут ооочень компактным кодом и сплошь состоит из повторов. Так что энтропия весьма косвенный параметр (типа средней температуры по больнице). Настоящая эффективность архивации заключается как раз в правильном сочетании типа данных со спообом их архивации.
чтоб провести эксперимент, надо еще закодить прогу которая выдаст мне данные для сжатия =\ но похоже действительно без эксперимента не разберешся %)
По-моему не стоит свеч, лучше найти алгоритм наиболее подходящий для данного типа файла. Скорость декомпрессии обычно тоже чего-то стоит, а экономить копейки бессмысленно. Хотя и обработка разными алгоритмами в несколько проходов тоже может дать эффект, но опять это сильно файлозависимо.
Booster Тут всё зависит от того какая именно информация о избыточности имеется у ТС. Если это просто "общие соображения" почерпнутые из популярных статей об архивации то скорее всего их использование только "испортит" данные или даст слабый выигрышь. Но если в данных есть какая-то "нестандартная" закономерность, то её использование может дать очень хороший выигрышь, поскольку универсальный архиватор в принципе не предназначен для распознавания и эффективной упаковки таких закономерностей. Например, попробуй упаковать стандартным архиватором массив float данных сгенерированных чем нибудь типа y = lg(x)*sin(x) Это конечно надуманный пример, но в реальности данные могут оказаться хорошо интерполируемыми степенным рядом или рядом Фурье или ещё чем нибудь подобным и это может оказаться сущетвенно эффективнее чем универсальный алгоритм упаковки, но только при условии "подходящего" типа данных, собственно именно поэтому универсальные архиваторы даже и не пытаются искать подобные закономерности.
Y_Mur у меня дерево структур разных типов. Его надо сериализовать и сжать. Поля структур - числа, строки и массивы структур, строк или чисел. Вот я и думаю, сжимать его как есть, или сначала сделать более компактным. Цель - получить минимальный размер сжатых данных. 95% что сжимать буду алгоритмом DEFLATE.
DEFLATE и так является комбинацией LZ + Haffman, так что зачем изобретать велосипед? К тому-же арифметика давно свободна от патентов, не вижу смысла в Haffman-е.
"сжимать буду алгоритмом DEFLATE" - это значит что у меня в проекте уже есть библиотека (не моя) реализующая этот алгоритм, по этому мне выгодно использовать именно ее, а не что-то другое, чтобы не плодить зависимостей и не раздувать размер программы.
