Кодирование неравномерными кодами

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

Для обеспечения однозначности декодирования необходимо после каждого сообщения передавать некоторый разделитель, не совпадающий ни с одной из кодовых комбинаций. Это значительно снижает эффективность кодирования. Чаще идут по другому пути - используют неравномерные коды, удовлетворяющие префиксному свойству: никакое более короткое слово кода не является началом (префиксом) другого более длинного слова кода. В таблице 1 пять сообщений закодированы двумя неравномерными кодами, из них код 1 - непрефиксный, а код 2 - префиксный. Существует несколько алгоритмов построения префиксных кодов. Рассмотрим коды Шеннона-Фано и Хаффмана.

Таблица 1 − Примеры кодов

Номер кода	Сообщение и соответствующее ему кодовое слово	Вид кода
а1	а2	а3	а4	а5
						Непрефиксный
						Префиксный

Коды Шеннона-Фано

Алгоритм кодирования кодом Шеннона-Фано состоит в следующем:

1 Все сообщения источника располагают в таблице в один столбец в порядке убывания их вероятностей.

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

3 Сообщениям верхней группы в качестве первого символа кодового слова присваивают символ - " 0 ", а нижнего - " 1 " (или наоборот).

4 Каждая из полученных групп, если она содержит более одного сообщения, делится на две подгруппы, имеющие, по возможности, равные суммарные вероятности. В качестве второго символа кодового слова используется " 0 " или " 1 " в зависимости от принадлежности сообщений верхней или нижней подгруппе (как в п. «Кодирование неравномерными кодами»).

5 Процесс повторяется до тех пор, пока в каждой подгруппе не останется по одному сообщению.

Пример 1 Требуется закодировать кодом Шеннона-Фано восемь сообщений а_1, а_2, а_3, а_4, а_5, а_6, а_7, а_{8 ,} имеющих следующие вероятности появления р(а₁)=0,12;

р(а₂)=0,03; р(а₃)=0,2; р(а₄)=0,15; р(а₅)=0,07; р(а₆)=0,13; р(а₇)=0,10; р(а₈)=0,2.

Результаты кодирования сообщений кодом Шеннона-Фано приведены в таблице 2

Таблица 2− Кодирование сообщений кодом Шеннона-Фано

Сообщения аi	Вероят-ности	Этапы разбиения на группы и подгруппы	Кодовая комбина-ция
1-й	2-й	3-й	4-й
а3	0,2
а8	0,2
а4	0,15
а6	0,13
а1	0,12
а7	0,10
а5	0,07
а2	0,03

В результате кодирования получен неравномерный префиксный код, обеспечивающий однозначное декодирование сообщений. Для расчета полученной степени сжатия определим число n двоичных символов " 0 " и " 1 ", необходимых для кодирования любого из сообщений равномерным двоичным кодом, и среднее число кодовых символов n_ср, затрачиваемых на кодирование одного сообщения в таблице 3.2. Значения чисел n и n_ср находят из выражений n≥log₂M и ,

где n_i - количество символов, затраченных для кодирования сообщения а_i.

Для сообщений из таблицы 2

;

n_ср = 0,2∙2+0,2∙3+0,15∙3+0,13∙3+0,12∙3+0,10∙3+0,07∙4+0,03∙ 4= 2,9

Энтропия источника сообщений составляет

Степень сжатия будет равна: n/nср = 3/2,9 ≈1,0345. Потери информации при кодировании сообщений неравномерным кодом не произойдет, поскольку, как видно из примера, n_ср больше Н(А), то есть энтропия источника не уменьшится.

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

Коды Хаффмана

Метод сжатия, предложенный Хаффманом, свободен от недостатков метода Шеннона-Фано и широко применяется в настоящее время.

Алгоритм кодирования по методу Хаффмана состоит в следующем:

1 Все сообщения источника располагают в таблице в один (основной) столбец в порядке убывания их вероятностей.

2 Два самых маловероятных сообщения (два последних) объединяют в одно и вычисляют их суммарную вероятность.

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

4 Два самых маловероятных сообщения полученного вспомогательного столбца объединяют в одно и вычисляют их суммарную вероятность.

5 Повторяют шаги 3 и 4, создавая новые вспомогательные столбцы, до тех пор, пока не получат единственное сообщение, вероятность которого Р=1,0.

6 Строят кодовое дерево Хаффмана, начиная от сообщения вероятностью Р=1,0. От этой вероятности отводят две ветви, соответствующие двум вероятностям, давшим в сумме вероятностьР=1,0. Ветви с большей вероятностей присваивают символ " 1 ", а с меньшей − " 0 ". Затем каждую из полученных ветвей вновь разветвляют на две и так продолжается до тех пор, пока не доходят до концевых узлов, соответствующих вероятностям каждого из исходных сообщений а_i. При присвоении ветвям символов «1» и «0» необходимо соблюдать постоянство в расположении ветвей (например, левая ветвь всегда «1»). При разветвлении ветви на две равновероятные одной из них присваивается " 1 ", а другой " 0 ".

7 Кодируют исходные сообщения, двигаясь по ветвям кодового дерева в направлении от вероятности Р=1,0 к концевым узлам, соответствующим определенным сообщениям.

Пример 2. Требуется закодировать кодом Хаффмана восемь сообщений а_1, а_2, а_3, а_4, а_5, а_6, а_7, а_{8 ,} с вероятностями р(а₁)=0,16; р(а₂)=0,10; р(а₃)=0,04; р(а₄)=0,16; р(а₅)=0,22; р(а₆)=0,02; р(а₇)=0,20; р(а₈)=0,10.

