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

Question

Я пытаюсь сжать TCP-пакеты, каждый размером около 4 КБ. Пакеты могут содержать любой байт (от 0 до 255). Все тесты алгоритмов сжатия, которые я нашел, были основаны на файлах большего размера. Я не нашел ничего, что сравнивало бы степень сжатия различных алгоритмов для маленьких файлов, что мне и нужно. Мне нужно, чтобы он был с открытым исходным кодом, чтобы он мог быть реализован на C ++, поэтому не RAR, например. Какой алгоритм можно рекомендовать для небольших файлов размером около 4 килобайт? LZMA ? HACC ? ZIP ? GZIP ? bzip2

Answer 1

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

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

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

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

Answer 2

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

• RFC1978 Протокол сжатия PPP Predictor
• RFC2394 Сжатие полезной нагрузки IP с использованием DEFLATE
• RFC2395 Сжатие полезной нагрузки IP с использованием LZS
• RFC3173 Протокол сжатия полезной нагрузки IP (IPComp)
• RFC3051 Сжатие полезной нагрузки IP с использованием пакетного метода ITU-T V.44
• RFC5172 Согласование для сжатия дейтаграмм IPv6 с использованием протокола управления IPv6
• RFC5112 Статический словарь, специфичный для присутствия, для сжатия сигналов (Sigcomp)
• RFC3284 Общий формат данных дифференцирования и сжатия VCDIFF
• RFC2118 Протокол многоточечного сжатия Microsoft (MPPC)

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

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

Answer 8

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

Answer 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: Я забыл упомянуть, что я использовал параметры (флаги) по умолчанию для каждого из алгоритмов.