9.1 Архивация данных

Возможность уплотнения данных основана на том, что информация часто обладает избыточностью, которая зависит от вида информации. Случайная потеря 10% фотографии, скорее всего, не повлияет на ее информативность. Если на странице книги отсутствует 10% строк, то понять ее содержание уже трудно. Если взять программный код, в котором утрачено 10% информации, то восстановить его, скорее всего, уже не удастся. У этих видов данных разная избыточность. Несмотря на то, что объемы внешней памяти ЭВМ постоянно растут, потребность в архивации не уменьшается. Это объясняется тем, что архивация необходима не только для экономии места в памяти, но и для надежного хранения копий ценной информации, а также для быстрой передачи информации по сети на другие ЭВМ. Кроме того, возможность отказа магнитных носителей информации, разрушающее действие вирусов заставляет пользователей делать резервное копирование ценной информации на другие (запасные) носители информации.

Процесс записи файла в архивный файл называется архивированием (упаковкой, сжатием), а извлечение файла из архива – разархивированием (распаковкой).

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

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

Архивация информации – это такое преобразование информации, при котором объем информации уменьшается, а количество информации остается прежним.

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

Степень (качество) сжатия файлов характеризуется коэффициентом сжатия Kc, который определяется как отношение объема сжатого файла Vc к объему исходного файла Vo, выраженное в %:

Чем меньше Kc, тем выше степень сжатия.

Все используемые методы сжатия информации можно разделить на 2 класса:

  • Упаковка без потерь информации (обратимый алгоритм) – можно точно восстановить исходную информацию по имеющейся упакованной информации.
  • Упаковка с потерей информации (необратимый алгоритм) – распакованное сообщение будет отличаться от исходного.

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

1. Метод Хаффмана (1952) – основан на учете частот символов. Часто встречающиеся символы кодируются короткими последовательностями битов, а более редкие символы – длинными последовательностями битов. К каждому сжатому архиву прикладывается таблица соответствия имеющихся символов и кодов, заменяющих эти символы.

Пример: Пусть входной алгоритм сообщения состоит из 4-х символов: a, b, c, d, частоты повторения которых 1/2, 1/4, 1/8,1/8. Кодирование Хаффмана для этого алфавита задается таблицей:

символ Частота Входной код (до архивации) Выходной код(после архивации)
A 1/2 00 0
B 1/4 01 10
C 1/8 10 110
D 1/8 11 111

Тогда текст abbadaca будет закодирован так:
Входной код — 00 01 01 00 11 00 10 00 — 16 бит
Выходной код — 0 10 10 0 111 0 110 0 — 14 бит

К маленькому файлу прикладывать таблицу кодировки не выгодно, т.к. она займет места больше, чем сам файл. Чем длиннее файл, тем выгоднее этот метод. Метод Хаффмана эффективен для упаковки текстов.

2. Метод RLE (Run Length Encoding) – основан на выделении повторяющихся фрагментов. В сообщениях часто встречаются несколько подряд идущих одинаковых байтов, а некоторые последовательности байтов повторяются многократно. При упаковке такие места можно заменить командами вида: «повторить данный байт n раз» или «взять часть текста длиной k байт, которые встречалась m байтов назад». При упаковке графической информации чаще встречается первая ситуация, при упаковке текстов – вторая.

Пример:
Изображение звездного неба: на черном фоне видны редкие белые звезды. При растровом представлении неба информация в ЭВМ будет храниться в таком виде: черное- черное- черное- черное- белое- черное- черное- черное- черное- белое-черное- черное- черное- черное- белое- черное- черное- белое- черное и т.д. Значительно компактнее хранить информацию, указав, сколько раз подряд идут черные пиксели, сколько раз белые и т.д.

Упакованная этим методом последовательность состоит из управляющих байтов, за которыми следуют 1 или несколько байтов данных. Если старший бит управляющего байта равен 1, то следующий байт данных надо повторить при распаковке столько раз, сколько указано в оставшихся 7 битах управляющего байта. Например, управляющий байт 10001001, значит следующий за ним байт надо повторить 9 раз. Если старший бит управляющего байта равен 0, то следующие байты надо взять без изменений – столько, сколько указано в оставшихся 7 битах. Например, управляющий байт 00000011 означает, что следующие за ним 3 байта надо взять без изменений.

Пример: Дана неупакованная последовательность из 12 байт

