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

Лекция 9 "Сжатие данных"

Характерной особенностью большинства типов  данных является их избыточность. Степень  избыточности данных зависит от типа данных. Например, для видеоданных  степень избыточности в несколько  раз больше чем для графических  данных, а степень избыточности графических  данных, в свою очередь, больше чем  степень избыточности текстовых  данных. Другим фактором, влияющим на степень  избыточности является принятая система  кодирования. Примером систем кодирования  могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий  и идей для высказывания мыслей. Так, установлено, что кодирование  текстовых данных с помощью средств  русского языка дает в среднем  избыточность на 20-25% большую чем  кодирование аналогичных данных средствами английского языка.

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

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

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

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

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

• JPEG - для графических данных;
• MPG - для для видеоданных;
• MP3 - для аудиоданных.

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

• GIF, TIFF - для графических данных;
• AVI - для видеоданных;
• ZIP, ARJ, RAR, CAB, LH - для произвольных типов данных.

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

• алгоритм RLE (Run Length Encoding);
• алгоритмы группы KWE(KeyWord Encoding);
• алгоритм Хаффмана.

Алгоритм RLE

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

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей  структурой: 1 4 2 2 3 1 4 3, где первое число  каждой пары чисел - это код данных, а второе - коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда  как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий  степень сжатия, можно вычислить  по формуле:

где Vx- объем  памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

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

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

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

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

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

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

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

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

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

Пусть задан  текст, в котором бурва 'А' входит 10 раз, буква 'В' - 8 раз, 'С'- 6 раз , 'D' - 5 раз, 'Е' и 'F' - по 4 раза. Тогда один из возможных  вариантов кодирования по алгоритму  Хаффмана приведен в таблицы 1.

Таблица 1.

Как видно  из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после  сжатия - 93 бит, то есть около 12 байт (без  учета длины словаря). Коэффициент  сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

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

Таблица 2.

Кроме того, современные архиваторы предоставляют  пользователю полный спектр услуг для  работы с архивами, основными из которых являются:

1. создание нового архива;
2. добавление файлов в существующий архив;
3. распаковывание файлов из архива;
4. создание самораспаковающихся архивов (self-extractor archive);
5. создание распределенных архивов фиксированного размера для носителей маленькой емкости;
6. защита архивов паролями от несанкционированного доступа;
7. просмотр содержимого файлов разных форматов без предварительного распаковывания;
8. поиск файлов и данных внутри архива;
9. проверка на вирусы в архиве к распаковыванию;
10. выбор и настройка коэффициента сжатия.

Контрольные вопросы

1. Какие факторы  влияют на степень избыточности  данных? 
2. Что такое архив? Какие программные средства называются архиваторами? 
3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми? 
4. Приведите примеры форматов сжатия с потерями информации. 
5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток? 
6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия? 
7. В чем состоит основная идея алгоритма RLE? 
8. В чем состоит основная идея алгоритмов группы KWE? 
9. В чем состоит основная идея алгоритма Хаффмана? 
10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.