 |
Является ли gzip лучшим метод сжатия?
|
|
|
|
Как происходит сжатие в системе UNIX
Ашкеев.Д.Е
Студент КАЗАТУ, группы РЭТ “308”
Аннотация: Большие корпорации использовали алгоритмы сжатия для хранения всё увеличивающихся массивов данных, но истинное распространение алгоритмов произошло с рождением интернета в конце 80-х. Пропускная способность каналов была чрезвычайно узкой. Для сжатия данных, передаваемых по сети, были придуманы форматы ZIP, GIF и PNG. В это время многие компаний стали разрабатывать разные утилиты и смешанные алгоритмы для улучшения отрасли сжатия. В UNIX использовалась/используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).
Основная часть: gzip (сокращение от GNU Zip) — утилита сжатия и восстановления (декомпрессии) файлов, использующая алгоритм Deflate. В своей основе gzip выполняет только две функции: сжатие и распаковку одного файла; упаковка нескольких файлов в один архив невозможна.
Схема работы с архивом.tar.gz с несколькими файлами.
В этом нам поможет утилита tar. Сам по себе tar не является архиватором в привычном понимании этого слова, т.к. он самостоятельно не использует сжатие. В то же время, многие архиваторы (например, gzip или bzip2) не умеют сжимать несколько файлов, а работают только с одним файлом или входным потоком. Поэтому чаще всего эти программы используются вместе. tar создает несжатый архив, в который помещаются выбранные файлы и каталоги, при этом сохраняя некоторые их атрибуты (такие как права доступа). После этого полученный файл *.tar сжимается архиватором, например, gzip. Вот почему архивы обычно имеют расширение.tar.gz или.tar.bz2 (для архиваторов gzip и bzip2 соответственно).
При сжатии к оригинальному расширению файла добавляется суффикс.gz. Для упаковки нескольких файлов обычно их сначала архивируют (объединяют) в один файл утилитой tar, а потом этот файл сжимают с помощью gzip. Таким образом, сжатые архивы обычно имеют двойное расширение.tar.gz, либо сокращенное.tgz.
|
|
|
С другой стороны, указанная особенность дает gzip возможность работать с непрерывным потоком данных, упаковывая/распаковывая их «на лету». Это широко применяется в UNIX-системах: при помощи перенаправления потоков можно работать с упакованными файлами так же легко, как и с распакованными (распаковывая их в памяти при чтении и упаковывая при записи); многие UNIX-утилиты имеют встроенную поддержку этого механизма. В последнее время gzip активно применяется для сжатия интернет-трафика. Сейчас gzip поддерживают большинство современных браузеров.
Использование алгоритма Deflate в gzip
Алгоритм Deflate был создан на базе предшественников: LZ77 и LZ78. Deflate использует комбинацию алгоритма LZ77 и алгоритма Хаффмана.
Алгоритм LZ77
Алгоритм LZ77 заменяет повторные вхождения данных на «ссылки». Т.е. если в имеющихся данных какая-то цепочка элементов встречается более одного раза, то все последующие её вхождения заменяются «ссылками» на её первый экземпляр. Каждая такая ссылка имеет два значения: смещение и длина.
Пример:
Original text: «ServerGrove, the PHP hosting company, provides hosting solutions for PHP projects» (81 bytes)
LZ77: «ServerGrove, the PHP hosting company, p<3,32>ides<9,26>solutions for<5,52><3,35>jects» (73 bytes, assuming that each reference is 3 bytes)
Как вы могли заметить, слова «hosting» и «PHP» повторяются, поэтому во второй раз, когда подстрока найдена, она будет заменена ссылкой. Есть и другие совпадения, такие как «er», но т.к. это незначительно (в данном случае — «er» отсутствует в других словах), остается оригинальный текст.
Кодирование Хаффмана
Кодирование Хаффмана является методом кодирования с переменной длиной, которая назначает более короткие коды к более частым «символам». Проблема с переменной длиной кода, как правило в том, что нам нужен способ узнать, когда код закончился и начался новый, чтобы расшифровать его.
|
|
|
Кодирование Хаффмана решает эту проблему, создав код префикса, где ни одно кодовое слово не является префиксом другого. Пример:
>Original text: «ServerGrove»
ASCII codification: «01010011 01100101 01110010 01110110 01100101 01110010 01000111 01110010 01101111 01110110 01100101» (88 bits)
ASCII представляет собой систему кодировки символов с фиксированной длиной, так что буква «е», которая повторяется три раза, а также является наиболее часто встречаемой буквой в английском языке, имеет такой же размер как буква «G», которая появляется только один раз. Используя эту статистическую информацию, Хаффман может создать наиболее оптимизированную систему
Хаффман: «1110 00 01 10 00 01 1111 01 110 10 00» (27 bits)
Метод Хаффмана позволяет нам получить более короткие коды для «e», «r» и «v», в то время как «S» и «G» получаются длиннее.
Deflate как алгоритм, который используется в GZIP сжатии, является комбинацией обоих этих алгоритмов.
Является ли gzip лучшим метод сжатия?
Ответ — нет. Есть другие методы, которые дают более высокие показатели сжатия, но существует несколько хороших причин использовать этот.
Во-первых, даже при том что gzip не самый лучший метод сжатия, он обеспечивает хороший компромисс между скоростью и степенью сжатия. Сжатие и распаковка у gzip происходят быстро и степень сжатия на высоком уровне.
Во-вторых, нелегко внедрить новый глобальный метод сжатия данных, который смогут использовать все. Браузерам потребуется обновление, что на сегодняшний день гораздо проще за счёт автообновления. Как бы то ни было, браузеры — не единственная проблема. Chromium пытался добавить поддержку gzip2, более лучшего метода основанного на преобразовании Барроуза-Уилера, но от него пришлось отказаться, т.к. некоторые промежуточные прокси-серверы искажали данные, т.к. не могли распознать заголовки bzip2 и пытались обработать gzip контент.
gzip+HTTP
Процесс получения сжатого контента между клиентом (браузером) и сервером достаточно прост. Если у браузера есть поддержка gzip/deflate, он даёт серверу понять это благодаря заголовку “Accept-Encoding”. Тогда, сервер может выбрать — отправлять содержимое в сжатом или оригинальном виде.
|
|
|
Заключение: Как можно понять из вышеизложенных данных, UNIX система дала жизнь и поныне существующим основам сжатия, а также нашла жизнь в “серфинге” браузера, сжимая и экономя трафик. Что касается нашей темы, то сжатие в системе UNIX была основана на уже существовавших тогда алгоритмах сжатия, и как это и случается в процессе развития, была усовершенствована до определенного баланса скорости / качества сжатия.
Литература
1. С. Д. Кузнецов, Операционная система UNIX.
2. Raul Fraile, How Gzip compression works (переведен сайтом habrahabr.ru).
3. Вячеслав Голованов, Алгоритмы сжатия данных без потерь (статья размещена на сайте habrahabr.ru).
4. Sebastian Plesciuc, Huffman algorithm (переведен сайтом habrahabr.ru).
|
|
|
