Обзор методов сжатия данных


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Обзор методов сжатия данных

Методы сжатия данных имеют достаточно длинную историю развития, которая началась задолго до появления первого компьютера. В этой статье будет произведена попытка дать краткий обзор основных теорий, концепций идей и их реализаций, не претендующий, однако, на абсолютную полноту. Более подробные сведения можно найти, например, в Кричевский Р.Е. [1989], Рябко Б.Я. [1980], Witten I.H. [1987], Rissanen J. [1981], Huffman D.A.[1952], Gallager R.G. [1978], Knuth D.E. [1985], Vitter J.S. [1986] и др.

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

- степень сжатия (compress rating) или отношение (ratio) объемов исходного и результирующего потоков;

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

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

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

Под необратимым сжатием подразумевают такое преобразование входного потока данных, при котором выходной поток, основанный на определенном формате информации, представляет, с некоторой точки зрения, достаточно похожий по внешним характеристикам на входной поток объект, однако отличается от него объемом. Степень сходства входного и выходного потоков определяется степенью соответствия некоторых свойств объекта (т.е. сжатой и несжатой информации, в соответствии с некоторым определенным форматом данных), представляемого данным потоком информации. Такие подходы и алгоритмы используются для сжатия, например, данных растровых графических файлов с низкой степенью повторяемости байтов в потоке. При таком подходе используется свойство структуры формата графического файла и возможность представить графическую картинку приблизительно схожую по качеству отображения (для восприятия человеческим глазом) несколькими (а точнее n) способами. Поэтому, кроме степени или величины сжатия, в таких алгоритмах возникает понятие качества, т.к. исходное изображение в процессе сжатия изменяется, то под качеством можно понимать степень соответствия исходного и результирующего изображения, оцениваемая субъективно, исходя из формата информации. Для графических файлов такое соответствие определяется визуально, хотя имеются и соответствующие интеллектуальные алгоритмы и программы. Необратимое сжатие невозможно применять в областях, в которых необходимо иметь точное соответствие информационной структуры входного и выходного потоков. Данный подход реализован в популярных форматах представления видео и фото информации, известных как JPEG и JFIF алгоритмы и JPG и JIF форматы файлов.

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

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

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

Сжатие способом кодирования серий

Наиболее известный простой подход и алгоритм сжатия информации обратимым путем - это кодирование серий последовательностей (Run Length Encoding - RLE). Суть методов данного подхода состоит в замене цепочек или серий повторяющихся байтов или их последовательностей на один кодирующий байт и счетчик числа их повторений. Проблема всех аналогичных методов заключается лишь в определении способа, при помощи которого распаковывающий алгоритм мог бы отличить в результирующем потоке байтов кодированную серию от других - некодированных последовательностей байтов. Решение проблемы достигается обычно простановкой меток в начале кодированных цепочек. Такими метками могут быть, например, характерные значения битов в первом байте кодированной серии, значения первого байта кодированной серии и т.п. Данные методы, как правило, достаточно эффективны для сжатия растровых графических изображений (BMP, PCX, TIF, GIF), т.к. последние содержат достаточно много длинных серий повторяющихся последовательностей байтов. Недостатком метода RLE является достаточно низкая степень сжатия или стоимость кодирования файлов с малым числом серий и, что еще хуже - с малым числом повторяющихся байтов в сериях.

Сжатие без применения метода RLE

Процесс сжатия данных без применения метода RLE можно разбить на два этапа: моделирование (modelling) и, собственно, кодирование (encoding). Эти процессы и их реализующие алгоритмы достаточно независимы и разноплановы.

Процесс кодирования и его методы

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

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

Второй метод - метод адаптивного кодирования (adaptive coder method). Его общий принцип состоит в том, чтобы менять схему кодирования в зависимости от характера изменений входного потока. Такой подход имеет однопроходный алгоритм и не требует сохранения информации об использованном кодировании в явном виде. Адаптивное кодирование может дать большую степень сжатия, по сравнению со статическим, поскольку более полно учитываются изменения частот входного потока. Данный метод известен как динамическое кодирование Хаффмена [Huffman], [Gallager], [Knuth], [Vitter].

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

Пример:

Пусть входной алфавит состоит из четырех символов: a, b, c, d, частоты которых в входном потоке равны, соответственно, 1/2, 1/4, 1/8, 1/8. Кодирование Хаффмена для этого алфавита задается следующей таблицей:

