Ниже приводится популярное изложение принципов сжатия информации. Рекомендую также несколько ссылок по описанию арифметических методов сжатия:

В цифровых тисках

Сергей Зелинский

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

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

Кратко коснемся терминологии. Принято различать архивацию и упаковку (компрессию, сжатие) данных. В первом случае речь идет о слиянии нескольких файлов и даже каталогов в единый файл - архив, во втором - о сокращении объема исходных файлов путем устранения избыточности. Как правило, современные программные архиваторы обеспечивают также сжатие данных, являясь еще и упаковщиками.

Два типа сжатия

Все алгоритмы (методы) сжатия данных можно разделить на два больших типа - сжатие без потерь и с потерями. Первый тип алгоритмов используется в тех случаях, когда необходимо полное совпадение исходных данных и восстановленных после сжатия/распаковки (компрессии/декомпрессии), например, в случае двоичной информации, текстов и т. д. На алгоритмах этой группы основываются широко используемые программы-архиваторы и протоколы передачи данных в компьютерных сетях.

Второй тип алгоритмов сжатия используется в случаях, когда пользователю не требуется полного совпадения входной и обработанной информации. Как правило, такие алгоритмы используются для уменьшения избыточности файлов, содержащих изображения и звуки, и основываются на нечувствительности человеческих органов восприятия к небольшим искажениям в представляемой информации. Сжатие данных с потерей части информации обеспечивает наивысшую степень и скорость сжатия данных. Примерами таких алгоритмов являются форматы JPEG и MPEG, обеспечивающие 20-кратную степень сжатия.

Данный сравнительный тест посвящен приложениям, использующим методы сжатия без потери информации.

Математическая теория сжатия

Теоретические основы сжатия информации были заложены в конце 40-х годов прошлого века Клодом Шенноном. В его статье "Математическая теория коммуникаций" впервые было сформулировано положение о том, что энтропия любого блока информации равна вероятности его появления во всем массиве данных. Соответственно, наиболее часто повторяющиеся блоки являются и наиболее "избыточными" и могут быть представлены в более сжатом виде.

Общая формула Шеннона, позволяющая найти количество информации в случайном сообщении фиксированного алфавита, выглядит так:
H = P1*log2(1/P1) + P2*log2(1/P2) + ... + Pn*log2(1/Pn)
где H - количество бит информации в одном символе сообщения, P1, ..., Pn - вероятности появления символов X1, ..., Xn в тексте сообщения.

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

Принцип работы архиваторов основан на поиске в файле избыточной информации и последующем ее кодировании (генерировании кода), чтобы получить минимальный объем хранимых данных. Целью процесса сжатия является получение более компактного выходного потока данных из некоторого изначально некомпактного входного потока с помощью соответствующего преобразования. В настоящее время известно множество различных алгоритмов сжатия информации, которые условно делятся на четыре группы (повторяющихся последовательностей, вероятностных, арифметических и словарных).

Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является 1 бит. Основными техническими характеристиками процессов сжатия являются степень сжатия (отношение объемов исходного и результирующего потоков), скорость сжатия (время, затрачиваемое на сжатие некоторого объема информации) и качество сжатия (насколько сильно упакован выходной поток).

От простого к сложному

Метод повторяющихся последовательностей (Run-Length Encoding - RLE) является наиболее простым из известных алгоритмов сжатия информации и используется в основном для сжатия графических файлов. Классический вариант этого метода предусматривает замену последовательности повторяющихся символов на строку, содержащую сам этот символ, и число повторов этого символа.

Например, строка АААББББВВВВВГГ будет записана в виде: 3А4Б5В2Г. В рассмотренном примере содержится 14 символов. Как известно, для представления одного символа требуется 1 Байт, или 8 бит. Для представления всей последовательности требуется 14*8=112 бит, а после сжатия нужно лишь 8*8=64 бита, т. е. даже на таком маленьком массиве данных объем уменьшается почти вдвое. В то же время применение этого метода для сжатия текстовых или исполняемых (EXE, COM) файлов оказывается неэффективным, а общим недостатком RLE является достаточно низкая степень сжатия.

Строим дерево

К вероятностным методам относятся алгоритмы Шеннона-Фено и Хаффмана. В их основе лежит идея построения дерева, на ветвях которого положение каждого символа определяется частотой его появления в файле. Каждому символу присваивается код, длина которого обратно пропорциональна частоте появления символа в файле.

