Общие методы сжатия данных

В настоящий момент разработано огромное количество методов сжатия данных, каждый из которых имеет свои достоинства и недостатки. Метод, который называется кодированием длины серии (run-length encoding), дает наилучший эффект при сжатии данных, состоящих из длинных последовательностей одинаковых элементов. Действительно, при кодировании длины серии такая последовательность заменяется кодом, обозначающим повторяющийся элемент, и числом его повторений. Например, для того чтобы обозначить, что набор битов состоит из 253 единиц, за которыми следуют 118 нулей и 87 единиц, потребуется меньше места, чем для перечисления всех 458 битов.

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

Другим методом сокращения размера данных является частотно-зависимое кодирование (frequency-dependent encoding), в котором длина кода элемента информации обратно пропорциональна частоте использования этого элемента. Эти коды являются примерами кодов переменной длины (variable-length codes), что означает, что элементы информации представлены последовательностями разной длины, в отличие от таких кодов, как Unicode, в котором все символы представлены 16-битовыми последовательностями. В английском языке буквы е, t, a и i используются чаще, чем буквы z, q и х. Поэтому при кодировании текста на английском языке можно сохранить место в памяти, если использовать короткие наборы битов для первых букв и более длинные для вторых. В результате мы получим код, в котором текст будет иметь более короткое представление, чем имел бы в коде с фиксированной длиной, таком как ASCII или Unicode. Давид Хаффман известен как открыватель алгоритма, который широко используется для создания частотно-зависимых кодов. Поэтому почти все частотно-зависимые коды, используемые сегодня, — это коды Хаффмана (Huffman codes).

Хотя мы и назвали кодирование длины серии, относительное кодирование и частотно-зависимое кодирование общими методами кодирования данных, каждое из них все-таки имеет свою область применения. В отличие от них система сжатия Лемпеля-Зива (Lempel-Ziv encoding), названная в честь ее создателей Абрахама Лемпеля и Якоба Зива, является более универсальной системой. На самом деле пользователи Сети (см главу 3), возможно, видели или использовали обслуживающее программное обеспечение, в котором для создания сжатых файлов, называемых zip-файлами, применяется метод Лемпеля-Зива. Система кодирования Лемпеля-Зива является примером кодирования с адаптивным словарем (adaptive dictionary encoding). Словарем в этой системе является набор стандартных блоков, из которых построено сообщение, которое нужно сжать. Если бы мы хотели сжать текст на английском языке, то такими стандартными блоками были бы буквы алфавита. Если бы мы хотели сжать уже закодированные данные, то стандартными блоками были бы цифры 0 и 1. При адаптивном кодировании словарь может изменяться в процессе кодирования. Например, в случае с английским текстом, закодировав часть сообщения, мы можем решить добавить в словарь ing и the. Теперь каждый раз, когда в тексте встретится ing или the, они могут быть закодированы при помощи обращения к словарю один раз, а не три. Метод Лемпеля-Зива позволяет разумно и эффективно адаптировать словарь в процессе кодирования (или сжатия) данных.

Сжатие звука

Как мы уже говорили в разделе 1.4, одна секунда музыкального звучания, оцифрованная с частотой дискретизации 44 100 отсчетов в секунду, требует более одного миллиона битов в памяти. Такие требования допустимы для музыкальных записей, распространяемых на компакт-дисках, но попытка сочетать звук и изображение при записи фильмов бросает вызов возможностям технологий. Поэтому Экспертной группой по движущимся изображениям (The Motion Picture Experts Group), входящей в организацию ISO, был разработан метод сжатия данных, который значительно сокращает требования к памяти. Один из этих стандартов называется МРЗ (MPEG-1 Audio Layer-3) и позволяет достичь коэффициента сжатия от 12 до 1. При использовании стандарта МРЗ размер музыкальных записей может быть сведен к размеру, который может экономно передаваться по Сети. Эта возможность грозит коренным образом изменить индустрию звукозаписи.