Например, кодом цепочки abaaacb, представленной на входе как 00 01 00 00 00 10 01, будет 0 10 0 0 0 110 10, соответственно - 14 бит на входе дали 11 бит на выходе. Кодирование по Хаффмену обычно строится и хранится в виде двоичного дерева, в "листьях" которого находятся символы, а на "ветвях" - цифры 0 или 1. Тогда уникальным кодом символа является путь от корня дерева к этому символу, по которому все 0 и 1 "собираются" в одну уникальную последовательность.

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

Методы Хаффмена дают достаточно высокую скорость и умеренно хорошее качество сжатия. Эти алгоритмы давно известны и широко применяется как в программных (всевозможные компрессоры, архиваторы и программы резервного копирования файлов и дисков), так и в аппаратных (системы сжатия "прошитые" в модемы и факсы, сканеры) реализациях.

Однако, кодирование Хаффмена имеет минимальную избыточность при условии, что каждый символ кодируется в алфавите кода символа отдельной цепочкой из двух бит - {0, 1}. Основным же недостатком данного метода является зависимость степени сжатия от близости вероятностей символов к 2 в некоторой отрицательной степени, что связано с тем, что каждый символ кодируется целым числом бит. Так при кодировании потока с двухсимвольным алфавитом сжатие всегда отсутствует, т.к. несмотря на различные вероятности появления символов во входном потоке алгоритм фактически сводит их до 1/2.

Данная проблема, как правило, решается путем введения в алфавит входного потока новых символов вида "ab", "abc",. . . и т.п., где a, b, c - символы первичного исходного алфавита. Такой процесс называется сегментацией или блокировкой входного потока. Однако, сегментация не позволяет полностью избавиться от потерь в сжатии (они лишь уменьшаются пропорционально размеру блока), но приводит к резкому росту размеров дерева кодирования, и, соответственно, длине кода символов вторичных алфавитов. Так, если, например, символами входного алфавита являются байты со значениями от 0 до 255, то при блокировании по два символа мы получаем 65536 символов (различных комбинаций) и столько же листьев дерева кодирования, а при блокировании по три - 16777216! Конечно, при таком усложнении, соответственно возрастут требования и к памяти и ко времени построения дерева, а при адаптивном кодировании - и ко времени обновления дерева, что приведет к резкому увеличению времени сжатия. Напротив, в среднем, потери составят 1/2 бита на символ при отсутствии сегментации, и 1/4 или 1/6 бита соответственно при ее наличии, для блоков длиной 2 и 3 бита.

Арифметическое кодирование

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

Предполагаемая требуемая последовательность символов, при сжатии методом арифметического кодирования, рассматривается как некоторая двоичная дробь из интервала [0, 1). Результат сжатия представляется, как последовательность двоичных цифр из записи этой дроби. Идея метода состоит в следующем: исходный текст рассматривается как запись этой дроби, где каждый входной символ является "цифрой" с весом, пропорциональным вероятности его появления. Этим объясняется интервал, соответствующий минимальной и максимальной вероятностям появления символа в потоке. Поясним работу метода на примере:

Пусть алфавит состоит из двух символов: a и b с вероятностями соответственно 3/4 и 1/4. К ак уже говорилось выше, кодирование Хаффмена не может упаковывать слова в данном алфавите, т.к. не справляется без сегментации с двухсимвольным алфавитом.

Рассмотрим наш интервал вероятностей [0, 1). Разобьем его на части, длина которых пропорциональна вероятностям символов. В нашем случае это [0, 3/4) и [3/4,1). Суть алгоритма в следующем: каждому слову во входном алфавите соответствует некоторый подинтервал из интервала [0, 1) а пустому слову соответствует весь интервал [0, 1). После получения каждого следующего символа интервал уменьшается с выбором той его части, которая соответствует новому символу. Кодом цепочки является интервал, выделенный после обработки всех ее символов, точнее, двоичная запись любой точки из этого интервала, а длина полученного интервала пропорциональна вероятности появления кодируемой цепочки.

Применим данный алгоритм для цепочки "aaba":

В качестве кода можно взять любое число из интервала, полученного на шаге 4, например, 0.1.

Алгоритм декодирования работает синхронно с кодирующим: начав с интервала [0, 1), он последовательно определяет символы входной цепочки. В частности, в нашем случае он вначале разделит (пропорционально частотам символов) интервал [0, 1) на [0, 0.11) и [0.11, 1). Поскольку число 0.0111 (код цепочки "aaba") находится в первом из них, можно получить первый символ: "a". Затем делим первый подинтервал [0, 0.11) на [0, 0.1001) и [0.1001, 0.1100) (пропорционально частотам символов). Опять выбираем первый, так как 0 " 0.0111 " 0.1001. Продолжая этот процесс, мы однозначно декодируем все четыре символа. Для того, чтобы декодирующий алгоритм мог определить конец цепочки, мы можем либо передавать ее длину отдельно, либо добавить к алфавиту дополнительный уникальный символ - "конец цепочки".

