Java стратегии Deflater - DEFAULT_STRATEGY, ФИЛЬТРОВАННЫЙ и HUFFMAN_ONLY

Варианты стратегии, упомянутые в Java Deflater, возникли в реализации zlib (C) ZLIB и ( RFC 1950 ) и DEFLATE ( 1951 ), я полагаю. Они присутствуют практически во всех библиотеках сжатия, реализующих DEFLATE.

Чтобы понять, что они означают, вам нужно немного узнать о DEFLATE . Алгоритм сжатия сочетает в себе кодирование LZ77 и Хаффмана. Основы:

• Сжатие LZ77 работает, находя повторяющиеся последовательности данных. Реализации обычно используют «скользящее окно» размером от 1k до 32k, чтобы отслеживать данные, которые были переданы ранее. Для любых повторов в исходных данных, вместо того, чтобы вставлять повторяющиеся данные в выходные данные, сжатие LZ77 вставляет «обратную ссылку». Представьте себе обратную ссылку: «сюда вставьте те же данные, которые вы видели 8293 байта назад, для 17 байтов». Обратная ссылка кодируется как эта пара чисел: длина - в данном случае 17 - и расстояние (или смещение) - в данном случае 8293.

• Кодирование Хаффмана заменяет фактические данные кодами.Когда данные говорят X, код Хаффмана говорит Y. Очевидно, что это помогает сжатию только в том случае, если замена короче оригинала. (контрпример есть в фильме Джима Керри Да, человек , когда Норм использует слово «Автомобиль» в качестве короткого имени для Карла. Карл указывает, что Карл уже довольно короткий.) Алгоритм кодирования Хаффмана определяет частоту анализ, и использует кратчайшие заменители наиболее часто встречающихся последовательностей данных.

Deflate объединяет их, так что можно использовать коды Хаффмана в обратных ссылках LZ77. Параметры стратегии для различных компрессоров DEFLATE / ZLIB просто сообщают библиотеке, сколько весить по Хаффману по сравнению с LZ77.

• FILTERED обычно означает, что совпадения LZ77 остановлены на длине 5. Поэтому, когда в документации указано

  Use (Filtered) для данных, созданных фильтром (или предсказателем), ... Отфильтрованные данные состоят в основном малых значений с несколько случайным распределением.

  (из справочной страницы zlib )
  ... мое прочтение кода говорит, что он выполняет сопоставление LZ77, но только до последовательностей из 5 или меньше байтов. Думаю, это то, что документ подразумевает под "малыми ценностями". Но номер 5 не упоминается в документе, поэтому нет гарантии, что номер не будет изменен с rev на rev или с одной реализации ZLIB / DEFLATE на другую (например, версию C и версию Java).

• HUFFMAN_ONLY говорит, что коды замены выполняются только на основе частотного анализа. HUFFMAN_ONLY работает очень-очень быстро, но не очень эффективно для сжатия большинства данных.Если у вас нет очень небольшого диапазона байтовых значений (например, если байты в вашем фактическом потоке данных принимают одно из 20 из возможных 255 значений) или если у вас нет экстремальных требований к скорости сжатия за счет размера, HUFFMAN_ONLY не будет тем, что вы хотите.

• ПО УМОЛЧАНИЮ объединяет эти два способа, как, по мнению авторов, будет наиболее эффективным для большинства приложений.

Насколько я знаю, в DEFLATE нет возможности сделать только LZ77. Стратегии LZ77_ONLY нет. Но, конечно, вы можете построить или приобрести свой собственный кодировщик LZ77, и это будет «только LZ77».

Имейте в виду, что стратегия никогда не влияет на правильность сжатия; он влияет только на его работу и производительность, будь то скорость или размер.

Есть и другие способы настройки компрессора. Один из них - установить размер скользящего окна LZ77. В библиотеке C это указывается с помощью параметра «Оконные биты». Если вы понимаете LZ77, то вы знаете, что меньшее окно означает меньше поиска назад, что означает более быстрое сжатие за счет пропуска некоторых совпадений. Часто это более эффективная ручка, которую можно повернуть при сжатии.

Суть в том, что в случае 80% вам не нужно настраивать стратегию. Возможно, вам будет интересно поиграться с битами окна, просто чтобы посмотреть, что происходит. Но делайте это только тогда, когда вы сделали все остальное, что вам нужно сделать в своем приложении.

ссылка:
Как работает DEFLATE, Антей Полевой шпат