Является ли вывод алгоритма сжатия (например, gzip, zip или snappy) определенно меньше, чем ввод?
У меня есть этот вопрос, так как мне нужно выделить выходной буфер для сжатых данных. Мне нужно знать, насколько большие выходные данные алгоритма сжатия (например, gzip, zip или snappy) определенно меньше входных данных?
Решение
За с потерями алгоритмы сжатия, возможно, так и есть, хотя и не гарантировано. За без потерь алгоритмы сжатия это не так — сжатие без потерь всегда будет генерировать выходные данные, которые больше чем вход для некоторых входов. Увидеть эта страница Википедии для рассуждения почему.
Другие решения
всегда есть фиксированный размер, связанный с «заголовком», но для любых реальных данных (например, длины этого комментария) сжатие обычно помогает.
Тем не менее, небезопасно объявлять буфер пост-сжатия того же размера, что и входной буфер. Это может быть быть больше
Библиотеки сжатия, такие как zlib (для inflate / deflate, используемые в gzip & pkzip), более вероятно, предназначены для обработки максимум N байтов от входных и выходных максимум M байтов до выделенного пользователем буфера — и сигнализации вызывающей стороне, если библиотека ожидает либо новые входные данные, либо новый / очищенный выходной буфер. Лишь в редких случаях эти библиотеки ожидают полного ввода и вывода в памяти, но работают с блоками.
Также «окна поиска» многих распространенных алгоритмов относительно невелики. Это также ограничивает объем необходимой памяти. Встречные примеры существуют, например BWT используется в tar.bz2.
И, как отмечали другие люди, выходные данные любого алгоритма сжатия без потерь могут быть больше, чем входные данные, и в этом случае большинство хорошо спроектированных библиотек сжатия автоматически реализуют механизм возврата, который просто переносит несжатый блок в контейнер с информацией о размере.
Подводя итог: многим библиотекам сжатия просто необходим буфер размером от нескольких килобайт до нескольких мегабайт, и он обрабатывает ввод любой длины. (Между прочим, такие ограничения включены в MPEG — в дополнение к ожидаемому размеру кадра (например, 128 кбит / с в mp3) они указали максимальный требуемый размер буфера)
Если вы используете zlib (для gzip), вам может пригодиться следующий интерфейс: (от zlib.h)
ZEXTERN uLong ZEXPORT compressBound OF((uLong sourceLen));
/*
compressBound() returns an upper bound on the compressed size after
compress() or compress2() on sourceLen bytes. It would be used before
a compress() or compress2() call to allocate the destination buffer.
*/
Я считаю, что bzip имеет похожий интерфейс. Возвращаемое значение будет немного больше, чем sourceLen, и его следует использовать только в том случае, если данные сжимаются достаточно мало, чтобы можно было выполнить сжатие в памяти. Однако для таких приложений это очень полезно.
Обратите внимание, что большую часть времени вы не будете использовать большую часть выделенной памяти, поэтому вы также можете иметь возможность вернуть неиспользованную память, если вы планируете хранить сжатую версию в памяти в течение любого промежутка времени.
Нет.
Быстрый пример: данные с равномерно распределенными неповторяющимися значениями не могут быть сжаты без потерь, и в результате вы получите исходные данные плюс прикрепленные метаданные.