При разработке этого метода возникают две проблемы: во-первых, необходима арифметика с плавающей точкой, теоретически, неограниченной точности, и, во-вторых, - результат кодирования становится известен лишь при окончании входного потока. Однако, дальнейшие исследования показывают [Rubin], что можно практически без потерь обойтись целочисленной арифметикой небольшой точности (16-32 разряда), а также добиться инкрементальной работы алгоритма: цифры кода могут выдаваться последовательно по мере чтения входного потока при ограничении числа символов входной цепочки каким либо разумным числом.

Модели входного потока

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

Возможны различные подходы к этой проблеме: простейший из них - сбор статистики появления каждого символа независимо от других (моделирование источником Бернулли, при котором вероятность появления последующего символа не зависит от того, какие символы встретились перед ним). Возможно, также и использование марковских моделей: сбор статистики появления каждого символа в которых производится с учетом некоторого количества предыдущих появлявшихся символов (в марковском источнике первого порядка вероятность появления символа зависит только от одного последнего символа, второго - от двух и т. д.). Марковские модели могут давать более точную картину источника, однако число состояний в них больше, соответственно большим будет объем хранимых таблиц частот. Кроме того, при использовании кодирования Хаффмена они могут даже ухудшить качество сжатия, поскольку порождаемые ими вероятности обычно хуже приближаются степенями 1/2.

Кодирование сортировкой

Здесь нельзя не упомянуть простой и достаточно эффективный метод кодирования источника с неизвестным распределением частот, известный как сжатие при помощи "стопки книг" или как сжатие сортировкой или хешированием. Метод был впервые открыт и исследован Рябко в 1980г., а затем переоткрыт Бентли, Слейтером, Тарьяном и Веи в 1986г. Идея метода состоит в следующем: пусть алфавит источника состоит из N символов с номерами 1, 2,..., N. Кодирующий алгоритм сохраняет последовательность символов, представляющую собой некоторую перестановку символов в последовательности первичного входного алфавита. При поступлении на вход некоторого символа c, имеющего в этой переставленной последовательности номер i, кодирующий алгоритм записывает код этого символа (например, монотонный код). Затем поступивший символ переставляется в начало последовательности и номера всех символов, стоящих перед c, увеличиваются на 1. Таким образом, наиболее часто встречающиеся символы будут переходить в начало списка и иметь более короткие коды, что в свою очередь снизит объем выходного потока при их записи в качестве символов выходного потока.

Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

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

В простейшем случае для кодирования в качестве входного алфавита можно использовать именно эти символы (байты) входного потока. Именно так работает метод squashing программы PKPAK (использовано статическое кодирование Хаффмена и двухпроходный алгоритм). Степень сжатия при этом относительно невелика - для текстовых файлов порядка 50%. Гораздо большей степени сжатия можно добиться при выделении из входного потока повторяющихся цепочек - блоков и кодирования ссылок на эти цепочки с построением хеш таблиц от первого до n-го уровня.

Метод, о котором и пойдет речь, принадлежит Лемпелю и Зиву, и обычно называется LZ-compression. Суть его состоит в следующем: упаковщик постоянно хранит некоторое количество последних обработанных символов в буфере. По мере обработки входного потока вновь поступившие символы попадают в конец буфера, сдвигая предшествующие символы и вытесняя самые старые. Размеры этого буфера, называемого также скользящим словарем (sliding dictionary), варьируются в разных реализациях кодирующих систем. Экспериментальным путем установлено, что программа LHArc использует 4-килобайтный буфер, LHA и PkZip - 8-ми, а ARJ - 16-килобайтный.

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

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

Таким образом, алгоритм Лемпеля-Зива преобразует один поток исходных символов в два параллельных потока длин и индексов в таблице (length + distance). Очевидно, что эти потоки являются потоками символов с двумя новыми алфавитами, и к ним можно применить один из упоминавшихся выше методов (RLE, кодирование Хаффмена или арифметическое кодирование).

Так мы приходим к схеме двухступенчатого кодирования - наиболее эффективной из практически используемых в настоящее время. При реализации этого метода необходимо добиться согласованного вывода обоих потоков в один файл. Эта проблема обычно решается путем поочередной записи кодов символов из обоих потоков.

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)

