Алгоритм сжатия Deflation

The deflation algorithm used by gzip (also zip and zlib) is a variation of
LZ77 (Lempel-Ziv 1977, see reference below). It finds duplicated strings in
the input data.  The second occurrence of a string is replaced by a
pointer to the previous string, in the form of a pair (distance,
length).  Distances are limited to 32K bytes, and lengths are limited
to 258 bytes. When a string does not occur anywhere in the previous
32K bytes, it is emitted as a sequence of literal bytes.  (In this
description, `string’ must be taken as an arbitrary sequence of bytes,
and is not restricted to printable characters.)

Literals or match lengths are compressed with one Huffman tree, and
match distances are compressed with another tree. The trees are stored
in a compact form at the start of each block. The blocks can have any
size (except that the compressed data for one block must fit in
available memory). A block is terminated when deflate() determines that
it would be useful to start another block with fresh trees. (This is
somewhat similar to the behavior of LZW-based _compress_.)

Duplicated strings are found using a hash table. All input strings of
length 3 are inserted in the hash table. A hash index is computed for
the next 3 bytes. If the hash chain for this index is not empty, all
strings in the chain are compared with the current input string, and
the longest match is selected.

The hash chains are searched starting with the most recent strings, to
favor small distances and thus take advantage of the Huffman encoding.
The hash chains are singly linked.

antananarivo — профиль | СПЛЕТНИК

There are no deletions from the
hash chains, the algorithm simply discards matches that are too old.

To avoid a worst-case situation, very long hash chains are arbitrarily
truncated at a certain length, determined by a runtime option (level
parameter of deflateInit). So deflate() does not always find the longest
possible match but generally finds a match which is long enough.

deflate() also defers the selection of matches with a lazy evaluation
mechanism. After a match of length N has been found, deflate() searches for
a longer match at the next input byte. If a longer match is found, the
previous match is truncated to a length of one (thus producing a single
literal byte) and the process of lazy evaluation begins again. Otherwise,
the original match is kept, and the next match search is attempted only N
steps later.

The lazy match evaluation is also subject to a runtime parameter. If
the current match is long enough, deflate() reduces the search for a longer
match, thus speeding up the whole process. If compression ratio is more
important than speed, deflate() attempts a complete second search even if
the first match is already long enough.

The lazy match evaluation is not performed for the fastest compression
modes (level parameter 1 to 3). For these fast modes, new strings
are inserted in the hash table only when no match was found, or
when the match is not too long. This degrades the compression ratio
but saves time since there are both fewer insertions and fewer searches.

antananarivo

14 ноября 2008 г. ApacheFreeBSDGZipОптимизация

Сжимаем сайт при помощи mod_deflate

Решил заняться оптимизацией скорости загрузки блога и решил его прогнать при помощи сервиса webo.in, в рекомендациях по оптимизации было написано:

HTML-файлы могут быть уменьшены в размере.
Рекомендуется применить для них технику minify, также размер файлов может быть существенно (до 80%) уменьшен через архивирование (gzip).

Решил начать с архивирования файлов… Перейдем к mod_deflate

  1. Apache 1.3 — mod_gzip и mod_deflate (разработанный Сысоевым, автором nginx). Подробнее можно почитать у Лиссяры -> mod_gzip — сжатие html страниц «на лету»
  2. Apache 2.2 — mod_deflate

Так как у меня версия Apache 2.2.8 на сервере, то буду рассказывать про второй пункт. Для начала необходимо установить данный модуль (желательно ставить через порты), но у меня он был уже установлен, я его просто активировал в httpd.conf

Открываем файл конфигурации Apache

И добавляем правило:

AddOutputFilterByType — тут назначаем фильтр DEFLATE для миме типов: text/html text/plain text/xml

DeflateCompressionLevelстепень gzip-компрессииот1 до 9 (Инструмент для расчета степени gzip-сжатия в помощь)

Проверяем наши настройки

Проверяем сжатие

или

ну или посмотрите в своём любимом броузере (для FireFox рекомендую Live Http Headers)

Если видим строку «Content-Encoding: gzip», то всё в порядке!

Идём дальше, если нет, проверьте предыдущие шаги.

Теперь в фильтр можно добавить ещё типы: text/css и text/javascript

Логи храним в отдельном файле

Далее, указываем в виртуальных хостах путь до лога, например:

Когда речь заходит о передаче больших объёмов информации, особенно текстовой, логично вспомнить о сжатии данных. Существует множество алгоритмов сжатия, многие из которых имеют давнюю историю, некоторые алгоритмы вплотную подбираются к теоретическому пределу степени сжатия — но требуют много времени и памяти, другие работают быстро и скверно, какие-то из них прямо предназначены для определённых типов данных, но стандартом в HTTP давно стал gzip.

Этот формат воплощает метод DEFLATE, который базируется на двух базовых алгоритмах: LZ77 и кодировании Хаффмана.

LZ77 ищет во входном потоке данных повторящиеся последовательности, и заменяет все повторные их вхождения ссылками. В бинарных данных это довольно редкая ситуация, но в тексте это происходит гораздо чаще, и это даёт возможность добиться существенного сжатия уже на этом этапе.

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

Дальше работает алгоритм Хаффмана, который подсчитывает частоту употребления каждого фрагмента из словаря, и назначает частым фрагментам более короткий номер — так мы сокращаем сами номера фрагментов. Доказано, что код Хаффмана очень близок к теоретическому пределу степени сжатия.

Эти алгоритмы можно использовать, к примеру, для сжатия JSON-сообщений — в типичном случае вы получите степень сжатия от 30% (для коротких сообщений) до 2 раз (если сообщение длиннее 500 байт) и больше.

Классическая библиотека zlib, написанная и поддерживаемая авторами самого gzip Жан-Лу Гайи и Марком Адлером, довольно неудобна в использовании — это множество c и h-файлов, зависимость от системных дефайнов, привязка к системным форматам целых чисел. У меня не получилось её завести, и я обратился к другой библиотеке, которую заметил уже очень давно — miniz за авторством Rich Geldreich.

Она предоставляет простые функции compress и uncompress, которые принимают входной поток данных (массив unsigned char) + длину данных в нём, и указатель на выходной буфер + указатель на int, в котором будет записана длина сжатых данных.

На компьютере библиотека запускается очень легко, нужно лишь подключить её через include (странный способ):

Однако, при попытке перенести этот код на микроконтроллер STM32F217 возникла проблема — выделение памяти под структуру tdefl_compressor заканчивается неудачей.

Она требует у malloc кусок памяти размером в 320 килобайт, чего в микроконтроллерах отродясь не бывало. Нехило, разом зохавать 320 кБ. Чо ж делать-то?

Посмотрим, из чего состоит эта структура.

Чему же равны эти дефайны?

Похоже, выделяются массивы отдельно под первый раунд (LZ77) и второй раунд сжатия (код Хаффмана). Уже и так всё понятно, но давайте посмотрим реальные размеры всех этих массивов:

m_dict = 33 кБ

m_huff_count + m_huff_codes + m_huff_code_sizes = 4 кБ

m_lz_code_buf = 25 кБ

m_next = 65 кБ (!)

m_hash = 8 кБ

m_output_buf = 32 кБ

Ну всё ясно, нашли главных виновников. Надо уменьшать размеры этих массивов, поправив дефайны — но я не знаю как библиотека работает «под капотом», наверняка же нельзя просто так наобум кромсать массивы. Директива TDEFL_LESS_MEMORY не особенно помогла, библиотека по-прежнему требовала 168 кБ памяти. В моём STM32F217 всего 128 кБ памяти, да и на другие задачи память тоже нужна.

Я написал автору библиотеки, Rich Geldreich. Первое что он предложил сделать — это уменьшить размер словаря (m_dict), но он в два раза меньше самого большого массива, m_next. Вторая рекомендация была уже более предметной:

  1. Уменьшить TDEFL_LZ_CODE_BUF_SIZE до 4-8 кБ или около того. Уменьшение размера блоков увеличит количество блоков на выходе, уменьшая степень сжатия.
  2. Уменьшить TDEFL_LZ_HASH_BITS до 9-10, но это приведёт к уменьшению производительности. При этом нужно установить TDEFL_LEVEL1_HASH_SIZE_MASK равным меньшему из 4095 или (1 « TDEFL_LZ_HASH_BITS) — 1.
  3. Значительное уменьшения требований по памяти достигается уменьшением TDEFL_LZ_DICT_SIZE до 1-16 кБ, при этом оно должно быть степенью двойки. Rich опасался что это приведёт к глюкам в коде, но забегая вперёд скажу что всё прошло гладко.

В итоге я доигрался с уменьшением массивов до:

TDEFL_LZ_CODE_BUF_SIZE = 1 кБ TDEFL_OUT_BUF_SIZE = TDEFL_LZ_CODE_BUF_SIZE * 1 (вместо * 1.3) TDEFL_LZ_HASH_BITS = 8 TDEFL_LZ_DICT_SIZE = 1 кБ

доведя таким образом memory footprint до ровно 10 кБ.

Ещё одна проблема — по умолчанию размер кучи ограничен всего 0x2000 = 8192 байт, больше вы выделить не можете. Это легко поправить, в IAR нужно зайти в свойства проекта -> Linker -> Override default, Edit -> Stack/Heap sizes -> HEAP, я поставил 0x15000. Для STM32F217 этого достаточно, можно чуть больше.

Для запуска в окружении МК библиотеке нужно также задать дефайны MINIZ_NO_STDIO и MINIZ_NO_TIME, чтобы она не попыталась использовать системные функции ввода/вывода и времени.

Проверив работу библиотеки на разных наборах данных (я экспериментировал с JSON-строками) — преимущественно текстовых, преимущественно численных, с кусками русскоязычных идентификаторов и так далее, я не заметил никаких проблем.

Antananarivo

Одна из моих тестовых JSON-строк:

Она имеет длину 183 байта, после сжатия библиотекой miniz она сокращается до 134 байт (-34%), очень хороший результат для такой сравнительно короткой строки: ведь чем длиннее строка, тем больше получается словарь, и сжатие становится эффективнее, потому что для очень многих последовательностей найдётся образец в словаре. На коротких строках словарь мал, и нельзя ожидать сильного сжатия.

На более длинных строках, таких как пример на официальном сайте json:

кстати, она имеет длину 582 байта; на таких строках можно добиться гораздо большего сжатия, в этом примере 252 байт (степень сжатия 43%) на максимальных настройках. Кстати, степень сжатия в функции compress принята «средней», чтобы управлять ей используйте функцию compress2, которая последним параметром принимает дефайн типа MZ_NO_COMPRESSION, MZ_BEST_SPEED, MZ_BEST_COMPRESSION или даже MZ_UBER_COMPRESSION. Автор модуля явно не лишён юмора

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

И ещё один интересный момент, архиватор 7z с алгоритмом gzip и пресетом ultra сжал мою 183-байтовую строчку до 156 байт, а miniz (я напомню) до 134. Получается, miniz в два раза круче ultra 7z gzip!

Справедливости ради стоит сказать что существует алгоритм zopfli, который может достичь на 10% более сильного сжатия, чем стандартная реализация DEFLATE, но ему потребуется в 100 раз больше времени.

Делает он это за счёт попыток найти кратчаший путь в графе, короче он пытается по-разному разбить данные для сжатия и ищет самый оптимальный способ это сделать.

Ещё существуют программы deflopt и defluff, которые принимают результат работы DEFLATE и оптимизируют код, вытягивая ещё долю процента сжатия.

Этот алгоритм сжатия можно использовать как для сохранения данных в файл, так и для общения по сети, веб-серверы должны прожёвывать GZIP-трафик сходу и без проблем.

Вырисовывается структура правильного обмена данными с сервером: протокол верхнего уровня HTTP + транспорт JSON + сжатие GZIP.

Осталось добавить шифрование — и получится законченный протокол: удобный, текстовый, защищённый и сжатый.

Добавить комментарий

Закрыть меню