Ирина Эланс

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

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

Содержание

Основные термины		стр. 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)	Основан на построении цифрового дерева

Процесс сжатия в общем виде протекает следующим образом: на вход алгоритма сжатия поступает непрерывный входной поток. Алгоритм постоянно хранит некоторое достаточно большое количество последних обработанных символов в области SDB (Sliding Dictionary Buffer - Буфер скользящего словаря). По мере обработки входного потока вновь поступившие символы попадают в конец SDB, смещая предыдущие символы и вытесняя самые старые. Размер SDB сильно варьируется в разных реализациях (от 8 Kb в ранних версиях ZIP, до 1 Mb в WinRAR v2.0). Увеличивая размер SDB, мы улучшаем степень сжатия, но при этом падает его скорость, и растет требуемый объем памяти.

Путем поиска в SDB алгоритм выделяет самую длинную начальную подстроку входного потока, совпадающую с одной из подстрок в SDB, и выдает на выход пару (Distance, Length), где Distance - расстояние от найденной в SDB подстроки до входной подстроки, а Length - ее длина. В случае если подстрока в SDB не найдена, в выходной поток просто копируется очередной символ входного потока. Поясним на следующем примере. Имеется входной поток АDСАВDВАDAССADDВDАВDВАЕDАСCAD. Для первых 17-ти символов алгоритм не находит подстрок, поэтому они просто копируются в выходной поток. Но в 18-й позиции он обнаруживает подстроку АВDВА и видит, что такая же подстрока располагается в 4-й позиции. Поэтому он заменяет ее ссылкой [14, 5], где 14 - это расстояние от 18-й позиции до 4-й, а 5 - длина подстроки. Далее подстроки опять не находятся, т.е. происходит простое копирование, до тех пор пока в 25-й позиции не обнаруживается подстрока АССА, которая расположена также и в 10-й позиции. Она заменяется ссылкой [15, 4], где 15 - это расстояние от 25-й позиции до 10-й, а 4 - длина подстроки.

В результате выходной поток будет иметь вид АDСАВDВАDAССADDВD [14, 5]ЕD[15,4]D.

Таким образом, алгоритм Лемпеля-Зива (иногда называемый также LZ-compression) преобразует входной поток в два выходных параллельных потока Distance и Length. Эти потоки хорошо поддаются сжатию алгоритмом Хаффмана, или арифметическим сжатием, и отсюда мы логично приходим к идее двухступенчатого сжатия, при котором на первом этапе входной поток сжимается за счет замены подстрок на ссылки на такие же подстроки, встречающиеся ранее, а на втором этапе происходит дополнительное сжатие за счет компрессии ссылок.

АЛГОРИТМ ДВУХСТУПЕНЧАТОГО СЖАТИЯ

Алгоритм двухступенчатого сжатия является наиболее эффективным алгоритмом, из практически применяемых в настоящее время. Именно он применяется в архиваторах ZIP, RAR, ARJ и многих других случаях, где требуется сжатие данных.

При использовании этого алгоритма возникают две проблемы: проблема синхронной записи двух выходных потоков в файл и проблема быстрого поиска в SDB. Первая из них, как правило, решается чередованием записи символов из потока Distance и из потока Length, т.е. Distance1, Length1, Distance2, Length2,:

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

Архиваторы

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

1. файловые архиваторы

2. программные архиваторы

3. дисковые архиваторы

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

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

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

Для архивирования используются специальные программы - архиваторы или диспетчеры архивов. Наиболее известные архиваторы: WinZip; WinRar; WinArj. Эти программы обеспечивают возможность использования и других архиваторов, поэтому, если на компьютере, куда перенесены сжатые в них файлы, отсутствуют указанные программы, архивы можно распаковать с помощью другого архиватора. До сих пор широко используются и соответствующие программы, созданные в MS DOS, но способные работать и в Windows.

Почти все архиваторы позволяют создавать удобные самораспаковывающиеся архивы (SFX - Self-extracting-архивы) - файлы с расширением .ехе. Для распаковки такого архива не требуется программы-архиватора, достаточно запустить архив *.ехе как программу. Многие архиваторы позволяют создавать многотомные (распределенные) архивы, которые могут размещаться на нескольких дискетах.

Основными характеристиками программ-архиваторов являются:

• скорость работы;

• сервис (набор функций архиватора);

• степень сжатия - отношение размера исходного файла к размеру упакованного файла.

Основными функциями архиваторов являются:

• создание архивных файлов из отдельных (или всех) файлов текущего каталога и его подкаталогов, загружая в один архив до 32 000 файлов;

• добавление файлов в архив;

• извлечение и удаление файлов из архива;

• просмотр содержимого архива;

• просмотр содержимого архивированных файлов и поиск строк в архивированных файлах;

• ввод в архив комментарии к файлам;

• создание многотомных архивов;

• создание самораспаковывающихся архивов, как в одном томе, так и в виде нескольких томов;

• обеспечение защиты информации в в архиве и доступ к файлам, помещенным в архив, защиту каждого из помещенных в архив файлов циклическим кодом;

• тестирование архива, проверка сохранности в нем информации;

• восстановление файлов (частично или полностью) из поврежденных архивов;

• поддержки типов архивов, созданных другими архиваторами и др.

Типы архивов

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

Характерными форматами сжатия с потерей информации являются:

• .jpg - для графических данных;

• .mpg - для видеоданных;

• .mp3 - для звуковых данных.

Характерные форматы сжатия без потери информации:

• .tif, .pcx и другие - для графических файлов;

• .avi - для видеоклипов;

• .zip, .arj, .rar, .lzh, .cab и др. - для любых типов файлов.

Список литературы

Новожилов, О. П.

«Информатика: учебное пособие» Юрайт Издательство ООО, 2011

Семакин, И.Г.

Информатика и ИКТ : базовый уровень : учебник для 10-11-го классов
Бином. Лаборатория знаний, 2010, Несерийное издание.

Интернет-ресурс:

http://www.comprice.ru

http://www.windxp.com.ru

http://ru.wikipedia.org