Методы архивации

Содержание

 

Основные термины		стр. 2
Алгоритмы сжатия
	Алгоритм RLE	стр. 4
	Алгоритм Хаффмана	стр. 4
	Арифметическое сжатие	стр. 6
	Алгоритм Лемпеля-Зива	стр. 8
	Алгоритм двухступенчатого сжатия	стр. 11
Архиваторы		стр. 12
Типы архивов		стр. 15
Список литературы		стр. 16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные термины

 

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

Архивация файлов - перекодирование данных с целью уменьшения их объёма.

Резервное копирование (англ. backup) - процесс создания копии данных на носителе (жёстком диске, дискете  и т. д.), предназначенном для восстановления данных в оригинальном месте их расположения в случае их повреждения или разрушения, соответствующими программами - резервными дубликаторами данных

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

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

 

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

Существует два вида алгоритмов сжатия данных:

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

 

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

 

Возникает вопрос - зачем  же нужен такой метод необратимого сжатия?

Рассмотрим следующий пример. На обычный Audio-CD (формат WAV) помещается в среднем 15-20 композиций, в то время как на CD с композициями в формате MPEG (файлы *.mp3) их может быть более 150. Достигается это именно за счет необратимого сжатия. Как известно, при переводе аналогового (в данном случает звукового) сигнала в цифровую форму, он подвергается дискретизации, т.е. делается выборка величин его уровней с определенной частотой. Устройство человеческого уха таково, что оно не замечает искажений звукового сигнала, если их величина не превышает определенного порога. Произведя необратимое сжатие исходной выборки, а затем, воспроизводя восстановленную выборку, мы не заметим разницы в звучании композиции, если уровень потери информации не превысил некоторого допустимого значения.

Аналогично для изображений, глаз не замечает искажений цвета  и яркости, меньших некоторой  пороговой величины, а, следовательно, допустимо потерять часть информации в выборке цвет + яркость. На этом принципе построен формат JPEG (файлы *.jpg).

 

 

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

 

АЛГОРИТМ  RLE

Наиболее простой из всех алгоритмов - это алгоритм RLE (Run Length Encoding - Кодирование Длин Серий). Суть метода состоит в замене цепочек  повторяющихся символов на этот символ и количество его повторов. Например, последовательность символов ABDCCCCCBAB будет заменена на ABD[C,5]BAB, вместо того чтобы писать символ "С" 5 раз подряд, алгоритм пишет его один раз, и рядом с ним указывает количество его повторов - 5. Недостатком метода является очень низкая степень сжатия текстов. Причина этого очевидна - нет слов, в которых подряд шло бы более двух одинаковых букв, а, следовательно, и сжимать почти нечего. Однако для графических файлов он довольно эффективен, т.к. последовательности одинаковых символов в них встречаются часто. Например, если в файле содержится изображение неба, то подряд может идти несколько сотен одинаковых байт с кодом синего цвета. Реально алгоритм RLE применяется в графических файлах формата PCX, а также как аппаратный протокол сжатия в некоторых типах модемов.

 

 

АЛГОРИТМ  ХАФФМАНА

Алгоритм Хаффмана (Huffman) является одним из старейших алгоритмов сжатия. Он относится к группе алгоритмов статистического сжатия, т.е. для  работы ему требуются сведения о  частоте появления каждого символа  во входном потоке.

Например, пусть имеется 8-символьный входной поток ACBBADAA. Частота появления символа "А" равна 4 / 8 = 0.5 (4 - число символов "А" в потоке, 8 - длина потока). Аналогично для "B" получаем 0.25 , для "C" и "D" - 0.125.

Сущность алгоритма  Хаффмана заключается в присвоении символам входного потока двоичных кодов переменной длины, в зависимости от их частоты. Чем чаще встречается символ, тем короче присваиваемый ему код. В нашем примере символу "А" будет присвоен двоичный код 1, символу "В" - 01, символам "C" и "D" - коды 000 и 001 соответственно. Присваиваемые коды должны подчиняться правилу префикса: "Код, использованный в сжатом потоке, не может быть префиксом любого другого кода". Выше мы присвоили символу "В" код 01 именно следуя этому правилу. Если символу "В" был бы присвоен код 10, то при восстановлении исходного потока возникла бы проблема: или истолковать единицу как код символа "А", а ноль как начало кода другого символа, или единица и ноль вместе образуют код для символа "В".

Для получения кодов, удовлетворяющих правилу префикса, обычно используют дерево кодов Хаффмана. "Листьями" этого дерева являются символы, а "ветвям" соответствует цифра 0, если она "растет" влево, или 1, если вправо.

 

 

 

 

 

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

Достоинством алгоритма Хаффмана является хорошая степень сжатия при достаточно высокой скорости работы. Недостаток - необходимость  двойного просмотра входного потока: первый раз с целью получения частот символов и построения дерева кодов, второй раз собственно проведение процесса сжатия. От этого недостатка можно попытаться избавиться путем построения заранее единого дерева, и применения его к любому входному потоку. При этом для построения дерева можно использовать давно подсчитанные филологами средние значения частот букв в текстах на русском языке. Например, частота буквы "А" больше частоты "У", а частота "Ц" меньше частоты "К". Однако для графических, звуковых и бинарных файлов такой метод, очевидно, не будет эффективным и, скорее всего, приведет к ухудшению качества сжатия. Для сжатия таких файлов можно применить алгоритмы Кнута (Knuth) и Уиттера (Witter), которые являются модификациями алгоритма Хаффмана. Эти алгоритмы достаточно сложны, и их описание выходит за рамки данной статьи.

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

 

 