Этапы объединения вероятностей сообщений а₁…а₈ во вспомогательные столбцы продемонстрированы в таблице 3. На рисунке 2 приведено кодовое дерево, построенное по результатам данных таблицы 3. Кодовые комбинации, полученные в результате кодирования, приведены в таблице 4. Они представляют собой неравномерный префиксный код.

Таблица 3−Формирование вспомогательных столбцов кода Хаффмана

Сообщения аi	Вероят-ности р(аi)	Вспомогательные столбцы
а5	0,22	0,22	0,22	0,26	0,32	0,42	0,58	1,00
а7	0,20	0,20	0,20	0,22	0,26	0,32	0,42
а1	0,16	0,16	0,16	0,20	0,22	0,26
а4	0,16	0,16	0,16	0,16	0,20
а2	0,10	0,10	0,16	0,16
а8	0,10	0,10	0,10
а3	0,04	0,06
а6	0,02

Рисунок 2 − Кодовое дерево кода Хаффмана

Таблица 4 − Кодовые комбинации кода Хаффмана

Сообщение	а1	а2	а3	а4	а5	а6	а7	а8
Код

Для полученного кода среднее число символов «0» и «1», приходящихся на одно закодированное сообщение, составит: n_ср=0,22∙2+0,2∙2+0,16∙3+0,16∙3+0,10∙3+0,10∙4+0,04∙5+0,02∙5=2,8

Степень сжатия равна 3/2,8=1,071.

Словарные методы сжатия

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

Так, если элементарными сообщениями являются буквы русского алфавита (примем, что их число М =32=2⁵) и они передаются равновероятно и независимо, то энтропия источника, приходящаяся на одну букву, составит То есть каждую букву можно закодировать последовательностью из пяти двоичных символов. Если же буквы составляют связный русский текст, то они оказываются неравновероятными (например, буква А передается значительно чаще, чем буква Ф) и, главное, зависимыми. Так, после гласных не может появиться "ь" и др. Подсчитано, что для текстов русской художественной прозы энтропия оказывается менее 1,5 бит/букву и, следовательно, возможен способ эффективного кодирования текстов без потери информации, при котором в среднем на одну букву будет затрачено не 5, а немногим более 1,5 двоичных символов, то есть на 70% меньше. Существует довольно много способов сокращения избыточности текста. Так вместо " ААА " можно закодировать "3 А " или же сокращать слова, как это делается в стенографии. Особенно большой эффект дает укрупнение алфавита, когда кодируются не отдельные буквы, а целые слова.

Рассмотрим следующий пример. В достаточно большом словаре имеется около 10000 слов, содержащих в среднем по 7 букв. Как указывалось выше, на кодирование одной буквы русского алфавита требуется 5 двоичных символов, а на одно слова, состоящее из 7 букв - 5 Для кодирования 10000 слов необходимо затратить 350000 тысяч символов. Если же кодировать не буквы, а эти 10000 слов и дополнительно еще по две грамматические формы на каждое слово, то на каждое из 30000 слов придется затратить по 15 двоичных символов вместо 35 (2¹⁵=32768). Таким образом, в среднем на букву придется немногим больше двух символов, т.е. сжатие достигнет 60%. Слова, не вошедшие во вновь созданный словарь, придется передавать обычным способом, затрачивая по пять символов на букву.

Существуют различные способы создания словарей. Большинство из них базируются на универсальных алгоритмах сжатия LZ77 и LZ78, разработанных в 70-е годы ХХ века совместно Зивом (Ziv) и Лемпелем (Lempel). Сжатая информация содержит меньше битов, чем исходная, но по ней возможно однозначное восстановление каждого бита исходных данных. Процесс восстановления информации называется разжатием. Используют и такие пары терминов: компрессия/декомпрессия, кодирование/декодирование, упаковка/распаковка. Очевидно, что, кроме собственно словаря, созданный сжатый файл должен содержать последовательность ссылок на этот словарь.

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

Алгоритмы группы LZ78 не используют скользящего окна и в создаваемый словарь помещают не все встречаемые при кодировании строки, а лишь "перспективные" с точки зрения вероятности последующего использования. В начале обработки словарь пуст. Далее, теоретически, словарь может расти бесконечно, т.е. на его рост сам алгоритм не налагает ограничений. На практике при достижении определенного объема занимаемой памяти словарь должен очищаться полностью или частично.

Разработано большое число модификаций алгоритмов LZ77 и LZ78. Их наименования содержат буквы LZ и первые буквы фамилий авторов модификации. Например: LZBW - авторы Бендер (Bender) и Вулф (Wolf); LZCB - автор Блум (Bloom).

Сжатие информации с потерями

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

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

Работы по анализу качества и оценке эффективности алгоритмов компрессии цифровых аудио- и видеоданных с целью их последующей стандартизации начались в 1988 году, когда Международным союзом электросвязи была образована международная экспертная группа MPEG (Moving Pictures Experts Group). Итогом работы этой группы на первом этапе явилась разработка в 1992 году международного стандарта MPEG-1. В дальнейшем были разработаны стандарты сжатия MPEG-2, MPEG-4, MPEG-7, MPEG-21. Стандарт MPEG-2 разработан для использования в системах вещательного телевидения.

Дата добавления: 2015-08-13