Данный алгоритм отличают высокая скорость работы как при упаковке, так и при распаковке, достаточно скромные требования к памяти и простая аппаратная реализация. Недостаток - низкая степень сжатия по сравнению со схемой двухступенчатого кодирования. Предположим, что у нас имеется словарь, хранящий строки текста и содержащий порядка от 2-х до 8-ми тысяч пронумерованных гнезд. Запишем в первые 256 гнезд строки, состоящие из одного символа, номер которого равен номеру гнезда. Алгоритм просматривает входной поток, разбивая его на подстроки и добавляя новые гнезда в конец словаря. Прочитаем несколько символов в строку s и найдем в словаре строку t - самый длинный префикс s. Пусть он найден в гнезде с номером n. Выведем число n в выходной поток, переместим указатель входного потока на length(t) символов вперед и добавим в словарь новое гнездо, содержащее строку t+c, где с - очередной символ на входе (сразу после t). Алгоритм преобразует поток символов на входе в поток индексов ячеек словаря на выходе. При размере словаря в 4096 гнезд можно передавать 12 бит на каждый индекс. Каждая распознанная цепочка добавляет в словарь одно гнездо. При переполнении словаря упаковщик может либо прекратить его заполнение, либо очистить (полностью или частично).

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

От алгоритмов сжатия к форматам файлов, программам паковщикам и архиваторам.

Конечно, для системы сжатия информации хороший алгоритм - первоочередной, но не единственный больной вопрос. Конечному пользователю, как правило, нет дела до принципов организации функционирования и внутренней структуры используемых им программ, лишь бы работали качественно. Под качеством систем сжатия принято понимать несколько критериев, которые определяются применением при ее реализации и конкретном использовании. Так большинство применений необратимого сжатия лежит в области технологии хранения графической информации - картинки и видео, что, в свою очередь локализует алгоритм в рамках одного файла для одного стандарта и характера входного потока. Однако, на практике, из-за экономии места на накопителях, возникает необходимость сжатия любого файла (в том числе и выполнимого модуля). Эту проблему решают паковщики. И, наконец, проблему сжатия нескольких файлов и даже всех файлов каталогов и дисков решают программы - архиваторы. Заметим, что в список возможных задач архиваторов входит не только сжатие/извлечение информации файлов различных форматов, но и сохранение дерева файловой системы, атрибутов файлов, их имен, некоторой комментирующей информации, создание самораспаковывающихся архивов, архивация с сохранением кодов циклического контроля ошибок, для гарантии абсолютного соответствия извлеченных файлов исходным файлам, шифровку данных архива и архивация с паролем, обеспечение пользователя удобным интерфейсом и др. Поэтому, архиваторы являются одной из самых сложных систем программ. В настоящее время, к вышеперечисленным задачам можно пожелать наличия некоторых необязательных, но удобных свойств и возможностей. Это конфигурируемость пакета, наличие развитого оконного интерфейса, а не интерфейса командной строки, настраиваемость на определенный тип информации, сохранение параметров в файле архива, создание многотомных и/или самоизвлекающихся архивов и др. Все это желательно иметь при малой длине файла архиватора. Между программами паковщиками и архиваторами обычно не имеется принципиальных различий, однако, паковщики упаковывают информацию одного файла в один файл, а архиваторы образуют один файл выходного потока, который, впрочем, может быть автоматически нарезан на файлы равной длины для записи на гибкие диски. Отдельную группу составляют программы паковщики, занимающиеся сжатием выполнимых модулей и дисков. Также упаковку данных при помощи алгоритмов сжатия используют системы резервного копирования, сжатия устройств (логических дисков MS-DOS), факс-модемные драйверы и утилиты и др.

В настоящий момент на рынке программных продуктов и серверах программного обеспечения можно встретить достаточно большое число архивирующих и сжимающих утилит, большинство из которых доступны для некоммерческого использования. Такая доступность, прежде всего, связана с тем, что каждая, даже коммерческая, программа нуждается в обширном рынке пользователей. А поскольку форматы файлов архиваторов и паковщиков, даже использующих один и тот же алгоритм, не одинаковы, то такие программы невольно конкурируют за рынок пользователей. С этим также связано и то, что поддержка более популярных форматов файловых архивов начинает включаться в другие утилиты и программы и используемые форматы становятся стандартными форматами архивов (zip, arj, rar, ha, pak, cab и др.). Стандартный формат подразумевает исключительную легкость при поиске программы, необходимой для извлечения файлов из сжатого состояния и поддержку их другими программами.

