ЛЕКЦИЯ №4 ОПТИМАЛЬНОЕ И ЭФФЕКТИВНОЕ КОДИРОВАНИЕ

4.1 Понятие кодирования. Кодовое дерево.

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

Если исходный алфавит содержит m букв, то для построения равномерного кода с использованием D кодовых букв необходимо обеспечить выполнение следующего условия:

,

где n- количество элементов кодовой последовательности.

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их в коды как n-разрядное число в D-ичной системе счисления.

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

.

При этом - энтропия кода одной буквы в n - разрядном D- ичном числе. Таким образом, информационные возможности кода используются не полностью.

Пример. Для двоичного 5-рарядного кода букв русского алфавита информационная емкость составляет 5 бит, =4,35 бит.

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

Если i-ая буква, вероятность которой p_i, получает кодовую комбинацию длины n_i, то средняя длинна кода или средняя длина кодового слова равна:

Введем понятие кодового дерева, которым часто пользуются при рассмотрении Известно, что любую букву или событие, содержащиеся в алфавите источника или в сообщении, можно разложить на последовательности двоичных решений с исходами «ДА»=1 и «НЕТ»=0, причем без потери информации. Таким образом, каждой букве исходного алфавита может быть поставлена в соответствие или, как говорят, приписана некоторая последовательность двоичных символов - 0 или 1.А такую последовательность называют кодовым деревом. При этом потери информации не происходит, так как каждое событие может быть восстановлено по соответствующему кодовому слову.

C₁,C₂,…,C₁₁-кодовые слова. Уровень кодового дерева определяет длину кодового слова.

4.2 Теорема кодирования источников, неравенство Крафта.

Префиксный код.

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

Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H(X) существует D- ичный префиксный код, в котором средняя длинна кодового слова , удовлетворяет неравенству:

В префиксном коде никакое кодовое дерево не является префиксом другого кодового дерева. Это значит, что поток кодовых слов может использоваться без специального разделения этих слов. Например, если код 101 является кодом какой-то буквы, то в качестве кодов других букв нельзя использовать следующие комбинации: 1,10,10101, …и т.д.

Из теоремы Шеннона следует, что тем ближе длина кодового слова к энтропии источника, тем более эффективно кодирование. В идеальном случае, когда , код называют эффективным. Эффективность кода оценивается величиной:

.

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

Для существования однозначно декодируемого D- ичного кода, содержащего k кодовых слов с длинами n₁,n₂,…,n_k, необходимо и достаточно, чтобы выполнялось неравенство Крафта:

4.3 Методы оптимального кодирования. Сжатие данных.

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

1.Сжатие без потерь - устранение избыточности информации, не связанное с ее изменением, принципиально существенным для пользователя.

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

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

Методы сжатия данных были разработаны как математическая теория, которая до первой половины 80-х годов 20 века мало использовалась в компьютерной технике.

Методы или алгоритмы сжатия данных без потерь можно разделить на:

1.Статистические методы или алгоритмы. Например, методы Шеннона - Фано, Хаффмана и др.

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

2.Адаптивные методы или алгоритмы. Например, модифицированные коды Хаффмана, арифметическое кодирование и др.

Здесь распределение вероятностей символов сначала считается равномерным на заданном интервале, а потом оно меняется по мере накопления статистики.

3.Динамические методы или алгоритмы. Они являются универсальными и не нуждаются в априорной статистике. Например, метод Лемпела- Зива.

4.3.1 Метод кодирования Шеннона - Фано.

Буквы исходного алфавита записываются в порядке убывания их вероятностей. Это множество разбивается так, чтобы вероятности двух подмножеств были примерно равны. Все буквы верхнего подмножества в качестве первого символа кода получают 1, а буквы нижнего подмножества-0. Затем последнее подмножество снова разбивается на два подмножества с соблюдением того же условия и проводят то же самое присвоение кодовым элементам второго символа. Процесс продолжается до тех пор, пока во всех подмножествах не останется по одной букве кодового алфавита.

Пример.

Буква xi	Вероятности pi	Кодовая последовательность	Длина кодового слова ni	pini	-pilog2pi
Номер разбиения
x1	0,25						0,5	0,5
x2	0,25		0				0,5	0,5
x3	0,15	0					0,45	0,4
x4	0,15			0			0,45	0,4
x5	0,05	0			1		0,2	0,2
x6	0,05						0,2	0,2
x7	0,05			0			0,2	0,2
x8	0,05				0		0,2	0,2

= = (0,25*2+0,25*2+0,15*3+0,15*3+0,05*4+0,05*4+0,05*4+0,15*4)=2,7 бит

= - (2*0,25*log₂ 0,25 + 2*0,15*log₂ 0,15 + 4*0,05*log₂0,05) = 2,7 бит

= 1

Метод Шеннона - Фано не всегда приводит к однозначному построению кода, так как при разбиении на подмножества можно сделать большей по вероятности как верхнюю, так и нижнюю часть, следовательно, такое кодирование хотя и является эффективным, но не всегда будет оптимальным.

4.3.2 Метод кодирования Хаффмана.

Этот метод всегда дает оптимальное кодирование в отличие от предыдущего, так как получаемая средняя длина кодового слова является минимальной.

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

Пример.

= = (4*0,05 +3*0,15+4*0,05+0,4+3*0,2+3*0,15)= 2,3 бит

= - (0,4log₂ 0,4+0,2 log₂ 0,2+2* 0,15 log₂0,15 +2*0,05 log₂0,05)= - (0,52 + 0,46+ 2*0,4+2*0,2)= 2,18

= 1,05

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

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

Недостатки кода:

1.Различные длины кодовых слов приводят к неравномерным задержкам кодирования.

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

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

