Каков наилучший алгоритм сжатия для небольших файлов размером 4 КБ?

Ответ 1

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

Я очень рекомендую Deflate (используется zlib и Zip) по ряду причин. Алгоритм довольно быстр, хорошо протестирован, лицензирован BSD и является единственным сжатием, которое должно поддерживаться Zip (в соответствии с Appnote infozip). Помимо основ, когда он определяет, что сжатие больше размера разуплотненного, существует режим STORE, который добавляет только 5 байтов для каждого блока данных (максимальный блок - 64k байт). Помимо режима STORE, Deflate поддерживает два разных типа таблиц Хаффмана (или словарей): динамический и фиксированный. Динамическая таблица означает, что дерево Хаффмана передается как часть сжатых данных и является наиболее гибким (для разных типов неслучайных данных). Преимущество фиксированной таблицы заключается в том, что таблица известна всем декодерам и, следовательно, не должна содержаться в сжатом потоке. Код декомпрессии (или Inflate) относительно прост. Я написал как версии Java, так и Javascript, основанные непосредственно на zlib, и они работают довольно хорошо.

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

Точка уточнения: Zip не является типом сжатия, это контейнер. Для сжатия пакетов я бы обошел Zip и просто использовал API deflate/inflate, предоставляемый zlib.

Ответ 2

Если вы хотите "сжать пакеты TCP", вы можете использовать стандартную методику RFC.

• RFC1978 Протокол PPP Predictor Compression Protocol
• RFC2394 Сжатие полезной нагрузки IP с использованием DEFLATE
• RFC2395 Сжатие полезной нагрузки IP с использованием LZS
• RFC3173 Протокол сжатия полезной нагрузки IP (IPComp)
• RFC3051 Сжатие полезной нагрузки IP с использованием пакета Packet Method ITU-T V.44
• RFC5172 Переговоры по сжатию датаграммы IPv6 с использованием протокола управления IPv6
• RFC5112 Статический словарь присутствия для сжатия сигналов (Sigcomp)
• RFC3284 Формат данных раздельного и сжатия данных VCDIFF
• RFC2118 Протокол Microsoft Point-To-Point Compression (MPPC)

Есть, вероятно, другие релевантные RFC, которые я пропустил.

Ответ 3

Все эти алгоритмы разумно попробовать. Как вы говорите, они не оптимизированы для крошечных файлов, но ваш следующий шаг - просто попробовать их. Вероятно, потребуется всего 10 минут, чтобы протестировать-сжать некоторые типичные пакеты и посмотреть, какие размеры приводят. (Попробуйте использовать и другие сменные флажки). Из полученных файлов вы, вероятно, можете выбрать, какой инструмент лучше всего работает.

Кандидаты, которые вы указали, являются хорошими первыми попытками. Вы также можете попробовать bzip2.

Иногда простые "попробуйте их все" - это хорошее решение, когда тесты просты в использовании.. слишком много думает, иногда замедляет вас.

Ответ 4

Я не думаю, что размер файла имеет значение - если я правильно помню, LZW в GIF сбрасывает свой словарь каждые 4K.

Ответ 5

ZLIB должно быть в порядке. Он используется в MCCP.

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

Ответ 6

Мне посчастливилось использовать библиотеки сжатия zlib напрямую и не использовать какие-либо контейнеры файлов. ZIP, RAR, имеют накладные расходы, чтобы хранить такие вещи, как имена файлов. Я видел, что сжатие приводит к положительным результатам (сжатие меньше исходного размера) для пакетов до 200 байтов.

Ответ 7

Вы можете проверить bicom. Этот алгоритм запрещен для коммерческого использования. Если вы хотите, чтобы это было для профессионального или коммерческого использования, посмотрите на "алгоритм кодирования диапазона".

Ответ 8

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

Ответ 9

Я сделал то, что Арно Сетагая предложил в своем ответе: сделал несколько пробных тестов и сравнил результаты.

Тесты сжатия выполнялись с использованием 5 файлов, каждый из которых имел размер 4096 байт. Каждый байт внутри этих 5 файлов генерировался случайным образом.

ВАЖНО: в реальной жизни данные, скорее всего, не будут случайными, но, как правило, имеют тихие повторяющиеся байты. Таким образом, в реальной жизни сжатие будет иметь тенденцию быть немного лучше, чем следующие результаты.

ПРИМЕЧАНИЕ. Каждый из 5 файлов был сжат сам по себе (т.е. не вместе с другими 4 файлами, что приведет к лучшему сжатию). В следующих результатах я просто использую сумму размера 5 файлов для простоты.

Я включил RAR только для сравнения, хотя он не является открытым исходным кодом.

Результаты: (от лучшего к худшему)

LZOP: 20775/20480 * 100 = 101,44% от исходного размера

RAR: 20825/20480 * 100 = 101,68% от исходного размера

LZMA: 20827/20480 * 100 = 101,69% от исходного размера

ZIP: 21020/20480 * 100 = 102.64% от исходного размера

BZIP: 22899/20480 * 100 = 111,81% от исходного размера

Заключение: К моему удивлению, ВСЕ проверенные алгоритмы произвели больший размер, чем оригиналы!!! Я думаю, они хороши только для сжатия больших файлов или файлов с большим количеством повторяющихся байтов (а не случайных данных, подобных приведенным выше). Таким образом, я не буду использовать какой-либо тип сжатия для своих TCP-пакетов. Возможно, эта информация будет полезна для других, которые считают сжатие небольших фрагментов данных.

EDIT: Я забыл упомянуть, что я использовал опции по умолчанию (флаги) для каждого из алгоритмов.