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

СЖАТИЕ ДАННЫХ*

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

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

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

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

Хотя обсуждавшиеся выше методы кодирования были представлены как технологии сжатия данных общего назначе- ния, тем не менее, каждый из них имеет собственную сферу применения. В противоположность этому, системы, основанные на использовании метода кодирования Lempel-Ziv (названного в честь его создателей Абрахама Лемпеля (Abraham Lempel) и Джэкоба Зива (Jacob Ziv), действительно являются системами сжатия данных общего назначения. Многие пользователи Internet (глава 3), несомненно, уже встречали и даже использовали такие универсальные программы сжатия данных произ- вольного типа, как zip и unzip, в которых применяется технология Lempel-Ziv.

Системы кодирования по методу Lempel-Ziv используют технологию кодирования с применением адаптивного словаря (adaptive dictionary encoding). В данном контексте термин "словарь" означает набор строительных блоков, из которых созда- ется сжатое сообщение. Если сжатию подвергается английский текст, то строительными блоками могут быть символы алфа- вита. Если потребуется уменьшить размер данных, которые хранятся в компьютере, то компоновочными блоками могут стать нули и единицы. В процессе адаптивного словарного кодирования содержание словаря может изменяться. Например, при сжатии английского текста может оказаться целесообразным добавить в словарь окончание ing и артикль the. В этом случае место, занимаемое будущими копиями окончания ing и артикля the, может быть уменьшено за счет записи их как одиночных ссылок вместо сочетания из трех разных ссылок. Системы кодирования по методу Lempel-Ziv используют изо- щренные и весьма эффективные методы адаптации словаря в процессе кодирования (или сжатия). В частности, в любой мо- мент процесса кодирования словарь будет состоять из тех комбинаций, которые уже были закодированы (сжаты).

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

abaabrb (5, 4, a)

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

a   b    a     a     b     r     b

а)

a  b  a  a  b  r b

б)

a  b  a  a  b  r  b  a  a  b r

в)

a  b  a  a  b  r  b  a  a  b  r a

г)

Рис. 1.19. Процесс распаковки сообщения abaabrb (5, 4, a):

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

сообщения символа, указанного в триплете

В данном случае необходимо отсчитать в обратном направлении 5 символов, и мы попадем на второй слева символ a уже распакованной строки. Второе число в триплете задает количество последовательных символов справа от начального, кото- рые составляют добавляемый сегмент. В нашем примере это число 4, и это означает, что добавляемым сегментом будет

aabr. Копируем его в конец строки и получаем новое значение распакованной части сообщения:

abaabrbaabr

Наконец, последний элемент (в нашем случае это символ a) должен быть помещен в конец расширенной строки, в ре- зультате чего получаем полностью распакованное сообщение:

abaabrbaabra

Теперь предположим, что сжатая версия текста имеет такой вид:

abaabrb (5,4, a)(0,0,d)(8,6, b)

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

abaabrbaabra (0,0,d) (8,6, b)

Теперь распакуем второй триплет и получим следующий результат:

abaabrbaabrad (8,6, b)

Обратите внимание, что второй триплет (0,0, d) использовался только потому, что символ d еще не встречался в этом тексте. И наконец, распакуем третий триплет и получим полностью распакованное сообщение:

abaabrbaabradrbaabrb

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

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

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

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

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

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

К сожалению, при использовании режима "без потерь" создаваемые файлы растровых изображений настолько велики, что они с трудом обрабатываются методами современной технологии, а потому и применяются на практике крайне редко. Большинство существующих приложений использует другой стандартный метод формата JPEG – режим "базовых строк". В этом режиме каждый из пикселей также представляется тремя составляющими, но в данном случае это уже один компонент яркости и два компонента цвета. Грубо говоря, если создать изображение только из компонентов яркости, то мы увидим черно-белый вариант изображения, так как эти компоненты отражают только уровень освещенности пикселя.

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

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

Дополнительной экономии места можно достичь с помощью записи информации, определяющей изменения компонен- тов яркости и цвета, а не их абсолютных значений. В этом случае, как и в режиме "без потерь" формата JPEG, отправной точкой является тот факт, что при сканировании изображения уровень различий между соседними пикселями может быть закодирован с использованием меньшего количества битов, чем при записи самих характеристик отдельных пикселей. (В действительности эти изменения кодируются с помощью математического метода, называемого дискретным косинусным преобразованием и применяемого к блокам размером 8 ´ 8 пикселей.) Полученная в результате битовая комбинация допол- нительно сжимается с использованием кодов переменной длины. В результате применение режима "базовых строк" формата JPEG позволяет получать цветные изображения приемлемого качества, размер которых находится в соотношении 1 : 20 с размером растровых файлов, в которых для представления каждого пикселя используется трехбайтовая схема, используемая в большинстве существующих сканеров.

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

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

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

Вопросы для самопроверки

1.     Ниже представлен текст сообщения, сжатый с использованием метода LZ77. Как будет выглядеть распакованное со- общение?

101101011 (7, 5, 0) (12, 10, 1) (18, 13, 0)

2.     Несмотря на то что мы не очень подробно рассматривали алгоритм кодирования данных по методу LZ77, все же по- пытайтесь выполнить сжатие следующего сообщения:

bbabbbaababaababaababaaa

3.     Выше утверждалось, что формат GIF позволяет лучше представлять цветные мультипликационные изображения, чем формат JPEG. Объясните, почему это действительно так.

4.     Какое наибольшее количество байтов потребуется для представления изображения размером 1024 ´ 1024 пикселей, если использовать формат GIF? Что можно сказать относительно использования режима "базовых строк" формата JPEG?

5.     Какие особенности человеческого глаза используются в режиме "базовых строк" формата JPEG?