11111111 11111111 11111111 11111111 11111111 11110000
00001111 11000011 10101010 10101010 10101010 10101010

5 раз повторяется байт 11111111. Следовательно, надо записать управляющий байт 10000101, затем сам байт 11111111. Выигрыш – 3 байта. Затем идут 3 неодинаковых байта. Следовательно, управляющий байт будет 00000011, за ним следуют 3 уникальных байта. Всего получается 4 байта, т.е. получили проигрыш в 1 байт. Затем снова идет повторяющийся 4 раза байт 10101010. Значит, управляющий байт будет 10000100, за ним следует сам байт 10101010. Выигрыш – 2 байта. В результате упаковки получим последовательность:

10000101 11111111 00000011 11110000 00001111 11000011
10000100 10101010

В сумме – 8 байт вместо исходных 12. Общий выигрыш – 4 байта. Этот метод хорошо сжимает растровые графические изображения (bmp, tif, gif, pcx) и табличные данные. Но метод дает низкую степень сжатия файлов с малым числом повторяющихся байтов. Бывают данные, которые при уплотнении этим методом станут больше, чем исходные.

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

Одни из наиболее популярных программ-упаковщиков – PKZIP/PKUNZIP и ARJ. Эти программы обеспечивают высокую скорость работы и большую степень сжатия информации. Программа PKZIP/PKUNZIP стала фактическим стандартом сжатия файлов, а программа ARJ, обеспечивая почти такую же степень сжатия, отличается разнообразным сервисом и умеет создавать архивы, располагающиеся на нескольких дискетах (многотомные).

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

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

PKZIP режимы     имя_архива     [имена_файлов] …     
ARJ команда     режимы     имя_архива     [ каталог\]     [имена_файлов] …    

команда – одна буква, которая задает для программы ARJ вид выполняемой деятельности.

А — добавление файлов в архив
М – пересылка файлов в архив
U – обновление архива
L – просмотр оглавления архива
D – удаление файла из архива

режимы – указываются с предшествующим знаком «-» или «/», они задают или уточняют требуемые от программы архивации действия.

Режимы программы PKZIP:

-u – обновление архива
-m – пересылка в архив
-d – удаление файла из архива
-v – просмотр оглавления архива
-s – защита архива с помощью пароля
-x – исключение файла или группы файлов из обработки

Режимы программы ARJ:

-g – защита архива с помощью пароля
-v – создание многотомного архива

имя_архива — задает обрабатываемый архивный файл. Если расширение имени файла не указано, то подразумевается расширение .ZIP для программы PKZIP и .ARJ для программы ARJ;

каталог – для программы ARJ задает базовый каталог, в котором содержатся файлы, включаемые в архив;

имена_файлов – задают файлы, включаемые в архив. При задании имен файлов можно использовать символы * и ?. Если имена файлов не заданы, то подразумеваются все файлы из текущего каталога.

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

Примеры:

PKZIP myzip – добавление в архивный файл MYZIP.ZIP всех файлов из текущего каталога;

ARJ a myarj – добавление в архивный файл MYARJ.ARJ всех файлов из текущего каталога;

PKZIP docfiles *.doc a:\*.doc – добавление в архивный файл DOCFILES.ZIP всех файлов с расширением .DOC из текущего каталога и из корневого каталога на диске A:;

ARJ u a:myarc – обновление архивного файла A:MYARC.ARJ. В архивный файл добавляются все файлы из текущего каталога кроме тех, у которых в архиве имеются копии с более поздним временем создания или последней модификации;

PKZIP –f a:myarc b:\*.* — добавление в архив A:MYARC.ZIP новых версий файлов этого архива из корневого каталога диска B:.

Извлечение файлов из архива.
Для извлечения файлов из архивов, созданных программой PKZIP (.ZIP-файлов), используется программа PKUNZIP. А программа ARJ сама умеет извлекать файлы из своих архивов.

Программы PKUNZIP и ARJ имеют следующие форматы вызовов:

PKUNZIP режимы     имя_архива     [имена_файлов] …     
ARJ команда     режимы     имя_архива     [ каталог\]     [имена_файлов] …    

Примеры:

PKUNZIP a:archive –o – извлечение всех файлов из архива A:ARCHIVE.ZIP и помещение их в текущий каталог. Файлы на диске с тем же именем затираются без предупреждений.

ARJ e a:archive –jyo d:\ — извлечение всех файлов из архива A:ARCHIVE.ARJ в корневой каталог диска D:. Файлы на диске с тем же именем затираются без предупреждений.

