Основные виды алгоритмов сжатия данных и как они работают
Дата публикации: 03.04.2017
Размер передаваемых данных является основным фактором, влияющим на «тяжесть» сайта, на его время загрузки. Все меры, обеспечивающее меньший объем передаваемых данных при сохранении объема информации или качества сайта, являются наиболее приоритетными при ускорении сайта. А методики, которые могут позволить такие меры применять, ценятся на вес золота. Сегодня мы разберемся, зачем нужно сжатие (или архивирование) данных на сайтах и как его правильно настроить.
На текущий момент существует большое количество алгоритмов сжатия (архивирования) данных, которые можно разделить на три основные группы:
Необходим сайт, мобильное приложение, услуги по SEO или контекстной рекламе? Тендерная площадка WORKSPACE поможет выбрать оптимального исполнителя. База проекта насчитывает более 10 500 агентств. Сервис работает БЕСПЛАТНО как для заказчиков, так и для исполнителей.
1
Поточные алгоритмы
К этой группе относятся алгоритмы семейств RLE (run-length encoding), LZ* и др.
При кодировании данных используется не информация о частотах символов в сообщении, а информация о последовательностях, встречавшихся ранее. Так работает, например, gzip (LZ77), bzip и compress.
2
Алгоритмы статистического (энтропийного) сжатия
Эта группа алгоритмов сжимает информацию, используя частоты, с которыми различные символы встречаются в сообщении.
К алгоритмам этой группы относятся алгоритмы арифметического и префиксного кодирования (с использованием деревьев Шеннона-Фанно, Хаффмана, секущих).
Алгоритм сжатия данных brotli использует, в том числе, кодирование Хаффмана совместно с LZ-алгоритмами.
3
Разностные алгоритмы
В отдельную группу можно выделить алгоритмы преобразования информации (включая использование словарей). Алгоритмы этой группы часто не производят непосредственного сжатия информации, но их применение значительно упрощает дальнейшее сжатие с использованием поточных и энтропийных алгоритмов. Алгоритм SDCH (VCDIFF) использует именно словари и разностное кодирование информации.
Поточные алгоритмы
Кодирование длин серий (RLE — Run-Length Encoding) — это один из самых простых и распространённых алгоритмов сжатия данных. В этом алгоритме последовательность повторяющихся символов заменяется символом и количеством его повторов.
Например, строку «ААААА», требующую для хранения 5 байт (при условии, что на хранение одного символа отводится байт), можно заменить на »5А», состоящую из двух байт.
Очевидно, что этот алгоритм тем эффективнее, чем длиннее серия повторов и чем больше таких повторов в исходном (кодируемом) тексте.
Основным недостатком этого алгоритма является его крайне низкая эффективность на последовательностях неповторяющихся символов.
Например, если рассмотреть последовательность «АБАБАБ» (6 байт), то после применения алгоритма RLE она превратится в »1А1Б1А1Б1А1Б» (12 байт). Для решения проблемы неповторяющихся символов существуют различные методы.
Алгоритмы LZ (название происходит от авторов Абрахама Лемпэла (Abraham Lempel) и Якоба Зива (Jacob Ziv)), в отличие от алгоритмов RLE, кодирует не количество повторов символов, а встречавшиеся ранее последовательности символов.
Во время работы рассматриваемых алгоритмов динамически создаётся таблица со списком уже встречавшихся последовательностей и соответствующих им кодов. Эту таблицу часто называют словарём, а соответствующую группу алгоритмов называют поточно-словарными.
К плюсам этой группы относится их большая, по сравнению, с RLE эффективность сжатия.
Наиболее известной реализацией этих алгоритмов является gzip-сжатие данных. Ранее различали два варианта использования в Сети: gzip и deflate. Единственное отличие между ними заключается в отправке (gzip) или не отправке (deflate) начала потока данных (файла), в котором описано, что это gzip-сжатые данные.
Для упрощения работы gzip-сжатия (включая использование статического сжатия) от поддержки deflate сейчас почти везде отказались.
Как настроить gzip на сайте
При настройке gzip для сжатия страниц сайта необходимо иметь в виду оптимальную степень сжатия, после которой дальнейшее расходование ресурсов процессора становится неэффективным.
При росте степени сжатия, как видно из графика ниже, процессорные издержки растут линейно (чем больше степень, тем кратно больше времени нужно на сжатие).
Но с ростом процессорных издержек фактическая эффективность gzip-сжатия растет по-другому. Ниже на графике хорошо видно, что только до 5 степени сжатия эффективность растет линейно (пропорционально), а после это существенно замедляет свой рост.
Если процессорные ресурсы у вас в избытке, то можно выставить и 7, и 9 степень сжатия, но изменений между 7 и 9 степенью почти нет (это доли процента).
Для nginx gzip-сжатие включается простыми директивами:
gzip on;
gzip_comp_level 7;
gzip_vary on;
gzip_types text/css text/javascript application/javascript;
Директива gzip_vary позволит передать соответствующий заголовок для кэширующих прокси с указанием особенностей кэширования сжатых ресурсов.
А gzip_types укажет, для каких типов файлов необходимо применять сжатие на сервере.
Статическое сжатие nginx
Для экономии ресурсов процессора вы можете использовать заранее сжатые файлы в формате gzip, имеющие дополнительное расширение .gz (например: main.css.gz будет архивом файла main.css).
При сжатии таких файлов можно использовать максимальную степень сжатия: они будут сжиматься только 1 раз, в дальнейшем веб-сервер будет использовать уже сжатую версию вместо обычной для тех пользователей, которые поддерживают сжатие.
Для подключения статического сжатия в nginx нужна поддержка модуля gzip_static, соответствующая директива в конфигурации выглядят так:
gzip_static on;
Сжатие в Apache
Apache использует модуль mod_deflate для отгрузки сжатых версий файлов. Его можно включить следующим образом (если он присутствует на сервере):
AddOutputFilterByType DEFLATE text/html text/css text/javascript
AddOutputFilterByType DEFLATE application/javascript
DeflateCompressionLevel 7
Сжатие в IIS
Для включения сжатия в веб-сервере IIS необходимо в диспетчере служб IIS зайти в свойства элемента «Веб узлы» и перейти на вкладку «Службы». Также сжатие можно включить через web.config при помощи следующей конфигурации:
Проверка сжатия
Сжатие данных на сайте можно проверить большим количеством способов. Первый из них — простой тест на gzip.
Второй — более общая проверка сайта на показатели скорости при помощи Google PageSpeed Insights. При отсутствия сжатия на сайте вы получите соответствующее уведомление (или список файлов, для которых сжатие не включено).
Zopfli
Zopfli является инициативой инженеров Google по созданию более эффективного алгоритма LZ-сжатия, который бы работал лучше существующих аналогов и был обратно совместим с gzip-распаковкой.
Для этого в дополнение к потоковым методам сжатия (с максимально допустимым окном кодирования) используются энтропийные методы (кодирование Хаффмана и поиск минимального представления), что в совокупности дает выигрыш в размере 5–7% на реальных данных.
Это можно проиллюстрировать на следующем примере. Если у нас есть строка «CCCCDDDABABABCCCCABABAB», то ее LZ-представление будет выглядеть примерно следующим образом: C{4,1}D{3,4}AB{4,7}C{4,11}AB{4,15}.
Где в скобках указаны пары длина-начало кодируемого сегмента. При этом стандартный gzip создаст словарь по мере нахождения совпадающих подстрок: в словаре C будет обозначено в битах 1, D — 01, AB — 001.
Алгоритм zopfli пересортирует словарь по частоте вхождения подстрок, и обозначит в битах C — 1, AB — 01, D — 001.
Таким образом, на все указанное выше представление строки удастся сэкономить 1 бит при использовании zopfli (те самые 5–7% от «стандартного» размера).
Платой за более высокую степень сжатия (чем gzip-9) является крайне медленная работа алгоритма (приходится строить полное частотное дерево сжимаемой информации, что является трудоемкой процедурой).
Zopfli работает (в зависимости от настроек) в 30–100 раз медленнее gzip. Это ограничивает область его применения только статическим сжатием.
Как применить zopfli
Поскольку сжатые zopfli файлы можно распаковать как обычные gzip-архивы (ведь они таковыми и являются — наиболее оптимальным представлением gzip-архива для заданного файла), то его можно использовать для создания готовых gz-файлов (сжатых версий) CSS и JavaScript (а случае полностью статического сайта — и HTML) ресурсов.
Zopfli уже интегрирован в большинство пакетов, для сборки его на вашем сервере достаточно выполнить следующие команды:
git clone https://code.google.com/p/zopfli/
cd zopfli
make
chmod +x zopfli
./zopfli -c >
Для применения статического сжатия нужно не забыть его включить в вашем веб-сервере. Для nginx это одна директива (при наличии модуля gzip_static):
gzip_static on;
Brotli
После разработки более эффективной версии gzip инженеры из Google не остановились. Следующим шагом была создание отдельного алгоритма сжатия данных, который сжимал данные лучше, но не сильно проигрывал в скорости gzip.
Таким алгоритмом стал brotli. В нем сложились все три блока методов сжатия: поточное, энтропийное и словарное.
Brotli использует собственный словарь (составляющий 2/3 от спецификации алгоритма) из почти 100 тысяч различных фраз и кусочков слов, наиболее часто встречающихся в Сети.
Этот словарь применяется как основа для поточного сжатия данных (как в LZ-кодировании), но не исключает добавление новых строк, найденных в сжимаемом тексте. И, конечно, brotli использует энтропийное сжатие для наименьшего представления полученного архива.
Фактически, в браузеры, поддерживающие brotli, уже встроен почти весь словарь, используемый при сжатии данных, и он в архиве не передается. За счет этого и достигается значительный выигрыш в размере архивов.
Максимальная степень сжатия — 11 — позволяет добиться на 25% меньшего размера файла по сравнению с gzip-9, и на 20% — по сравнению с zopfli.
По времени сжатия brotli примерно сравним с zopfli, но с большим отличием: малая степень сжатия по скорости чуть-чуть уступает gzip, а степень сжатия при равной скорости существенно больше. Максимальная степень сжатия медленнее gzip-9 примерно в 80–100 раз.
Все браузеры на основе Chrome, Firefox и Edge 15 уже поддерживают brotli (но делают это только для SSL-соединений), на уровне HTTP-заголовков это выглядит так:
Accept-Encoding: br
Как использовать brotli
Для включения в nginx поддержки brotli необходимо собрать, как минимум, модуль brotli_static и включить его в конфигурации:
brotli_static on;
В таком режиме nginx будет при получении от браузера соответствующего заголовка (что brotli поддерживается) проверять, есть ли файл с расширением .br рядом с запрашиваемым — и отдавать его как сжатый brotli-архив.
Для создания самих brotli-архивов нужно будет либо установить из репозитория, либо отдельно собрать утилиты bro:
git clone https://github.com/badger/libbrotli
cd libbrotli
autoreconf -i
make install
git clone https://github.com/google/brotli
cd brotli
./configure
make
chmod +x bro
./bro —quality 11 —input —output
Можно дополнительно включить brotli-сжатие «на лету», установив модуль nginx brotli, но это может привести к дополнительным издержкам CPU при отгрузке страниц пользователям и ботам.
Для подключения brotli для IIS необходимо установить отдельный модуль: IIS Brotli, а для Apache есть mod_brotli, который настраивается аналогичным образом:
LoadModule brotli_module modules/mod_brotli.so
AddOutputFilterByType BROTLI text/html text/plain text/css text/xml
BrotliCompressionLevel 10
BrotliWindowSize 22
SDCH
От «швейцарского ножа» сжатия в Сети (brotli) переходим к более узкому инструменту — VCDIFF, или более известному как SDCH-сжатие.
VCDIFF предполагает использование заранее определенного словаря (который должен быть передан пользователю) и реализуется в браузерах через протокол SDCH (который является просто «оберткой» поверх VCDIFF контейнеров с данными).
Плюсом SDCH является то, что это альтернативный вариант сжатия, который можно использовать в дополнение к gzip или brotli: запаковать страницу при помощи SDCH-словаря, а запакованную версию дополнительно сжать «на лету», браузеры так понимают.
Минусом является достаточно сложный подготовительный процесс: необходимо создать словарь на основе нескольких страниц сайта, который будет содержать наиболее часто используемые блоки (чтобы передать их один раз) и не будет слишком большим (иначе будет «дешевле» передать сами страницы без SDCH-сжатия). Ниже показан примерный выигрыш в размере при использовании SDCH.
Очевидно, что если пользователь просматривает более 3 страниц на сайте — то выигрыш от использования этого алгоритма будет. Если меньше — то можно ограничиться стандартными механизмами сжатия.
Детально механизм подключения описан в блоге Айри, кратко алгоритм выглядит следующим образом:
Нужно установить пакет femtozip для сборки словаря из наиболее характерных страниц сайта.
Нужно установить VCDIFF библиотеки на сервер для использования словаря при кодировании «на лету».
Нужно установить модуль nginx sdch для кодирования «на лету».
Нужно собрать словарь при помощи femtozip и дополнительно сжать его zopfli или brotli.
Нужно включить sdch-сжатие «на лету» для сайта в конфигурации nginx на базе собранного словаря.
В качестве заключения
Gzip-сжатие является самым распространенным способом сократить размер передаваемой в Сети информации и поддерживается почти всеми серверами и браузерами.
Включить сжатие на сайте очень просто: достаточно добавить в конфигурацию сайта несколько инструкций в зависимости от вашего веб-сервера.
Оптимальной степенью сжатия будет 5 или 7 (в зависимости от ваших процессорных ресурсов).
Проверить, использует ли ваш сайт сжатие, можно в течение минуты любым из указанных выше инструментов.
Все рассмотренные «продвинутые» механизмы сжатия данных в Сети являются проверенными временем практиками (реализованными в соответствующих модулях и библиотеках) и могут быть использованы в рабочем веб-окружении прямо сегодня.
При дополнительной настройке веб-сервера возможно сокращение размера передаваемых текстовых данных еще на 25–70% (brotli / scdh), что может быть серьезным преимуществом для новостных порталов и высоконагруженных проектов, где на счету каждые 100 мс времени загрузки сайта. Даже обычное использование zopfli для сжатия статических файлов уже даст выигрыш в 5–7%, которые могут помочь вам сделать сайт быстрее.
По материалам Searchengines.ru
