Архивация. Создание архива данных. Извлечение данных из архива

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

Архивация

Архивация (упаковка)

— помещение исходных файлов (данных) в архивный файл в сжатом (англ. lossy) или несжатом (англ. lossless) виде.

Сжатие данных

— алгоритмическое преобразование данных, которое уменьшает их объём. При этом данные не теряются.

Архивация нужна для:

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

Выбор между сжатием с потерями (lossy) и без потерь (lossless) зависит от типа данных и требований к их качеству.

• сжатие без потерь обязательно там, где важна абсолютная точность и сохранение каждого бита информации. Например, при архивации текстовых документов, исходного кода программ, баз данных, исполняемых файлов (.exe), а также в профессиональной обработке фотографий (форматы RAW, PNG) и аудио (FLAC), где любое искажение недопустимо.
• сжатие с потерями широко применяется для мультимедийного контента, предназначенного для конечного пользователя — фотографии в формате JPEG, музыка в MP3/AAC, видео в MP4/AVI, — где алгоритм намеренно отбрасывает малозаметные для человеческого глаза или уха детали, уменьшая размер файла в десятки раз при приемлемом качестве.

В таблице приведены различные форматы файлов с разбивкой по типу сжатия:

* WebP поддерживает оба типа сжатия

Пример сжатия изображения:

Принцип архивации/сжатия данных

RLE

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

• Кодирование Хаффмана
• LZ77
• LZ78
• LZW
• Deflate
• Brotli
• Bzip2
• Арифметическое кодирование
• PPM

Рассмотрим принцип сжатия данных без потерь на примере кодирования длин серий (Run-Length Encoding, RLE). Это простой алгоритм. Он заменяет серии (последовательности) из двух или более одинаковых символов числом, обозначающим длину серии. После длины идёт сам символ. Алгоритм полезен для сильно избыточных данных, например простых картинок с большим количеством одинаковых пикселей.

Рассмотрим пример. На входе:

AAABBCCCCDEEEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

На выходе:

3A2B4C1D8E29A

Как вы видите, преобразованный набор символов хранит ту же информацию, но занимает в 48/13≈3.7 раза меньше места! Число 3.7 - степень сжатия данных.

Самостоятельное задание:

Зашифруйте последовательности с помощью RLE (кодирования длин серий) и посчитайте степень сжатия:

• SRRRJJJAAAGOYAEEEAAASAVVVSCALLVVVPPPLASSSAAAAADDD
• GYUURRRJJJJJWWWWWWWWCCCCCCCCCCCCC
• HAAAAAVEEEEEEANNNNNNNIIIIICCCCEEEEEEEEDDDDDDDDDDAYY

LZ77

LZ77

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

Общая схема алгоритма заключается в:

• Входные данные читаются последовательно.
• Слева от текущей позиции - прочитанная часть символов
• Справа от текущей позиции - непрочитанная часть символов
• Cкользящее окно = прочитанная часть символов + непрочитанная часть символов
• Для символов непрочитанной части ищется наиболее длинное совпадение в прочитанной части. Если совпадение найдено, то
  1. составляется комбинация (смещение, длина, следующий символ).
     • смещение указывает на сколько шагов надо сместиться назад,
     • длина - количество совпадающих символов.
  2. Комбинация записывается в словарь
• В конце выходными данными является словарь комбинаций.

Пример

Рассмотрим пример. Мы хотим закодировать текст:

Наш первый шаг - выбрать размеры двух буферов.

Первый буфер

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

Второй буфер

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

Размер первого буфера может быть больше или равным размеру второго буфера. Для простоты выберем оба буфера, равными 6 символам.

Начальная позиция:

Запишем в словарь символ c: (0,0,c), первый ноль - текущая позиция, второй ноль пишется, так как нет смещения. Идём дальше:

Запишем в словарь символ a: (0,0,a). Идём дальше:

Запишем в словарь символ b: (0,0,b). Идём дальше:

Запишем в словарь символ r: (0,0,r). Идём дальше:

Символ a уже встречался, поэтому считаем расстояние до него: 3 шага смещения. Следующий символ из непрочитанной части - c. Такого символа не было в комбинации, которую мы нашли. Поэтому длина комбинации - 1. Запишем в словарь: (3,1,c). Так как мы учли следующий за комбинацией символ c, то сместимся на два шага:

Текущий символ a мы уже встречали, причём дважды. Поэтому мы ищем наиболее длинную комбинацию: a, ad, ada, adab и т.д. Но не длиннее буфера непрочитанной области. Так как комбинаций длиннее 1 нет, то записываем в словарь найденную комбинацию с наименьшим смещением: (2,1,d). Идём дальше:

Удача! Первая длинная комбинация, которая позволит сэкономить много места! Символ a встречался 3 раза, однако самая длинная комбинация abra начинается с самого дальнего символа. Запишем в словарь комбинацию (7,4,r) и сместимся сразу на 5 позиций:

Символ r встречается 2 раза, при этом так же, как и в прошлый раз, с дальнего символа начинается более длинная комбинация. Причём комбинация включает символы также в непрочитанной зоне. Мы можем это также учесть. Запишем в словарь комбинацию rarra: (3,5,d).

Собирём вместе все наши записи из словаря:
(0,0,c) (0,0,a) (0,0,b) (0,0,r) (3,1,c) (2,1,d) (7,4,r) (3,5,d)

Была показана упрощённая схема алгоритма. Если мы посчитаем количество памяти, требующееся для хранения наших записей, то оно превысит количество памяти, необходимое для хранения исходной строки.

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

Самостоятельное задание:

1. Расшифруйте полученную в примере закодированную строку, запишите результат, сравните с исходной строкой.
2. Придумайте последовательность длиной не меньше 20 символов и зашифруйте её с помощью алгоритма LZ77. В качестве последовательности можете использовать любой текст.
3. Зашифруйте с помощью алгоритма LZ77 скороговорку:

Карл у Клары украл кораллы, а Клара у Карла украла кларнет

4. Расшифруйте текст, зашифрованный с помощью LZ77:

(0,0,‘т’) (0,0,‘р’) (0,0,‘и’) (0,0,‘д’) (0,0,‘ц’) (0,0,‘а’) (6,1,‘ь’) (0,0,’ ‘) (9,3,’ ‘) (0,0,‘к’) (0,0,‘о’) (5,1,‘а’) (0,0,‘б’) (0,0,‘л’) (0,0,‘я’) (8,1,‘л’) (6,1,‘в’) (13,1,‘р’) (12,1,‘в’) (6,1,‘л’) (6,1,’,’) (12,13,‘д’) (6,1,’ ‘) (39,1,‘а’) (37,1,’ ‘) (10,1,’ ‘) (0,0,‘н’) (0,0,‘е’) (3,1,‘в’) (0,0,‘ы’) (26,10,’’)

Архивы данных

Архив

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

Степень сжатия зависит от:

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

Лучше всего сжимаются файлы картинок и текстовые файлы, для которых размер архива может достигать 5 – 40% от общего размера исходных файлов. Меньше сжимаются файлы исполняемых программ и загрузочных модулей — 60 – 90%. Почти не сжимаются уже заархивированные файлы.

Пример сжатия файла с 412.2 Кб до 244 Кб:

В оглавлении архивного файла (архива) для каждого содержащегося в нём файла хранится следующая информация:

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

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

Архиваторы позволяют:

• создавать архивы с файлами;
• защищать созданные архивы паролем (получить данные из архива можно только введя пароль);
• разделять большой архивный файл на несколько частей (многотомный архив) при необходимости переноса данных на нескольких носителях ограниченного объёма;
• сохранять и восстанавливать структуру подкаталогов. Сжиматься могут как один, так и несколько файлов, которые в сжатом виде помещаются в архив.

Программы для архивации отличаются используемыми методами сжатия, что соответственно влияет на степень сжатия. Например архиватор 7-zip использует алгоритм сжатия данных по словарю LZMA, схожий с рассмотренным выше алгоритмом LZ77.

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

Разархивация (распаковка)

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

Архиваторы имеют следующие функциональные возможности:

1. Уменьшение требуемого объёма памяти для хранения файлов от 20% до 90% первоначального объёма.
2. Обновление в архиве только тех файлов, которые изменялись со времени их последнего занесения в архив, т.е. программа-упаковщик сама следит за изменениями, внесенными пользователем в архивируемые файлы, и помещает в архив только новые и измененные файлы.
3. Объединение группы файлов с сохранением в архиве имен директорий с именами файлов, что позволяет при разархивации восстанавливать полную структуру директорий и файлов.
4. Написания комментариев к архиву и файлам в архиве.
5. Создание саморазархивируемых архивов, которые для извлечения файлов не требуют наличия самого архиватора.
6. Создание многотомных архивов – последовательности архивных файлов. Многотомные архивы предназначены для архивации больших комплексов файлов на носители (например, флеш-память).

Популярные архиваторы:

Другие архиваторы вы можете посмотреть в списке архиваторов.

Практика

Задание 1. Сбор информации для последующего архивирования