4.3.3. Арифметическое кодирование.

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

Поэтому хотелось бы иметь такой алгоритм кодирования, который позволял бы кодировать символы менее чем 1 бит. Одним из таких алгоритмов является арифметическое кодирование, представленное в 70-х годах 20 века. При рассмотрении этого алгоритма будем исходить из того факта, что сумма вероятностей символов (и соответствующим им относительным частотам появления этих символов), всегда равна 1.Отсительные частоты появления могут определяться путем текущих статистических измерений исходного сообщения (это первый « проход» процедуры кодирования). Особенностью арифметического кодирования является то, что для отображения последовательности символов на интервале [0,1] используются относительные частоты их появления.

Пример определения частоты появления символов в сообщении

BANANANBAB.

Результатом такого отображения является сжатие символов или посимвольное сжатие в соответствии с их вероятностями, т.е. результатом арифметического сжатия будет некоторая дробь из интервала [0,1], который представляется двоичной записью (это второй «проход» процедуры кодирования). Заметим, что такой двухпроходный алгоритм может быть реализован в ранее рассмотренных кодах Шеннона – Фано и Хаффмана.

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

Эффективность арифметического кодирования растет с увеличением длины сжимаемого сообщения. Заметим, что в кодах Шеннона – Фано и Хаффмана такого не происходит.

Арифметическое кодирование заключается в построении отрезка , однозначно определяющего заданную последовательность символов в соответствии с их вероятностями. Объединение всех отрезков, пересекающихся только в граничных точках, для вероятностей каждого символа должно образовывать формальный интервал [0,1]. Для последнего полученного интервала, соответствующего последнему принятому символу сообщения, находит число, принадлежащее его внутренней части. Это число в двоичном представлении и будет кодом для рассматриваемой последовательности.

Пример. Пусть задан алфавит X={a ,b}, p(a) = , p(b) = . Необходимо закодировать сообщение {aba}.

Шаг кодирования	Поступающий символ	Интервал
	нет	[ 0,1 ]
	a	[ 1]
	b	[ ]
	a

				a

2.

		b		a

1. ,

2. ,

3.

		b		a

1. ,

2. ,

3.

В таком алгоритме в конце сообщения должен стоять некий маркер, обозначающий конец сообщения.

Код сообщения {aba}=10000.

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

4.3.4 Алгоритм универсального кодирования методом Лемпела-Зива.

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

Первый алгоритм разработан в 1971 году в Израиле Лемпелом и Зивом (LZ 77). Одной из причин популярности алгоритма LZ 77, а также семейства алгоритмов LZ 77, является их исключительная простота при высокой эффективности сжатия.

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

Алгоритм пытается найти в словаре фрагмент сообщения, совпадающий с содержимым буфера. На практике размер словаря составляет несколько кбайт, а размер буфера - до 100 байт. В результате кодирования формируется совокупность групп по три элемента в каждой < a,l,z >, где a- относительный адрес в словаре, т.е. смещение в словаре относительно его начала до первого символа фрагмента, с которым совпадает содержимое буфера; l - число совпадений элементов буфера и словаря; z –первый несовпадающий со словарем символ в буфере.

Пример. КРАСНАЯ КРАСКА

Для данного кода длину кодовой комбинации можно определить по следующей формуле:

- операция округления в большую сторону.

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

1.Часто повторяющиеся цепочки кодируются очень эффективно.

2.Редко повторяющиеся символы и их последовательности с течением времени удаляются из словаря.

3.Можно доказать, что словарное кодирование асимптотически оптимально, т.е. что длина кодового слова стремится к энтропии этого текста.

4.Практически достижимая степень сжатия для этих кодов 50-60 %.

В семейство алгоритмов LZ входит несколько моделей, которые модифицированы различными авторами в аспекте механизмов формирования кодовых групп, но во всех механизмах используется словарь. В настоящее время наибольшее распространение получил алгоритм LZW (1984 г.). В этом алгоритме длина кода уменьшается, так как не используется буфер. А кодирование проводится только по словарю, следовательно, кодовая группа определяется только длиной словаря.

Декодирование словарного кода происходит в обратном порядке и упрощается тем, что не требует поиска совпадений в словаре.

4.3.5 Особенности программ- архиваторов.

Если коды алгоритмов типа LZ передать для кодирования алгоритму Хаффмана или арифметическому алгоритму, то полученный двухшаговый алгоритм дает результат сжатия, подобный случайным программам-архиваторам, таким, как GZ, AGZ, PK zip. Наибольшую степень сжатия дают двухпроходные алгоритмы, которые последовательно сжимают два раза исходные данные, но они соответственно и работают в два раза медленнее. Большинство программ- архиваторов сжимают каждый файл по отдельности, хотя некоторые способны это делать в потоке файлов, что дает соответствующее увеличение степени сжатия, но и одновременно усложняет способы работы с полученным архивом. Например, замена в таком архиве файла на более новую версию может потребовать перекодирования всего архива. В общем потоке с файлами способен работать архиватор RAR, а в ОС Unix практически все архиваторы, такие как Gzip, Bzip2 и т.д.

4.3.6 Сжатие с потерями.

Сжатие с потерями используется в основном для трех видов данных:

1.Полноцветная графика.

2.Видеоинформация.

3.Звуковая информация.

Сжатие с потерями обычно происходит в два этапа:

1.Исходная информация с потерями приводится к виду, в котором ее можно эффективно сжимать алгоритмами второго этапа сжатия без потерь.

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

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

На сегодняшний день существует много форматов сжатия видеоинформации, но наиболее распространенным является MPEG. Этот стандарт был предложен в 1988 году и является практически единственным для спутникового телевидения и записи информации на DVD, CD и т.д.

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