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

Примечание. Менее очевидное достоинство архивирования состоит в том, что один большой архивный файл более экономно расходует дисковое пространство, чем множество маленьких. Секрет в том, что любая операционная система пишет информацию блоками, причем в последнем из них может быть занята очень незначительная часть (эффект особенно заметен, когда файл мал и блок единственный). Если вам кажется, что это пренебрежимые мелочи, советую прочитать стр.69-72 замечательной книги Лу Гринзоу [1].

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

Рассмотрим наиболее распространенные идеи, лежащие в основе обратимого сжатия.

Неравномерное кодирование.

Традиционное представление данных в ОЗУ является равномерным, т.е. каждому элементу информации соответствует одинаковый объем. Так, символ в стандарте ASCII занимает 1 байт, целое число – 2 или 4 байта, а 1 пиксел при наилучшей цветопередаче – 3 байта. Такой метод хранения обеспечивает максимально простое и быстрое извлечение данных в процессе обработки. Тем не менее, ради скорости приходится жертвовать объемом, который оказывается неоптимальным. Дело в том, что не все символы или цвета пикселов встречаются одинаково часто. Поэтому напрашивается такой способ кодирования, при котором чаще встречающимся символам ставится в соответствие меньшее количество битов, чем редко встречающимся. Такое неравномерное кодирование приводит к существенному сокращению суммарного числа битов в данных.

Для примера рассмотрим простейшую фразу из букваря “мама мыла раму”. Очевидно, что в ней буквы “м” и “а” встречаются гораздо чаще, чем “ы” или “у”. Следовательно, для кодирования входящих в текст символов можно применить следующую таблицу (пробелы не учитываются!) [2]:

буква	м	а	р	л	у	ы
код	00	10	11	010	0110	0111

В результате обсуждаемая фраза примет вид¹

00 10 00 10 00 0111 010 10 11 10 00 0110

Мы видим, что ее длина составила 29 бит, т.е. в среднем 2.4 бита на один символ. Это существенно меньше, чем при равномерном стандартном ASCII коде.

Пример выигрыша от применения неравномерного кодирования в случае более полного алфавита можно найти в новом издании учебника [3]. Простое и наглядное доказательство эффективности метода при наличии большого количества пробелов в тексте приведено в [4].

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

Описанные выше идеи лежат в основе метода Хафмана, предложенного в 1952 году. Долгое время он оставался наиболее популярным методом в программах-архиваторах. В 1977 году два ученых из Израиля А. Лемпел и Я. Зив предложили принципиально иной подход к проблеме. Они выдвинули идею формирования словаря последовательностей, часто встречающихся в данных. Важно, что если формировать такой словарь определенным способом, то программа декодирования сможет его восстановить непосредственно из данных.

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

Блочное кодирование.

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

Приведем еще один (довольно убедительный) пример из учебника [2]. Пусть имеется словарь языка, содержащий n = 16000 слов³. Для того, чтобы каждому из них поставить в соответствие равномерный двоичный код, потребуется 14 бит (2¹⁴ > n). Учитывая, что средняя длина слова в русском языке 6.3 символа (включая пробел), получим прекрасный показатель 14/6.3 ≈ 2.2 бита на один символ, что явно лучше характеристик ASCII.

Групповое кодирование (учет повторений).

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

Рис.1

Рассмотрим одно из горизонтальных сечений рисунка, отмеченное черной прямой. Как отчетливо видно, в нем после достаточно большого количества синих точек имеется одна желтая, а затем снова следует группа синих. Очевидно, что вместо хранения информации о каждой точке, можно просто закодировать, что 22 точки имеют синий цвет, 1 – желтый⁴ и т.п. В результате в нашем случае вместо 38 чисел, характеризующих цвет каждого пиксела, оказывается достаточно всего трех пар, указывающих количество точек и их цвет.

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

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

Разностное кодирование.

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

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

Наиболее известные стандарты необратимого сжатия базируются на рекомендациях группы профессиональных экспертов по качеству графических изображений и цветопередаче JPEG (Joint Photographic Experts Group). Данные рекомендации существенным образом учитывают особенности человеческого зрения.

Примечание. Строго говоря, несмотря на укоренившуюся терминологию, JPEG – это не сам формат файлов, а техника сжатия изображений.

Методы, применяемые в JPEG, опираются на достаточно сложную математику и выходят за рамки нашего обсуждения. Их суть заключается в том, что в каждом небольшом квадратном участке изображения (обычно 8x8 пикселов) производится разложение на гармонические составляющие⁵. Затем гармоники с наиболее высокими частотами, ответственные за резкие переходы в изображении, округляются. Фотографические и полутоновые изображения, в которых отсутствуют резкие границы и происходит плавное перетекание цветов, от такой обработки практически не пострадают, зато цвета точек, получившиеся в результате усреднения, поддаются сжатию во много раз лучше, чем в исходном изображении. В то же время, фрагменты, содержащие резкие цветовые переходы (рамки, тексты и т.п.) в процессе описанной процедуры искажаются весьма заметно (рис.2).

Рис.2

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

Заметим, что приемы сжатия изображений согласно идеям JPEG во многом совпадают с описанными ранее для кадров видео [6].

---

1 существенно, что приведенная последовательность нулей и единиц однозначно расшифровывается и не нуждается в каком-либо разделении - пробелы в тексте статьи поставлены исключительно для удобства восприятия!

2 разбиение текста на блоки может быть любым, включая блоки из одинакового количества символов

3 если верить известному произведению Ильфа и Петрова, это превышает словарный запас Шекспира

4 если цвета всех точек на рисунке разные, то при кодировании по указанному принципу файл может даже увеличиться; впрочем, никто не запрещает одиночные пикселы кодировать традиционным образом, а повторяющиеся - с указанием количества точек

5 из математики известно, что любая функция может быть представлена в виде суммы тригонометрических функций; впервые это утверждение высказал французский ученый Жан Батист Жозеф Фурье (1768-1830), хотя ему и не удалось представить убедительное доказательство; тем не менее, Фурье существенно развил применение гармонического анализа к физическим процессам

Литература

1. Гринзоу Л. Философия программирования для Windows 95/NT. СПб.: Символ-плюс, 1997, 640 с.
2. Стариченко Б.Е. Теоретические основы информатики. М.: Горячая линия-Телеком, 2003, 312 с.
3. Семакин И.Г. Информатика. Базовый курс. 7-9 классы / И.Г. Семакин, А.Л. Залогова, С.В. Русаков, Л.В. Шестакова. 2-е изд., испр. и доп. М.: БИНОМ, 2004, 390 с.
4. Информационная культура: Кодирование информации, информационные модели. 9-10 классы: Учеб. для общеобразоват. Учеб. заведений. М.: Дрофа, 2000, 208 с.
5. Кенцл Т. Форматы файлов Internet. СПб.: Питер, 1997, 320 с.
6. Еремин Е.А. Представление видео информации в ЭВМ. / Информатика, N 46, 2004, с.16-17.
   (см. здесь)