1. На рабочем столе создайте директорию и назовите её Информатика_архивация.
2. В папке Информатика_архивация создайте текстовый файл результаты архивации.txt
3. Внутри папки Информатика_архивация создайте директорию Архивация картинок, и с помощью браузера и любой поисковой системы найдите 10 фотографий городов, природы, людей из Вашей страны и скачайте их в данную директорию.
4. Нажмите правой клавишей мыши (ПКМ) по директории Архивация картинок, нажмите левой клавишей мыши (ЛКМ) по пункту Свойства, посмотрите на размер папки в байтах и запишите это значение в файл результаты архивации.txt в виде:

размер директории "Архивация картинок" до архивации составляет ... байт

5. Внутри Информатика_архивация создайте директорию Архивация PDF документов, и с помощью браузера найдите 5 любых статей по интересующей вас теме из энциклопедии Wikipedia на Вашем родном языке. Скачайте статьи в директорию Архивация PDF документов как документы формата PDF. Для этого на нужной странице нажмите ПКМ и выберите Сохранить страницу как, далее измените тип файла на Сохранить как PDF

PDF (Portable Document Format)

— универсальный открытый кроссплатформенный формат файлов, в котором можно хранить и передавать отчёты, статьи, презентации и другие документы. Файлы такого формата можно создать с помощью редактора текстовых документов из файлов .docx, с помощью Latex-редактора, с помощью редактора презентаций и многих других программ.

6. Нажмите ПКМ по директории Архивация PDF документов, нажмите ЛКМ по пункту Свойства, посмотрите на размер папки в байтах и запишите это значение в файл результаты архивации.txt:

размер директории "Архивация PDF документов" до архивации составляет ... байт

7. Внутри папки Информатика_архивация создайте директорию Архивация HTML-страниц, и с помощью браузера найдите 5 любых статей на интересующую вас тему из энциклопедии Wikipedia на русском языке и скачайте их в данную директорию как HTML-страницы.

8. Нажмите ПКМ по директории Архивация HTML-страниц, нажмите левой клавишей мыши (ЛКМ) по пункту Свойства, посмотрите на размер папки в байтах и запишите это значение в файл результаты архивации.txt:

размер директории "Архивация HTML-страниц" до архивации составляет ... байт

Задание 2. Создание архива

1. Зайдите в директорию Информатика_архивация
2. Нажмите ПКМ по директории Архивация картинок, наведите на пункт 7-Zip и нажмите ЛКМ по Добавить к архиву…
3. Выберите формат архива zip и максимальный уровень сжатия:

Параметры создания архива (а — Формат архива, б — Уровень сжатия):

4. Посмотрите на размер полученного архива в байтах и добавьте запись в файл результаты архивации.txt в виде

размер директории "Архивация картинок" после архивации составляет ... байт

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

Соотношение размера архива "Архивация картинок.zip" к размеру исходной директории равно ... \%

6. Посчитайте степень сжатия архива:

Степень сжатия равна  ...

7. Повторите пункты 1—6 для Архивация PDF документов
8. Повторите пункты 1—6 для Архивация HTML-страниц
9. В файл результаты архивации.txt добавьте в свободной форме оценку сравнения трёх результатов архивации.
10. Загрузите файлы результаты архивации.txt, Архивация картинок.zip, Архивация PDF документов.zip и Архивация HTML-страниц.zip в папку Архивация в папке Информатика в вашем облачном хранилище.

Задание 3. Извлечение файлов из архива

1. Создайте на Рабочем столе папку Извлечение.

2. Выберите архив Архивация картинок.zip

3. Щёлкните по нему ПКМ, выберите пункт Извлечь всё…

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

5. Нажмите кнопку ОК.

6. Ознакомьтесь с результатом извлечения.

7. Повторите пункты 2—6 для архива Архивация PDF документов.zip

8. Повторите пункты 2—6 для архива Архивация HTML-страниц.zip

9. Удалите папку Извлечение с Рабочего стола.

Ключевые слова

Добавьте слова в свой глоссарий

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

1. В чём принципиальная разница между сжатием с потерями (lossy) и без потерь (lossless)? Приведите по одному примеру типа файлов, для которого уместно использовать каждый из этих методов.
2. Из каких трёх элементов состоит запись в словаре алгоритма LZ77? Кратко объясните, что означает каждый из них: смещение, длина, следующий символ.
3. Почему текстовые файлы и простые изображения сжимаются хорошо (до 5–40% от исходного размера), а уже заархивированные файлы или видео в MP4 — почти не сжимаются?

Дополнительное (необязательное) задание. Программирование

1. Напишите программу кодирования и декодирования данных методами RLE и LZ77.
2. Сравните время работы таких алгоритмов на входных данных различной длины.
3. Сравните размер закодированных данных и степень сжатия алгоритмов.