Рассмотрим в качестве примера, как мы можем сжать сообщение, используя частный случай алгоритма Лемпеля-Зива, который называется LZ77. Начнем с простого цитирования начальной части сообщения. Затем представим оставшуюся часть сообщения в виде последовательности троек (содержащих два целых числа, за которым следует символ из сообщения). Каждая такая тройка описывает, как должна строиться следующая часть сообщения на основании предыдущей. Следовательно, словарь, из которого строится сообщение, состоит из самого сообщения.

Например, рассмотрим сжатое сообщение xyxxyzy (5. 4, х), состоящее из начального сегмента xyxxyzy, за которым следует тройка (5. 4, х). Цепочка xyxxyzy представляет собой часть сообщения, которая уже находится в развернутой форме. Для того чтобы развернуть оставшуюся часть сообщения, мы должны расшифровать тройку (5. 4, х), как показано на рис. 1.27. Первое число тройки показывает, на сколько символов нужно вернуться назад в развернутой цепочке. В нашем случае мы возвращаемся на пять символов назад до второго слева х. Теперь начинаем добавлять в конец развернутой цепочки символы, находящиеся в этой позиции. Второе число показывает, сколько символов из последовательности нужно добавлять. В нашем случае это число 4, поэтому мы дописываем символы xxyz в конец развернутой цепочки и получаем xyxxyzyxxyz. Наконец, добавляем в конец цепочки последний символ тройки. В нашем примере этот символ х, приписываем его в конец расшифрованной цепочки. В итоге получаем развернутое сообщение xyxxyzyxxyzx.

Теперь предположим, что нам нужно развернуть сообщение xyxxyzy (5. 4, х) (О, 0, w) (8. б. у). Начнем, как и раньше, с расшифровки первой тройки, получаем xyxxyzyxxyzx (0, 0, w) (8. 6, у). Теперь в результате разворачивания второй тройки получаем цепочку xyxxyzyxxyzxw (8, 6, у). Обратите внимание, что тройка (0, 0. w) использовалась потому, что символ w еще не встречался в сообщении. Наконец, расшифровываем последнюю тройку и получаем развернутое сообщение xyxxyzyxxyzxwzyxxyzy.

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

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

Сжатие изображений

В разделе 1.4 упоминалось, что в растровой графике, которая производится современными цифровыми преобразователями, изображение, как правило, представляется в формате три байта на один пиксел, что приводит к большим и трудно обрабатываемым файлам растровой графики. Для того чтобы уменьшить требования к памяти, было разработано много схем сжатия. Одна их них, разработанная компанией CompuServe, называется GIF (сокращенно от Graphic Interchange Format — формат графического обмена). Этот стандарт сжатия решает проблему путем сокращения количества цветов, которые могут быть приписаны пикселу, до 256. Это означает, что значение каждого пиксела можно представить с помощью одного байта, а не трех. Каждому из 256 значений пиксела при помощи таблицы, которая называется палитрой, ставится в соответствие определенное сочетание красного, зеленого и синего цветов. Изменяя палитру изображения, мы можем изменять цвета изображения.

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

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

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

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

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

Дополнительное пространство экономится при записи изменений яркости и цвета, а не их фактических значений. Причина этого, как и в методе «без потерь», заключается в том, что по мере сканирования изображения степень различия соседних пикселов можно представить более коротким двоичным кодом, чем тот, который потребовался бы для записи фактических значений цвета. В действительности, эти различия записываются при помощи математического метода, который называется дискретным косинусным преобразованием. Мы не будем рассматривать его в этой книге. Окончательный двоичный код затем сжимается при помощи метода с кодом переменной длины.

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

В заключение следует заметить, что исследования в области сжатия данных представляют собой широкое поле деятельности. Мы обсудили только два метода сжатия изображений из множества существующих. Кроме того, существуют различные техники сжатия звуковых и видеоданных. Например, группой Motion Picture Experts Group (MPEG — Экспертная группа по вопросам движущегося изображения), входящей в состав организации ISO, были разработаны методы, подобные тем, которые используются в стандарте JPEG, для того чтобы ввести стандарты кодирования (сжатия) движущихся изображений. Согласно этому алгоритму сначала кодируется первое изображение последовательности, подобно тому, как это делается в базисном стандарте JPEG, а затем при помощи методов относительного кодирования записываются оставшиеся изображения.