Gzip / Deflate распознает шаблоны

Question

Я изучаю внутреннюю работу Gzip и понимаю, что он использует комбинацию Кодирование Хаффмана и LZ77 .

Я также понимаю, что файл Gzip разделен на блоки, и для каждого блока есть словарь, созданный для него.Затем часто встречающиеся подобные данные заменяются указателями, указывающими на местоположения в словаре.

Таким образом, во фразе «скачки других лошадей» слово лошадей заменяется указателем.

Однако что, если у меня есть массив 32-битных целых, но он хранит только числа до 24 бит?В качестве аргументов, скажем, эти 24-битные числа очень случайны, их трудно сжать, и в них трудно найти повторы.

Это сделает первые 8 бит каждого целого числа легко сжимаемой строкой из 0, но каждая строкапотребуется указатель, и каждый указатель по-прежнему занимает некоторое количество данных.Даже 1-битный указатель (который, как я знаю, меньше, чем реально возможный) все равно будет занимать 12,5% исходного пространства.

Это может показаться несколько избыточным, когда массив можно легко уменьшить до 24-битного массива с базовым распознаванием образов.

Поэтому мой вопрос:

Содержит ли Gzip какие-либо механизмы для лучшего сжатия файла, чем указатели словаря?

Насколько хорошо Gzip может сжимать небольшие объемы повторяющихся данных, а затем небольшие объемы трудно сжимаемых данных?

Answer 1

В каждом блоке deflate нет «словаря, созданного для него».Для каждого блока deflate создается набор кодов Хаффмана для символов литерала / длины и символов расстояния.

Словарь, на который вы ссылаетесь, представляет собой просто 32K байта несжатого ввода, который непосредственно предшествует байту, который в данный момент находитсясжат.Вот и все.Каждая пара длина / расстояние может ссылаться на строку от 3 до 258 байтов в последних 32K.Это не зависит от блоков deflate, и такие ссылки часто возвращаются на один или несколько блоков.

Deflate не будет успешным при попытке сжать последовательность из трех случайных байтов, нулевого байта, трех случайных байтов, нулевого байта.Не будет никаких полезных повторяющихся строк, где deflate сможет только кодировать Хаффмана литералами, причем нули встречаются чаще.Нули будут кодироваться как два бита, поскольку они встречаются чуть более 25% времени, а остальные литералы - не менее 8,25 бита каждый.Для этих данных это даст в среднем около 6,7 бит на байт или сжатый коэффициент 0,85.Фактически, gzip дает около 0,86 для этих данных.

Если вы хотите сжать эту последовательность, просто удалите нулевые байты! Тогда все готово, дальнейшее сжатие невозможно при соотношении0,75.