ТЕМА . ОСНОВЫ СЖАТИЯ ИНФОРМАЦИИ
В подавляющем числе случаев мы имеем дело с избыточной информацией об объекте, процессе, явлении. Под избыточностью будем понимать излишнюю информацию, наличие которой не уменьшает энтропию, другими словами не увеличивает количество знаний о системе.
Степень избыточности видеоданных обычно выше, чем у графических, а у графических, в свою очередь, выше, чем у текстовых.
Избыточность обычно связана с качеством информации. Телевизор можно смотреть и при наличии помех. Если в тексте допущена опечатка, в большинстве случаев смысл изложенного не претерпевает искажения.
Посчитаем, к примеру, сколько займет памяти графическое изображение. Пусть его разрешение — 800х600 пиксел, а число оттенков цвета около 16 тысяч (High Color), т. е. цвет каждого пиксела представляется двухбайтовым кодом. 800×600=480000 элементов. 480000×2 байт = 960000 байт – это чуть меньше 1 мегабайта. Кажется, не так много – на лазерном диске поместится больше 650 таких картинок. Ну, а если речь идет о фильме (сменяющиеся картинки 800х600х16)? Стандартная скорость кинопроекции – 24 кадра в секунду. Значит, на компакт-диске можно записать фрагмент длительностью 650:24=27 секунд. Нездорово?! А ведь это далеко не единственный случай, когда информации слишком много. Таким образом, одна из причин использования сжатия данных – желание поместить больше информации в память того же объема. Есть и вторая причина. Сжатие информации ускоряет ее передачу по коммуникациям (локальным и глобальным сетям).
К данным имеющим избыточность можно применить методы сжатия (уплотнения, архивирования) для уменьшения необходимых объемов при их хранении.
В ВТ можно сжимать файлы, папки и диски.
Сжатие файлов применяют, как правило, для передачи по сетям, для транспортировки на носителях малой емкости (ГМД).
Сжатие папок используется, в основном, для резервного хранения информации.
Сжатие дисков служит для увеличения рабочего пространства носителя, правда существенно замедляет работу.
Мы будем рассматривать только сжатие первых двух объектов.
Существует несколько методов сжатия (компрессии) данных. Все их можно разделить на две группы сжатие без потерь и с потерями. В первом случае распакованное сообщение точно повторяет исходное. Естественно, так можно обрабатывать любую информацию. Сжатие же с потерями возможно только в тех случаях, когда допустимы некоторые искажения – какие именно, зависит от конкретного типа данных.
Практически все методы сжатия без потерь основаны на одной из двух довольно простых идей.
Одна из них впервые появилась в методе сжатия текстовой информации, предложенном в 1952 году Хафманом. Стандартно каждый символ текста кодируется одним байтом. Но дело в том, что одни буквы встречаются чаще, а другие реже. Например, в тексте, написанном на русском языке, в каждой тысяче символов в среднем будет 90 букв о, 72 – е и только 2 – ф. Больше же всего окажется пробелов: сто семьдесят четыре. Если для наиболее распространенных символов использовать более короткие коды (меньше 8 бит), а для менее распространенных – длинные (больше 8 бит), текст в целом займет меньше памяти, чем при стандартной кодировке.
Несколько методов сжатия основаны на учете повторяющихся байтов или последовательностей байт. Простейший из них – RLE (Run-Length Encoding – кодирование длины последовательности) – широко используется при сжатии изображений. В файле, сжатом таким методом, записывается, сколько раз повторяются одинаковые байты. Например, вместо RRRRRGGGBBBBBBRRRBBRRRRRRR будет храниться 5R3G6B3R2B7R (на самом деле хранятся двоичные коды коэффициентов повторения и коды цветов). Очевидно, что такой метод лучше всего работает, когда изображение содержит большие участки с однотонной закраской.
Другие методы основаны на том, что если некоторая последовательность байт встречается в файле многократно, ее можно записать один раз в особую таблицу, а потом просто указывать: взять столько-то байт из такого-то места таблицы На этой идее основан широко использующийся для сжатия различных данных метод LZW, названный так по первым буквам фамилий его разработчиков – Лемпеля (Lempel), Зива (Ziv) и Велча (Welch).
Методы сжатия без потерь уменьшают размер файлов не очень сильно. Обычно коэффициент сжатия не превосходит 1/3-1/4. Гораздо лучших результатов можно добиться, используя сжатие с потерями. В этом случае на основе специальных исследований определяется, какой информацией можно пожертвовать.
Например, установлено, что человеческое зрение очень чувствительно к изменению яркости и гораздо меньше, к цветовому тону. Поэтому при сжатии фотографических изображений (и вообще, изображений, в которых нет резких границ между цветами) можно исключить информацию о цвете части пикселов. При распаковке же определять его по соседним. На практике чаще всего применяется метод, использующий более сложную обработку, – JPEG (Joint Photographic Experts Group – объединенная группа экспертов по фотографии, разработавшая одноименный метод сжатия изображений.). Он позволяет сжимать изображение в десятки раз. С учетом особенностей восприятия человеком информации строятся также методы сжатия с потерями видеоизображения. Наиболее распространены сейчас методы сжатия с потерями видеоизображения – MPEG (Moving Picture Experts Group – группа экспертов по движущимся изображениям) и звука – MP3 (Music Packing).
Естественно, сжатие с потерями может использоваться только программами, предназначенными для обработки конкретных видов данных (например, графическими редакторами). А вот методы сжатия без потерь применяются и для любых произвольных файлов.
Заметим, что не стоит пытаться сжать файлы, которые уже были сжаты: размер их либо уменьшится совсем незначительно, либо даже увеличится.
Типы файлов с данными, полученными от сжатия с потерей информации:
JPG – для графических данных;
MPG – для видеоданных;
MP3 – для звуковых данных.
Типы файлов с данными, с возможностью восстановления информации:
TIF, PCX – для графических данных;
AVI – для видеоданных.
ZIP, ARJ, RAR, LZH, CAB – для любых данных
Эффективность архивации определяется коэффициентом (степенью) сжатия:
1 – отношение размера архива (отдельного файла) к объему неархивированных данных (исходному файлу).
