Следует ли самому сжимать данные перед сжатием стандартным алгоритмом?

Тема в разделе "WASM.A&O", создана пользователем GoldFinch, 27 авг 2010.

  1. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    Задача - сжать данные. Для этого буду использовать какой-то стандартный алгоритм, например DEFLATE (gzip).
    Однако у меня есть какие-то знания сжимаемых данных, и я могу их дополнительно сжать перед тем как сжимать DEFLATE'ом.
    Например мне надо сжимать строку с английскими буквами, я могу оставить только 5 двоичных разрядов на символ, Или например мне надо сжать массив чисел, я могу закодировать их в big-endian так чтобы у них была переменная длина в байтах (7 bit encoded integer).

    Однако у меня почему-то есть опасения, что мой_алгоритм+DEFLATE будет сжимать данные хуже, чем просто DEFLATE.
    Разубедите меня что это не так :)
     
  2. zicker

    zicker Member

    Публикаций:
    0
    Регистрация:
    23 дек 2008
    Сообщения:
    132
    Естественно хуже.
    У тебя энтропия станет близкой к единице.
    Как пример попробуй что-нить заархивировать 2 раза на максимальном сжатии. В большинстве случаев архив больше станет.
     
  3. Rel

    Rel Well-Known Member

    Публикаций:
    2
    Регистрация:
    11 дек 2008
    Сообщения:
    5.241
    так и будет скорее всего... по этой же причине например данные сначала архивируются, а потом шифруются... чем ближе энтропия к максимально, тем меньше избыточность и тем меньше коэффициент сжатия... ты кстати можешь попробовать утилиту ENT, чтобы посмотреть энтропию и потенциальный коэффициент сжатия данных... ну чтобы просто прикинуть, что и как...
     
  4. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    Допустим DEFLATE сожмет исходные данные в 2 раза.
    Мой алгоритм сожмет в 1.5 раза, DEFLATE после моего алгоритма сожмет данные в 1.5раза, получится 1.5*1.5=2.25 раза.

    DEFLATE сжимает без потерь, значит если в исходных данных есть избыточная информация, то и в сжатых данных будет эта избыточная информация которая будет занимать лишние биты. Почему бы ее не выкинуть заранее, если я о ней знаю?
     
  5. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    Вообще да, 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;
    }
     
  6. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    GoldFinch
    А зачем разубеждать?
    Проведи эксперименты и выложи здесь результаты :) другие возьмут на заметку ;)
    Имхо результат предсказать трудно - в некоторых случаях комбинация сжатий будет лучше, в других хуже. Это будет зависеть и от типа данных и от методов предварительного и окончательного сжатий.
     
  7. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    А на энтропию не загоняйся :) Например если возьмёшь любой фрактальный рисунок и заархивируешь его любым стандартным архиватором, то получишь высокую энтропию при весьма посредственном сжатии, что вовсе не означает что там нет избыточной информации ;)) ведь на самом деле этот рисунок развёрнут ооочень компактным кодом и сплошь состоит из повторов. Так что энтропия весьма косвенный параметр (типа средней температуры по больнице). Настоящая эффективность архивации заключается как раз в правильном сочетании типа данных со спообом их архивации.
     
  8. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    чтоб провести эксперимент, надо еще закодить прогу которая выдаст мне данные для сжатия =\
    но похоже действительно без эксперимента не разберешся %)
     
  9. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    По-моему не стоит свеч, лучше найти алгоритм наиболее подходящий для данного типа файла.
    Скорость декомпрессии обычно тоже чего-то стоит, а экономить копейки бессмысленно. Хотя и обработка разными алгоритмами в несколько проходов тоже может дать эффект, но опять это сильно файлозависимо.
     
  10. Y_Mur

    Y_Mur Active Member

    Публикаций:
    0
    Регистрация:
    6 сен 2006
    Сообщения:
    2.494
    Booster
    Тут всё зависит от того какая именно информация о избыточности имеется у ТС. Если это просто "общие соображения" почерпнутые из популярных статей об архивации то скорее всего их использование только "испортит" данные или даст слабый выигрышь.
    Но если в данных есть какая-то "нестандартная" закономерность, то её использование может дать очень хороший выигрышь, поскольку универсальный архиватор в принципе не предназначен для распознавания и эффективной упаковки таких закономерностей. Например, попробуй упаковать стандартным архиватором массив float данных сгенерированных чем нибудь типа y = lg(x)*sin(x) ;) Это конечно надуманный пример, но в реальности данные могут оказаться хорошо интерполируемыми степенным рядом или рядом Фурье или ещё чем нибудь подобным и это может оказаться сущетвенно эффективнее чем универсальный алгоритм упаковки, но только при условии "подходящего" типа данных, собственно именно поэтому универсальные архиваторы даже и не пытаются искать подобные закономерности.
     
  11. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Y_Mur
    Это всё понятно, сильнозависимо от данных. Без экспериментов никак.
     
  12. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    Y_Mur
    у меня дерево структур разных типов. Его надо сериализовать и сжать.
    Поля структур - числа, строки и массивы структур, строк или чисел.

    Вот я и думаю, сжимать его как есть, или сначала сделать более компактным.
    Цель - получить минимальный размер сжатых данных. 95% что сжимать буду алгоритмом DEFLATE.
     
  13. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    DEFLATE и так является комбинацией LZ + Haffman, так что зачем изобретать велосипед? К тому-же арифметика давно свободна от патентов, не вижу смысла в Haffman-е.
     
  14. GoldFinch

    GoldFinch New Member

    Публикаций:
    0
    Регистрация:
    29 мар 2008
    Сообщения:
    1.775
    "сжимать буду алгоритмом DEFLATE" - это значит что у меня в проекте уже есть библиотека (не моя) реализующая этот алгоритм, по этому мне выгодно использовать именно ее, а не что-то другое, чтобы не плодить зависимостей и не раздувать размер программы.