АРИФМЕТИЧЕСКОЕ СЖАТИЕ

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

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

Рассмотрим входной поток BBAB. Частоты  символов соответственно 0.25 для "А" и 0.75 для "В". Теперь возьмем открытый справа интервал [0, 1). Разобьем его на две части, длина которых пропорциональна частотам символов. Получим субинтервалы [0, 0.75) для "В" и [0.75, 1) для "А". Суть алгоритма сводится к выделению субинтервалов из [0, 1) для каждого из символов входного потока. После выбора из входного потока очередного символа алгоритм уменьшает интервал, выбирая ту его часть, которая соответствует выбранному символу.

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

 Мы получили, что  входному потоку ВВАВ соответствует  интервал [108/256, 135/256), или, если записать  дроби в двоичном виде [0.01101100, 0.10000111). Для определенности необходимо выбрать любое число из этого интервала, например 128/256 (0.1 в двоичном виде), и записать его в выходной поток. После завершения процесса сжатия к выходному потоку необходимо добавить информацию о частотах символов, иначе восстановление будет невозможно.

Процесс восстановления проходит аналогично сжатию: начиная  с базового интервала [0, 1), последовательно  восстанавливаются символы входного потока. Для нашего примера базовый  интервал сперва будет разделен (согласно частотам символов) на [0, ?) и [3/4, 1). Т.к. 128/256 принадлежит интервалу [0, ?), ясно, что первый восстанавливаемый символ будет "В". Затем делим этот интервал на [0, 9/16) и [9/16, ?). Число 128/256 принадлежит интервалу [0, 9/16), т.е. второй восстанавливаемый символ также является "В", и т.д. Продолжая процесс, мы однозначно восстановим входной поток.

Вообще говоря, иногда в процессе восстановления на каком-то этапе может  получиться бесконечная дробь (например, 1/3 = 0.333:.), и алгоритм зациклится. Для  предотвращения этого к входному потоку добавляют так называемый EOS (End of stream - Символ конца потока), выбирая его из числа символов, не встречающихся во входном потоке. Если в процессе восстановления получается интервал, соответствующий EOS, процесс считается законченным.

При применении этого  метода возникают две проблемы. Во-первых, необходима вещественная арифметика неограниченной точности, в то время как математический сопроцессор компьютера обеспечивает точность порядка 19-20 значащих цифр, а  применение программной эмуляции, очевидно, слишком неэффективно. Во-вторых, если в алгоритмах Хаффмана или RLE мы можем получать символы выходного потока параллельно со сжатием входного, то при арифметическом сжатии результат становится известен лишь после полного просмотра и сжатия входного потока. Исследования, проведенные Рубиным (Rubin), однако, показывают, что на практике можно обойтись целочисленной арифметикой небольшой точности (16-32 разряда), а также добиться последовательной выдачи символов выходного потока по мере чтения входного потока, ценой незначительного снижения степени сжатия.

Практически данный алгоритм иногда применяют в составе алгоритма  двухступенчатого сжатия.

 

 

АЛГОРИТМ ЛЕМПЕЛЯ-ЗИВА

Алгоритм первоначально  был разработан Лемпелом и Зивом (Lempel & Ziv), в дальнейшем подвергался многим усовершенствованиям и дополнениям. Принцип его работы кардинально отличается от всех рассмотренных выше алгоритмов. Главное преимущество его заключается в изначальной однопроходности, т.е. он способен сжимать входной поток по мере поступления символов, не требуя для себя никакой предварительной информации о потоке.

 

Алгоритм	Автор	Описание
LZ77	Лемпель и Зив (Lempel & Ziv)	Ссылки и символы чередуются. Ссылка адресует подстроку среды  предыдущих символов
LZ78	Лемпель и Зив (Lempel & Ziv)	Аналогично LZ77, ссылка адресует ранее разобранную подстроку
LZR	Роден (Roden)	Аналогично LZ77, ссылка адресует подстроку среди всех предыдущих символов
LZW	Велч (Welch)	Выходной поток состоит только из ссылок, адресующих ранее разобранную  подстроку. Все ссылки фиксированной длины
LZMW	Миллер и Вегман (Miller & Wegman)	Подстроки строятся путем слияния  двух предыдущих символов
LZJ	Джейкобсон (Jakobsson)	Выходной поток состоит только из ссылок, адресующих подстроку среди  всех предыдущих символов
LZC	Томас (Thomas)	Аналогично LZW, но длина ссылок не фиксирована
LZSS	Белл (Bell)	Ссылки и символы различаются  по флаг-биту, ссылка указывает на подстроку  среди предыдущих N-символов
LZB	Белл (Bell)	Аналогично с LZSS, ссылки кодируются разными способами
LZT	Тишер (Tischer)	Аналогично LZC, подстроки хранятся в LRU
LZH	Брэнт (Brent)	Аналогично LZSS, ссылки сжимаются алгоритмом Хаффмана
LZFG	Фиала и Грин (Fiala & Greene)	Основан на построении цифрового дерева