4.10.1. Архиваторы

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

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

Суть этого кодирования заключается в представлении часто встречающихся символов (сочетаний символов) короткими ко­дами, а редко встречаемых – более длинными. Предположим, что в исходной кодируемой последовательности встречаются только n символов: S1 S2, ..., Sn-2, Sn-1, Sn с вероятностью появле­ния р1, р2, ..., рn-2, pn-1, Рп. Для простоты будем считать, что сим­волы отсортированы в порядке убывания этой вероятности. Объе­диним два символа Sn-1 и Sn с наименьшими вероятностями появления в один комбинированный символ S и рассчитаем ве­роятность его появления рn-1 + рn. В результате получим после­довательность из п-1 символов: S1, S2, ..., Sn-2, S. В дальнейшем этот символ S участвует в обработке наравне с исходными. Сим­волы опять сортируют в порядке убывания вероятности их по­явления, и повторяют процедуру объединения до тех пор; пока не останется только два символа. Затем в обратном порядке про­исходит кодирование исходных символов. Поясним это следую­щим примером.

Пример 1. Имеется файл, содержащий только символы S1, ..., S4 с вероятностями их появления {0,6 0,2 0,15 и 0,05} соответственно. Требуется представить эти символы сокращен­ным кодом.

Решение. Упорядочим символы по возрастанию вероятностей их появления и объединим по приведенному алгоритму (рис.4.10).

Рис. 4.10. Иллюстрация процесса кодирования информации

На последнем шаге объединения установим, что символ S1 коди­руется 1 (единицей), а код остальных символов имеет первый 0 (нуль). Затем установим, что символ S2 кодируется кодом 01, а коды сим­волов S3 и S4 имеют первые 00. Аналогично, на последнем шаге определяем, что код символа S3 равен 001, а символа S4 — 000.

В результате символ S1 кодируется 1 (1 битом), символ S2 — 01 (2 битами), а символы S3 и S4 кодируются 001 и 000 (3 битами каждый). 

Оценим эффект уменьшения размера исходного текста при таком кодировании. Предположим, имеется последовательность из 1000 таких символов S1, ..., S4. Тогда символ, обозначенный через S1, присутствует в последовательности 600 раз, символ S2 — 200 раз и символы S3 и S4 по 150 и 50 раз соответственно. Расчет не сложный, достаточно вероятность появления символа умно­жить на объем выборки. Общая длина закодированной последо­вательности равна: (1x600) + (2x200)+ (3x150) + (3x50) = 1600бит.

Если кодировать символы без учета вероятности их встреча­емости, например символ S1 кодируется через 00, символ S2 че­рез 01 и символы S3 и S4 через 10 и 11 соответственно (каждый символ кодируется ровно двумя битами), то последовательность из 1000 таких символов займет 2x1000 = 2000 бит.

Эффект сокращения длины кода при использовании энтро­пийного кодирования с 2000 бит до 1600 (на 20%) очевиден, а с учетом обычно используемого для представления каждого сим­вола длины кода в 8 бит тем более очевиден (с 8000 бит до 1600 — то есть в 5 раз).

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

В реальных программах-архиваторах процедура поиска и пе­рекодировки намного сложнее.

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

Первые программы-архиваторы были ориентированы на ра­боту под управлением MS DOS: ARJ, PKZIP/PKUNZIP, РАК, LHA, RAR. Эти программы отличались форматом архивных файлов, скоростью работы, степенью сжатия файлов в архиве, интерфейсом пользователя. Общим их недостатком являлся не­достаточно удобный интерфейс. Пользователю необходимо было помнить форматы команд и постоянно указывать их в команд­ной строке. Этого недостатка лишены программы-архиваторы, ориентированные на работу под управлением ОС Windows. 

Некоторые из современных программ-архиваторов представлены в табл.4.5.

Сре­ди современных программ-архиваторов выделяют WinRAR (раз­ра-ботка Е. Рошал) и WinZip фирмы Niko Mak Computing (а также ряд других).

Таблица 4.5

Различные типы современных архиваторов

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

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