Принципы архивирования и программы архивации

Действие средств архивации информации основано на применении алгоритмов сжатия данных, имеющих достаточно долгую историю. В середине 40-х годов XX в. группа ученых-математиков, работавшая в области электротехники, предложила способ создания технологии хранения данных, обеспечивающей экономное расходование пространства хранения информации. Одним из ученых, входящих в эту группу, был Клод Элвуд Шеннон (Claude Elwood Shannon) – основоположник современной теории информации. Математическое понятие информации связано с единицами ее измерения. В теории информации для измерения количества информации принят энтропийный подход, который устанавливает ценность информации для получателя, содержащейся в сообщении. За единицу измерения информации принята величина, названная в честь К.Э. Шеннона – 1 Шеннон – единица измерения количества информации, равная количеству информации, содержащейся в сообщении, выраженном одним из двух равновероятных, взаимоисключающих и исчер­пываю­щих состояний)[8].. Из теоретических разработок того времени в настоящее время находят практическое применение алгоритмы сжатия Хаффмана и Шен­нона-Фано. В 1977 г. математики Абрахам Лемпел (Abraham Lempel) и Якоб Зив (Jacob Ziv) предложили иной алгоритм сжатия, который позже доработал Терри Велч (Terry Welch). Данный алгоритм впоследствии получил название в соответствии с фамилиями авторов-разработчиков – алгоритм LZW.

В настоящее время существует достаточно большое количество специальных программ для архивации файлов, хотя общепризнанных и наиболее употребимых не так уж и много. Некоторые из этих программ распространяются бесплатно[9], часть – на коммерческой основе (за плату), но большинство программ такого рода распространяются как «Shareware», т. е. они могут быть получены бесплатно, например, – через Internet. Если же пользователю эта программа понравилась, и он хочет использовать ее постоянно, ему предлагается выслать автору программы или распространителям небольшое, обычно до 50 дол., вознаграждение. Например, за полнофункциональный вариант программы-архиватора WinZip пользователь должен будет перечислить разработчику 29 дол. Как это делается – объясняется, например, в справочной системе утилиты WinZip[10]. Цена таких условно бесплатных программ очень сильно зависит от количества копий, которые хочет получить пользователь

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

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

Принцип работы практически всех программ-архиваторов основан на поиске в файле так называемой «избыточной» информации и последующем ее кодировании с целью получения минимального объема. Самый простой алгоритм – заменить длинную последовательность одинаковых символов одним таким символом с указанием количества его повторов[11]. Например, имея в исходном файле строку NNNNNNNNNNNNNNN, удобнее записать ее «15N». При такой записи даже «невооруженным глазом» видно, что она занимает значительно меньше места, чем первая – в исходном файле. Современные программы-архиваторы используют и более сложные методы сжатия, но тем не менее все методы архивации основаны на статистике сжимаемой информации, т.е. наиболее часто встречаемые символы кодируются наименьшим числом бит, редко встречаемые символы, соответственно, кодируются более длинной последовательностью бит.

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

Рассмотрим простейший пример. Пусть внутри нашего файла находится последовательность байтов, которые часто повторяются[12]:

 

F

F

F

F

F

M

M

M

M

M

V

V

V

V

V

 

Такой исходный (называемый – архивируемый) файл занимает 15 байт и состоит из следующих символов в шестнадцатеричной системе представления информации:

 

4D

4D

4D

4D

4D

 

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

 

4D

 

Такая запись означает: в файле с первой позиции пять раз повторяется символ «F», с позиции 6 пять раз повторяется символ «M» и с позиции 11 пять раз повторяется символ «V». Для хранения файла в такой форме потребуется уже всего 9 байт, что на 6 байт меньше исходного (сравните количество задействованных ячеек).

Рассмотренный метод является простым и очень эффективным способом сжатия файлов только в том случае, если обрабатываемый файл содержит большое количество последовательностей повторяющихся файлов. В том же случае, если исходный файл содержит небольшое количество последовательностей повторяющихся символов, такой метод не обеспечивает большой экономии объема. Наиболее эффективен метод сжатия данных, используемый в настоящее время в том или ином виде практически любой программой-архиватором, – это так называемый оптимальный префиксный код и, в частности, кодирование символами переменной длины (алгоритм Хаффмана). Этот метод позволяет записывать наиболее часто встречающиеся символы и группы символов всего лишь несколькими битами. Редкие же символы и фразы будут записаны более длинными битовыми строками. Метод основан на частоте встречаемости определенных символов. Например, в любом английском тексте буква E встречается гораздо чаще, чем буква Z, а буквы X и Q вообще относятся к наименее встречающимся. Таким образом, используя специальную таблицу соответствия, можно закодировать каждую букву Е меньшим числом бит и использовать более длинный код для кодирования более редких букв.

Частота встречаемости определенных символов в тексте была использована английским изобретателем Кристофером Шоулсом (Christopher Sholes) в XIX в. при конструировании пишущей машинки. В 1876 г. он предложил существующую до настоящего времени раскладку клавиатуры QWERTY, исходя именно из того принципа, что порядок букв на ней выбирался специально так, чтобы замедлить скорость набора текста на машинке: при очень быстром наборе рычажки с буквами цеплялись друг за друга[13].

Такие популярные архиваторы, как ARJ, PAK, PKZIP работают на основе другого метода (алгоритм Лемпела-Зива). Эти архиваторы классифицируются в специальной литературе как адаптивные словарные кодировщики. Принцип, на котором построен этот метод, заключается в том, что повторяющиеся текстовые строки заменяются указателями на идентичные им строки, встречавшиеся ранее в тексте файла. Лучше всего принцип действия этого метода можно проиллюстрировать на простом примере. Например, все слова какой-либо книги могут быть представлены в виде номеров страниц и номеров строк некоего условного словаря. Важнейшей отличительной чертой такого алгоритма является использование грамматического разбора предшествующего текста с разбиением его на фразы, которые записываются в словарь. Система принятых указателей позволяет сделать ссылки на любую фразу в окне установленного размера, предшествующего текущей фразе. В том случае, если соответствие найдено, текущая фраза заменяется указателем на своего предыдущего двойника.

 

Вопросы для самоконтроля

1. Какие программы называются архиваторами?

2. На чем основан принцип работы программ-архи­ва­торов?

3. Попробуйте пояснить принцип сжатия текстовой и графической информации на простых примерах.

4. Назовите основные виды современных программ-архи­ва­торов.

5. Какие критерии могут служить достаточным основанием для выбора того или иного типа архиватора?

6. Применение каких современных программ-архиваторов наиболее предпочтительно и почему?

⇐ Предыдущая123456789Следующая ⇒

Поделиться: