1. Обзор подходов к сжатию информации

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

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

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

Простейший вариант учета цепочек – так называемое «кодирование повторов» или код RLE, когда последовательность одинаковых символов заменяется парой – “код символа + количество его повторов в цепочке”. В большинстве случаев цепочки  одинаковых символов встречаются нечасто. Однако, например, при кодировании черно-белых растровых изображений, каждая строка которых состоит из последовательных черных или белых точек, такой подход оказывается весьма эффективным (он широко применяется при факсимильной передаче документов). Кроме того, кодирование повторов нередко используется как составной элемент более сложных алгоритмов сжатия.

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

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

К методам сжатия изображений относятся «блочный» алгоритм JPEG основанный на независимом «огрублении» небольших фрагментов изображений (квадраты 8х8 пикселей). Здесь с ростом степени сжатия проявляется мозаичность изображения. Блочный метод JPEG (разработанный специальной группой международного комитета по стандартизации) получил сейчас повсеместное распространение и ниже мы рассмотрим его подробнее. Достигается степень сжатия – в среднем в десятки раз.

При волновом сжатии в отличие от блочного изображение как бы «размывается» (чем выше степень сжатия, тем более нечетки границы и детали). При передаче данных получаемое изображение постепенно «проявляется» в деталях. Это позволяет получателю самому выбирать необходимый компромисс между качеством и скоростью получения изображения, что очень удобно, например в Интернет. К тому же «размытость» не столь резко воспринимается глазом как потеря качества по сравнению с «мозаичностью». Так что при субъективно близком уровне качества волновой метод дает  большую степень сжатия по сравнению  с «блочным». Именно такой подход реализован в новом стандарте JPEG 2000.

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

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

Что касается методов сжатия звука от произвольного источника, мы рассмотрим их ниже.

2. Эффективное посимвольное кодирование для сжатия данных.

Основные моменты сводятся к следующему:

• идея такого кодирования базируется на том, чтобы использовать для часто встречающихся символов более короткие кодовые цепочки, а для редких – более длинные. В результате средняя длина кода будет меньше, чем при равномерном кодировании;
• согласно теореме Шеннона, наилучшее кодирование позволяет сократить l_ср. до величены энтропии Н, подсчитанной для данного набора символов;
• неравномерное кодирование позволяет автоматически устранить избыточность, связанную с тем, что количество символов в алфавите может быть не кратно степени двойки (так, например, чтобы закодировать одинаковым числом разрядов 5 разновидностей символов потребуется 3 бита, так же как и для 8 символов).

Идея неравномерного кодирования, в котором длина кодовой цепочки зависит от частоты появления соответствующего символа, реализована еще в знаменитой «азбуке Морзе». Однако там наряду с «точками» и «тире» использовался третий кодовый символ – разделитель «пауза». Если ограничиться только «O» и «1», то при построении кода необходимо учесть дополнительное требование: чтобы все кодовые цепочки однозначно выделялись в непрерывном потоке битов, ни одна из них не должна входить как начальный участок в кодовую, цепочку  другого символа. Такое свойство кода называется префиксностью.

Наибольшее распространение получил способ построения эффективного кода предположенный Хаффменом. Рассмотрим его на примере. Пусть задан алфавит из 5 разновидностей символов Z₁ – Z_{5, и} их вероятности. В таблице 5.1 наряду с этими исходными данными приведены так же результаты кодирования по Хаффмену: кодовые цепочки K_i их длинны l_i. Процедуру построения кода иллюстрирует таблица и рисунок 1

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

Пример кода Хаффмена

                                                                     1

Zi	Pi	Ki	li
Z1   Z2   Z3   Z4   Z5	0,25   0,17   0,08   0,35   0,15	10   00   010   11   011	2   2   3   2   3
			lср

На втором этапе строится «дерево кода», ветви которого отображают в обратном порядке процесс «объединения вероятностей». При построении дерева принимается правило соответствия большей вероятности одному из направлений ветви (например «левому») и определенному значению бита кода (например, «1») . Цепочки битов от «корня» до конца каждой ветви соответствуют кодам исходных символов 

Таблица 2. Объединение вероятностей символов

Zi	Pi	Шаги объединения				Ki
		1	2	3	4
Z1   Z2   Z3   Z4   Z5	0,35   0,25   0,17   0,15   0,08	0,35   0,25   0,23   0,17	0,40   0,35   0,25	0,60   0,40	1,00	11   10   00   011   010

 

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

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

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

3. Сжатие информации с учетом цепочек символов по Лемпелю-Зиву

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

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

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

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

Уточним дополнительно некоторые моменты:

коды координат цепочки  и коды отдельных символов различаются битовыми признаками (например, в первом случае – 1, во втором –0) ;

поскольку цепочки находятся чаще в начале словаря, и чаще бывают короткими, дополнительный выигрыш получают за счет статистического кодирования (по Хаффмену) их «адресов» и «длин»;

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

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

Добавим, что алгоритм Лемпеля-Зива используется в большинстве популярных программ-архиваторов (в том числе, например, в zip, rar, arj и их windows – версиях).

Различие скорости и эффективности кодирование-декодирование определяются в основном особенностями программной реализации.

Алгоритм Лемпеля-Зива требует большого количества вычислительной работы. Его модификация – алгоритм Лемпеля-Зива-Велча является менее трудоемким, хотя и дает несколько худшие результаты по сжатию.

4.  Сжатие изображений по блочному алгоритму JPEG

Как известно, все множество цветовых оттенков может быть задано различными пропорциями яркости трех цветовых составляющих, – в частности, красного (Red – R),  зеленого (Green – G) и голубого (Blue – B). В памяти компьютера изображение чаще всего представляется как матрица (растр) точек –  пикселей.

(Наряду с таким «растровым»  представлением существует и так называемое «векторное», когда элементы изображения – кривые – описываются математическими уравнениями. К «векторному» описанию изображения применимы способы сжатия данных без потерь. Здесь мы будем говорить о методах, применяемых по отношению к растровым изображениям).

 Каждому пикселю отвечает три кодовых слова, характеризующих яркость составляющих RGB. Чаще всего для каждого из них отводится один байт (именно так кодируются цвета пикселей например в популярных графических форматах tif и bmp).

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

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

1. Почему сжатие с потерями используется в основном как кодирование изображений и звука?
2. Поясните суть методов «кодирования повторов» и кодирование по Лемпелю-Зиву.
3. В чем отличия «блочного» и «волнового» кодирования изображений в стандарте JPEG?
4. Какие преимущества при сжатии звуковой информации дает детальное знание особенностей источников звука.
5. Неравномерное кодирование особенно эффективно, когда когда объем алфавита n не равен степени двойки. Объясните это.
6. Что такое «префиксность» применительно к кодированию?
7. Поясните процедуру построения кода Хаффмена ?
8. В чем особенности однопроходного и двухпроходного кода Хаффмена?