PKUNZIP a:archive –f – обновление из архива A:ARCHIVE.ZIP версий файла из текущего каталога. Из архива извлекаются только более свежие версии тех файлов, которые уже имеются в текущем каталоге.

ARJ e –n a:archive c: — извлечение новых файлов из архива A:ARCHIVE.ARJ в текущий каталог на диске C:.

Для уменьшения размеров мультимедийных файлов используют процедуру сжатия.

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

Многие приемы сжатия аудио- и видеоинформации основываются на «обмане» органов чувств человека (зрение, слух) путем исключения избыточной информации, которую человек в силу своих физиологических особенностей не способен воспринять. Это компрессия с потерями. Эти методы не ставят цель абсолютно точно восстановить формы исходных сигналов. Их главная задача – достижение максимального сжатия сигнала при минимально заметных искажениях восстановленного после сжатия сигнала.
Приемы сжатия звука.

  1. Компадирование. Установлено, что если увеличивать громкость звука в 2, 4, 8 и т.д. раз, то человеческое ухо будет воспринимать этот процесс как линейное увеличение громкости звука. Изменение уровня громкости с 1 единицы до 2 единиц столь же заметно для человеческого уха, как и изменение громкости от 50 до 100 единиц. В то же время изменение громкости от 100 единиц до 101 единицы человеком практически не ощущается. Т.о., человеческое ухо логарифмирует громкость слышимых звуков. Поэтому при компадировании значение амплитуды звука заменяется логарифмом этого значения. Полученные цифры округляются, и для их записи требуется меньшее число разрядов. Для воспроизведения сигнала его подвергают обратному преобразованию – потенцированию.
  2. Очищение с помощью фильтров от неслышимых компонентов (например, убирают низкие басовые шумы). Затем вычисляются и удаляются замаскированные частоты, заглушенные другими мощными сигналами. Таким образом можно исключить до 70% информации из сигнала, практически не изменив качества его звучания.
  3. Для стереофонического сигнала применяют преобразование его в т.н. совмещенный стерео сигнал. Установлено, что слуховой аппарат человека может определить местоположение источника звука лишь на средних частотах, а высокие и низкие частоты звучат как бы отдельно от источника звука. Т.о., высокие и низкие частоты можно представить в виде монофонического сигнала. Это позволяет вдвое уменьшить объем информации, передаваемой на низких и высоких частотах.
  4. Маскирование во временной области. Тихий звук сразу после очень громкого не слышен. (Тиканье наручных часов некоторое время после выстрела пушки не услышишь.) Например, громкий звук длительностью 0,1 сек. может замаскировать тихие последующие звуки, запаздывающие на время до 0,5 сек., а, значит, их не надо сохранять.
  5. Маскирование в частотной области. Постоянно звучащий громкий синусоидальный сигнал «глушит» тихие сигналы близкие к нему по частоте, поэтому такие тихие звуки удаляют, используя алгоритмы спектрального анализа (БПФ).

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

Приемы сжатия видеоинформации.

Создается опорный кадр (I-кадр). Он формируется с помощью методов сжатия неподвижных изображений. I-кадры размещаются через каждые 10 – 15 кадров. Фрагменты изображений, которые изменяются, сохраняются при помощи расчетных кадров – P-кадров. Р-кадры содержат различия текущего изображения с предыдущим или последующим I-кадром и располагаются между опорными I-кадрами. Еще используются В-кадры. Они содержат усредненную информацию относительно двух ближайших (предыдущего и последующего) I-кадров или Р-кадров. Это позволяет предположительно восстанавливать отсутствующие кадры. В-кадры учитывают тот факт, что человек не способен за доли секунды рассмотреть детали движущегося изображения, поэтому можно формировать некоторое приблизительное изображение, учитывая информацию опорных кадров. Здесь происходит умышленный обман органов чувств человека.

Также используется то, что ошибки в изображении заметны глазом, если они превышают некоторый «порог заметности». Вариации цветности менее заметны, чем вариации яркости. Наиболее заметны изменения зеленого, затем красного, и наименее заметны изменения синего цвета. Используя эту особенность зрения человека, можно при упаковке изображения исключить данные о цвете, скажем, каждой 2-й точки, сохранив только ее яркость а при распаковке брать цвет соседней точки. Аналогично для группы соседних точек можно брать некоторый средний цвет.