Код строится следующим образом. После подсчета всех символов, встречающихся в файле, они вписываются в таблицу в порядке убывания частот их появления. Например, имеется строка символов, в которой используются 6 первых букв русского алфавита: А, Б, В, Г, Д и Е. На первом этапе она разбивается на две части так, чтобы суммы частот появления символов в них были приблизительно равны: А(8)-Б(2)-В(3) и Г(4)-Д(1)-Е(6). Для левого подмножества каждому символу приписывается "0", для правого - "1". Затем каждое из этих двух подмножеств делится пополам, и процедура повторяется для каждого из подмножеств. В конечном итоге в каждом подмножестве останется по одному символу.

В результате каждый из символов получает свой код ("А" - 00, "Б" - 011, "В" - 010 и т. д.), по которому к нему можно добраться с вершины дерева. При этом, чем чаще встречается символ в файле, тем ближе он к вершине дерева и тем короче его адресный код.

Метод Хаффмана очень похож на метод Шеннона-Фено, но создание дерева в нем начинается не с вершины, а с корня. Это метод сжатия, который уменьшает среднюю длину кода для символов.

Код Хаффмана может быть построен по следующему алгоритму. Сначала выписываются в строку все символы алфавита в порядке возрастания или убывания частоты (вероятности) их появления в сообщении. Для нашего примера это будет последовательность: А(8)-Е(6)-Г(4)-В(3)-Б(2)-Д(1).

Последовательно объединяются два символа с наименьшими частотами появления (в данном случае "Б" и "Д") в новый составной символ, вероятность появления которого полагается равной сумме частот составляющих его символов. Присваивая ветвям дерева "0" и "1", так же, как и в предыдущем методе, поднимаемся к вершине, получая код для каждого символа. В результате формируется дерево, каждый узел которого имеет суммарную вероятность всех узлов, находящихся ниже него. Затем отcлеживается путь к каждой ветви и помечает направление к каждому узлу (например, направо - "1", налево - "0").

Существуют две разновидности вероятностных методов сжатия данных, различающихся способом определения вероятности появления каждого символа в файле - статические и аддитивные. Первые используют таблицу частот появления символов в файле, рассчитываемую перед началом процесса сжатия. В аддитивных же методах частота появления символов меняется, и по мере считывания нового информационного блока из файла происходит перерасчет начальных значений частот.

Арифметические алгоритмы

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

Пpи аpифметическом кодиpовании текст пpедставляется вещественными числами в интеpвале [0; 1]. По меpе кодиpования текста, отобpажающий его интеpвал уменьшается, а количество бит для его пpедставления возpастает. Последующие символы текста сокpащают величину интеpвала исходя из значений их веpоятностей. Более веpоятные символы делают это в меньшей степени, чем менее веpоятные, и, следовательно, добавляют меньше бит к pезультату.

В качестве примера рассмотрим кодирование двух символов "А" и "Б" с вероятностями 0,666 и 0,333. Кодируя сообщение, для символа "А" выбираем интервал [0; 0,666], для символа "Б" - [0,666; 1]. Для двух символов получим: "АА" - [0; 0,444], "АБ" - [0,444; 0,666], "БА" - [0,666; 0,888] и для "ББ" - [0,888; 1].

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

Метод словарей

Этот алгоритм был впервые описан в работах Абрахама Лемпеля и Якоба Зива (двухступенчатое кодирование). На сегодняшний день этот алгоритм, известный как LZ-алгоритм, и его модификации получили наиболее широкое распространение по сравнению с другими алгоритмами сжатия. В его основе лежит идея замены наиболее часто встречающихся последовательностей символов (строк) в файле ссылками на образцы, хранящиеся в специально создаваемом словаре. Так, создав словарь, содержащий 65 536 наиболее употребительных слов, можно представить текстовые файлы в виде последовательности 16-битовых ссылок на место данного слова в словаре.

Например, если программа сжатия уже имеет в словаре последовательность "АБВ" и обнаружит последовательность "АБВА", то она вначале занесет в выходной файл код из словаря для "АБВ", затем для символа "A", после чего последовательность "АБВА" будет добавлена в словарь. Если же она позже встретит "АБВАБ", то выведет код для "АБВА", затем код для символа "Б" и добавит "АБВАБ" в словарь. Когда программа встречает последовательность из словаря, она выдает код и добавляет новую запись, которая на один байт длиннее. То есть каждый раз при повторении последовательности словарь будет расти за счет включения продолжения этой последовательности.

На практике приходится оперировать таблицами, заполняемыми по мере сканирования файла. При этом уже просмотренная часть файла используется как словарь. Алгоритм основывается на движении по потоку данных скользящего окна, состоящего из двух частей: большей по объему, в которой содержатся уже обработанные данные, и меньшей, в которую по мере просмотра помещается вновь считанная информация. Во время считывания каждой новой порции данных происходит проверка, и если оказывается, что такая строка уже есть в словаре, то она заменяется ссылкой.

