Тема 5. Сжатие данных. Архивация данных

Позиция 29 Сжатие информации

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

Вопросы для самостоятельного изложения

В каких случаях, и для каких целей необходимо сжимать данные?

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

- Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

- Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

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

На чем основана возможность сжатия данных? В каких случаях сжатие данных невозможно?

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

В каких случаях можно использовать сжатие с потерями, в каких — без потерь? Чем различаются обратимые и необратимые методы сжатия данных?

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

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

- MPG - для для видеоданных;

- MP3 - для аудиоданных.

Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым. В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:

- GIF, TIFF - для графических данных;

- AVI - для видеоданных;

- ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

Какой класс программ используется для сжатия данных? На каких принципах эти программы работают? Есть ли универсальные программы сжатия данных, которые оптимальны для данных любого вида?

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

- алгоритм RLE (Run Length Encoding);

- алгоритмы группы KWE(KeyWord Encoding);

- алгоритм Хаффмана.

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

В каких случаях эффективно использовать непрерывный архив? Ответ обоснуйте.

Непрерывный (solid) архив — это архив RAR, упакованный специальным способом, при котором все сжимаемые файлы рассматриваются как один последовательный поток данных. Непрерывная архивация поддерживается только в формате RAR, для формата ZIP такого типа упаковки не существует. Метод сжатия для архивов RAR — обычный или непрерывный — выбирается пользователем.

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

- архив предполагается редко обновлять;

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

- нужно достичь более плотной степени сжатия, даже в ущерб скорости упаковки.

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

Какой принцип лежит в основе алгоритма RLE?

Алгоритм RLE.

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

Какой принцип лежит в основе алгоритма KWE?

Алгоритмы группы KWE.

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

Какой принцип лежит в основе алгоритма Хафмана?

Алгоритм Хаффмана.

В основе алгоритма Хаффмана лежит идея кодирования битовыми группами. Сначала проводится частотный анализ входной последовательности данных, то есть устанавливается частота вхождения каждого символа, встречащегося в ней. После этого, символы сортируются по уменьшению частоты вхождения. Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

Перечислите, какие типы архивов можно создавать с помощью программы WinRAR? Укажите характерные отличия каждого из перечисленных типов архивов.

WinRAR может создавать архивы двух разных форматов: RAR и ZIP. Ниже описаны сравнительные особенности каждого из них.

Архивы ZIP.

Основное преимущество формата ZIP — его популярность. Так, большинство архивов в Интернете имеют формат ZIP. Если вы хотите кому-то отправить архив, но не уверены, что у адресата есть программа WinRAR для распаковки архива, то имеет смысл использовать формат ZIP. Впрочем, в этом случае вы можете отправить и самораспаковывающийся (SFX) архив. Такие архивы чуть больше обычных, но для их распаковки не требуется никаких дополнительных программ.

Другое преимущество ZIP — скорость. Архивы ZIP обычно создаются быстрее архивов RAR, однако на современных компьютерах эта разница в скорости часто не имеет решающего значения.

Архивы RAR.

Формат RAR в большинстве случаев обеспечивает существенно лучшее сжатие, чем ZIP, особенно в режиме создания непрерывных архивов. Другая важная возможность RAR — поддержка многотомных архивов. Они намного удобнее и проще в использовании, чем так называемые "разделённые по дискам" ("span disks") архивы ZIP. WinRAR не поддерживает такие архивы ZIP — многотомные архивы можно создавать только в формате RAR.

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

Формат RAR позволяет обрабатывать файлы практически неограниченного размера (до 8 эксабайт, что равносильно 8 589 934 591 Гбайт), тогда как размер одного файла в архиве ZIP не может превышать 2 Гбайт. Обратите внимание, что старые файловые системы не поддерживают файлы размером более 4 Гбайт, поэтому при работе с такими файлами вы должны использовать файловую систему NTFS.

Самораспаковывающиеся архивы (SFX).

Самораспаковывающийся (SFX, от англ. SelF-eXtracting) архив — это архив, к которому присоединён исполняемый модуль. Этот модуль позволяет извлекать файлы простым запуском архива как обычной программы. Таким образом, для извлечения содержимого SFX-архива не требуется дополнительных внешних программ. Вместе с тем, WinRAR может работать с SFX-архивом точно так же, как и с любым другим, поэтому если вы не хотите запускать SFX-архив (например, когда не можете гарантировать, что в нём нет вирусов), то для просмотра или извлечения его содержимого можно использовать WinRAR.

SFX-архивы, как и любые другие исполняемые файлы, обычно имеют расширение.EXE.

SFX-архивы удобны в тех случаях, когда нужно передать кому-то архив, но вы не уверены, что у адресата есть соответствующий архиватор для его распаковки. Также можно использовать SFX-архивы для распространения своих собственных программ. Например, дистрибутив WinRAR базируется на GUI SFX-модуле RAR Default.sfx. Тома (архивы из нескольких частей). Тома — это фрагменты архива, состоящего из нескольких частей. Тома поддерживаются только в формате RAR, но не в ZIP. Обычно тома используются для сохранения большого архива на нескольких дискетах или других сменных носителях. По умолчанию тома RAR получают имена вида 'имя_тома.partNNN.rar', где NNN — номер тома. Если по каким-либо причинам эта схема именования томов вас не устраивает, то с помощью ключа -vn можно включить старую схему, основанную на расширениях файлов, при которой первый том многотомного архива получает расширение.rar, а расширения последующих томов нумеруются как.r00,.r01,.r02 и т.д. до.r99. Тома также могут быть непрерывными и самораспаковывающимися. Первый самораспаковывающийся том имеет другое (т.е. не.rar) расширение, например, для SFX-томов для Windows это будет.exe. Уже созданные многотомные архивы не допускают изменения, т.е. в них нельзя добавлять, обновлять или удалять файлы. Вы можете создать только новый набор томов. Для распаковки томов необходимо начинать извлечение с первого тома. Если тома находятся на несменном носителе (например, на жёстком диске), то сначала нужно переписать все тома в одну папку.