1.5 Неравномерное кодирование

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

Коды Шеннона-Фано и Хаффмана являются префиксными. Префиксный код – код, обладающий тем свойством, что никакое более короткое слово не является началом (префиксом) другого более длинного слова. Такой код всегда однозначно декодируем. Обратное неверно.

Код Шеннона-Фано строится следующим образом. Символы источника выписываются в порядке убывания вероятностей (частот) их появления. Затем эти символы разбиваются на две части, верхнюю и нижнюю, так, чтобы суммарные вероятности этих частей были по возможности одинаковыми. Для символов верхней части в качестве первого символа кодового слова используется 1, а нижней – 0. Затем каждая из этих частей делится еще раз пополам и записывается второй символ кодового слова. Процесс повторяется до тех пор, пока в каждой из полученных частей не останется по одному символу.

Пример1.1:

Таблица 1.1 – Построение кода Шеннона-Фано.

Символ	Вероятность	Этапы разбиения				Код
		1	2	3	4
а1 а2 а3 а4 а5	0,40 0,35 0,10 0,10 0,05	1				1 01 001 0001 0000
		0 0 0 0	1
			0 0 0	1
				0 0	1
					0

Алгоритм Шеннона-Фано не всегда приводит к построению однозначного кода с наименьшей средней длиной кодового слова. От отмеченных недостатков свободен алгоритм Хаффмана.

Код Хаффмана строится следующим образом. Символы источника располагают в порядке убывания вероятностей (частот) их появления. Два самых последних символа объединяют в один вспомогательный, которому приписывают суммарную вероятность. Полученные символы вновь располагают в порядке убывания вероятностей, а два последних объединяют. Процесс продолжается до тех пор, пока не останется единственный вспомогательный символ с вероятностью 1. Для нахождения кодовых комбинаций строится кодовое дерево. Из точки, соответствующей вероятности 1, направляются две ветви. Ветви с большей вероятностью присваивается символ 1, с меньшей – 0. Такое ветвление продолжается до достижения вероятности каждого символа. Двигаясь по кодовому дереву сверху вниз, записывают для каждого символа кодовую комбинацию.

Пример1.2:

Таблица 1.2 – Построение кода Хаффмана.

Символ	Вероятность	Объединение символов				Код
а1 а2 а3 а4 а5	0,40 0,35 0,10 0,10 0,05	0,40 0,35 0,15 0,10	0,40 0,35 0,25	0,60 0,40	1,00	0 11 100 1011 1010

Рисунок 1.2 – Кодовое дерево для кода Хаффмана.

Домашнее задание:

1. [3.1.2] с.13…16;

[3.1.3] с.174…176;

[3.1.5] с. 109…112, 131…135, 297…299;

[3.1.14] с. 146…155;

[3.1.15] с.11…14.

2. Файл состоит из некоторой символьной строки:

«aaaaaaaaaabbbbbbbbccccccdddddeeeefff».

Закодировать символы кодами Шеннона-Фано и Хаффмана и оценить достигнутую степень сжатия.

РЕШЕНИЕ ЗАДАЧИ ДОМАШНЕГО ЗАДАНИЯ:

Рассчитаем частоты появления символов: υ(а)=10/36=0,28; υ(b)=8/36=0,22; υ(c)=6/36=0,17; υ(d)=5/36=0,14; υ(e)=4/36=0,11; υ(f)=0,08.

Таблица 1.3 – Построение кода Шеннона-Фано.

Символ	Частота	Этапы разбиения			Код
		1	2	3
a b c d e f	0,28 0,22 0,17 0,14 0,11 0,08	1 1	1		11 10 011 010 001 000
			0
		0 0 0 0	1 1	1
				0
			0 0	1
				0

Достигнутая в результате кодирования степень сжатия определяется коэффициентом сжатия:

,

где к₀ – первоначальный размер данных;

к_m – размер данных в сжатом виде.

При кодировании кодом Шеннона-Фано обеспечивается коэффициент сжатия:

36∙¯|log₂6|¯/(10∙2+8∙2+6∙3+5∙3+4∙3+3∙3)=108/90=1,2,

где 36 – количество символов в файле;

¯|log₂6|¯ - минимальная длина кодовой комбинации при кодировании равномерным кодом (¯|.|¯ обозначает ближайшее целое число, большее log₂6);

10, 8, 6, 5, 4, 3 – число символов a, b, c, d, e, f в файле;

2, 2, 3, 3, 3, 3 – длина кодовых комбинаций кода Шеннона-Фано, соответствующих символам a, b, c, d, e, f (см. таблицу 1.1).

Таблица 1.3 – Построение кода Хаффмана.

Символ	Частота	Объединение символов					Код
a b c d e f	0,28 0,22 0,17 0,14 0,11 0,08	0,28 0,22 0,19 0,17 1,14	0,31 0,28 0,22 0,19	0,41 0,31 0,28	0,59 0,41	1,00	10 01 111 110 001 000

Рисунок 1.3 – Кодовое дерево для кода Хаффмана.

При кодировании кодом Хаффмана обеспечивается степень сжатия:

К_сж=36∙¯|log₂6|¯/(10∙2+8∙2+6∙3+5∙3+4∙3+3∙3)=108/90=1,2.