Упомянем и об алгоритме Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW), который отличают невысокие требования к памяти и более низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Этот алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые коды в конец словаря. Он преобразует поток символов на входе в поток индексов ячеек словаря на выходе.

При размере словаря в 4096 входов можно передавать 12 бит на каждый индекс. Каждая распознанная цепочка добавляет в словарь один код. При переполнении словаря упаковщик может либо прекратить его заполнение, либо очистить (полностью или частично). При реализации этого алгоритма следует учесть, что любой код словаря, кроме самых первых, содержащих односимвольные последовательности, хранит копию некоторого другого кода, к которой в конец приписан один символ.

Некоторые разновидности LZ-алгоритма LZ77. Алгоритм, в котором чередуются указатели и символы. Указатели ссылаются на подстроку, расположенную в предыдущих N символах. LZB. Аналогичен алгоритму LZSS, кроме кодирования указателей. LZC. Алгоритм, реализованный программой compress в UNIX-системах. LZFG. Алгоритм, в котором указатели выбирают узел в дереве поиска. Строки в дереве выбираются из текущего окна. LZH. Алгоритм, аналогичный LZSS, на втором этапе которого кодирование указателей осуществляется по методу Хаффмана. LZJ. В результате работы этого алгоритма генерируются только указатели.Указатели означают подстроку в любом месте предыдущего текста. LZMW. Алгоритм, аналогичный LZT, но фразы строятся путем объединения предыдущих фраз. LZR. На выходе алгоритма чередуются указатели и символы. Указатели означают строку, расположенную в любом месте предыдущего текста. LZSS. Алгоритм, в котором указатели и символы разделяются битом флага. Указатели ссылаются на подстроки в предыдущих N символах. LZT. Аналогичен LZC, но с усовершенствованным обновлением словаря. LZW. На выходе этого алгоритма имеются только указатели фиксированного объема, ссылающиеся на предварительно выделенные подстроки.

Особенности сжатия графики

Напомним, что растровые изображения представляют собой двумерный массив чисел - пикселей, а изображения можно подразделить на две группы: с палитрой и без нее. У первых в пикселе хранится число - индекс в некотором одномерном векторе цветов, называемом палитрой (из 16 и 256 цветов).

Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого. При использовании некой системы цветопредставления каждый пиксель является структурой, полями которой являются компоненты цвета (например, RGB и CMYK).

На заре компьютерной эры для сжатия графики применялись традиционные алгоритмы, рассмотренные выше. С появлением новых типов изображений эти алгоритмы утратили эффективность. Многие изображения практически не сжимались, хотя обладали явной избыточностью. Тогда и появились алгоритмы с потерей информации. Как правило, в них можно задавать коэффициент сжатия (т. е. степень потерь качества).

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

Фрактальное сжатие

Так называемые фрактальные алгоритмы обеспечивают степень сжатия изображения до 1:2000 (формат FIF). Кроме того, при разархивации изображение можно масштабировать. Уникальность этих алгоритмов в том, что изображение не дробится на квадраты и учитывается не близость цветов в локальной области, а подобие разных по размеру областей изображения.

Фрактальные алгоритмы ориентированы на полноцветные изображения и изображения в градациях серого. Они требуют огромных вычислительных мощностей при архивации, зато распаковка менее ресурсоемка, чем JPEG.

Не только алгоритм

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

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

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

Многие популярные архивные форматы (ZIP, LZH, ARJ, ARC, ICE.) появились во времена DOS. Сегодня же, в эпоху Windows, из этих старожилов остались только ZIP, ARJ и LZH. В то же время появился новый кроссплатформный формат JAR (Java ARchive), который был создан для пересылки многокомпонентных Java-апплетов. Еще один формат - CAB от Microsoft применяется для архивирования дистрибутивов ПО.

Во многих случаях удачным решением проблемы совместимости является создание архивов в виде самораспаковывающихся программ (EXE-файлов). Правда, многие программы-архиваторы способны создавать EXE-архивы лишь на базе своего "родного" формата, что не всегда удобно (невозможно без специальных инструментов выборочно извлекать файлы из архива).

Итак, несмотря на то что цена мегабайта дискового пространства невысока и уменьшается с каждым годом, потребность в архивации не исчезает. Неудивительно - сжатие данных необходимо не только для экономии места на локальном дисковом носителе, но и для передачи информации. А при выборе архиватора пользователи должны руководствоваться его универсальностью и надежностью, не забывая о качестве и скорости сжатия.