Нами были проанализированы более 300 архиваторов и паковщиков и отобраны наиболее интересные. Тесты сжатия производились на ПК Intel Pentium 233MHz с RAM 64Mb под управлением ОС MS-Windows 95 (4.0.1111). Для тестирования использовались 7 файлов с совокупным размером 8646421 байт. В архиве содержались как текстовые (txt 643830), графические (bmp 2233560, psd 959170), двоичные (exe 4014592, dll 352256) и мультимедийные (avi 342420, mid 100593) файлы. Архивация производилась при работе в фоновом режиме из под оболочки FAR 1.52. Для измерения времени использовалась команда time. Файлы сжимались с жесткого диска на жесткий диск. Необходимо отметить, что в качестве опций для сжатия использовались параметры для наилучшего сжатия каждого файла, а в случае наличия у программы специальных параметров, определяющих сжатие файлов строго определенного формата, при его тестировании они также использовались. Результаты лучших экземпляров сведены нами в таблицу. Данные в таблице отсортированы в порядке ухудшения коэффициента сжатия, а ratio показывает, сколько процентов объема осталось после сжатия.

Как видно из приведенных результатов, в общем зачете - быстродействие/коэффициент сжатия победителями вышли IMP и UHARC. Абсолютными чемпионами по сжатию стали ACB и UHARC, а по скорости - AIN, однако, медленнее всех оказался ACB, затем идет BOA и UHARC. Наш привычный RAR занимает достаточно высокое место по скорости и относительно скромную позицию по сжатию, однако, это единственная из включенных нами в таблицу программ, имеющая оконно-ориентированный пользовательский интерфейс. Работа с остальными программами осуществляется посредством задания параметров в командной строке или файле.
................

Как выбрать программу - архиватор

Несмотря на то, что в наше время цена мегабайта дискового пространства уменьшается с каждым годом, а качество носителей информации растет, потребность в архивации и резервном копировании остается, а проблема все также актуальна, как и десять лет назад. Это определяется тем, что архивация и сжатие данных необходимы не только для экономии места на локальном дисковом носителе, но и для переноса информации, резервирования, резервного копирования и т.п. Поэтому, выбирая архиватор, необходимо руководствоваться его универсальностью и надежностью, но не забывать конечно и о главных параметрах - качество и скорость сжатия. Среди имеющихся в настоящий момент архиваторов многие являются специфичными к определенным форматам файлов, что несомненно следует использовать, но по назначению. Общий оценочный анализ показывает, что среди архиваторов с ratio <40% большинство имеет значительно более длительное время паковки, которое может быть настолько велико (отличаться в сотни раз) по сравнению с выигрышем в сжатии (на 7-10%), что целесообразность использования данных программ сомнительна даже на очень мощных персональных компьютерах, таких как Pentium II 330MHz. Угнетает и тот факт, что большинство систем сжатия по прежнему компонуются как выполнимые модули реального режима для ОС MS-DOS и все возможности защищенного режима не используются. Этот же относится и к интерфейсу программ, который в общем оставляет желать лучшего, т.к. командная строка, хоть и является достаточно универсальным средством взаимодействия пользователя с программами, однако, весьма плохо приспособлена для быстрого просмотра списков имен, множественного выбора из списков (например файлов в архиве), множественного помещения в список и т.п., т.е. для операций, наиболее часто встречающихся в процессе работы с архивами. Возражающим посоветую произвести такую операцию, замерив затраченное на нее время. Возьмите архив из ~500 файлов с различными расширениями и извлеките из него 20-30 файлов, причем имена которых определите во время просмотра содержимого архива. Выполните эту задачу при помощи командной строки и при помощи какого-нибудь оконного интерфейса. Такие и подобные операции пользователями интерфейсов командной строки обычно выполняются путем извлечения всех файлов из архива и удаления ненужных или переписывания необходимых в отдельный каталог, их архивация и удаление. Нет нужды говорить, что такая операция с применением оконного интерфейса и списков с возможностью множественного выбора элементов по маске производится гораздо быстрее и без затрат дополнительных дисковых ресурсов.

Из стандартных и наиболее полезных на текущий момент свойств программ архиваторов следует также отметить следующие:

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

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

Из попавших в рамки наших тестов, таким рекомендациям соответствует лишь RAR и WinRAR, а среди остальных - PkZip, WinZIP, ARJ, LHA и GZIP. Эти программы и стандарты поддерживаются большинством файловых менеджеров, для них написано множество оболочек и управляющих командных файлов.

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

Геннадий Баранов
http://pcclub.com.ua

Обзор методов сжатия данных

Сжатие способом кодирования серий

Сжатие без применения метода RLE

Процесс кодирования и его методы

Пример:

Арифметическое кодирование

Модели входного потока

Кодирование сортировкой

Двухступенчатое кодирование. Алгоритм Лемпеля-Зива

Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch - LZW)

Как выбрать программу - архиватор

Геннадий Баранов http://pcclub.com.ua

Геннадий Баранов
http://pcclub.com.ua