Архив1 / docx54 / Лаба 3 (2)

Цель:Изучение методик эффективного кодирования.

Задание

1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в таблицы.

2. Построить код Хаффмана по выбранным вариантам и результаты свести в таблицы. Для каждого построенного кода построить кодовое дерево.

Теоретическая часть

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

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

1. Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

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

3. Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0).

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

Близким по технике построения к кода Хаффмана являются коды Шеннона-Фано, предложенные Шенноном и Фано в 1948 - 49 гг. независимо друг от друга. Их построение может быть осуществлено следующим образом:

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

2. Последовательно делим множество символов на два подмножества так, чтобы сумма вероятностей появления символов одного подмножества была примерно равна сумме вероятностей появления символов другого. Для левого подмножества каждому символу приписываем "0", для правого - "1". Дальнейшие разбиения повторяются до тех пор, пока все подмножества не будут состоять из одного элемента.

Алгоритм создания кода Хаффмана называется снизу-вверх, а Шеннона-Фано - сверху-вниз. Преимуществами данных методов являются их очевидная простота реализации и, как следствие этого, высокая скорость кодирования/раскодирования. Основным недостатком является их неоптимальность в общем случае.

Практическая часть

Вариант 13

0,062	0,092	0,097	0,120	0,051	0,105	0,101	0,075	0,084	0,054	0,074	0,085
0,080	0,092	0,105	0,057	0,110	0,076	0,050	0,092	0,053	0,074	0,113	0,098
0,068	0,052	0,061	0,088	0,116	0,085	0,113	0,063	0,057	0,110	0,080	0,107

Знаки	Вероятность	Код Шеннона-Фано	Код Хаффмана
Z1	0,12	111	100
Z2	0,105	100	011
Z3	0,101	101	001
Z4	0,097	1001	000
Z5	0,092	1000	1111
Z6	0,085	011	1110
Z7	0,084	0101	1101
Z8	0,075	0100	1100
Z9	0,074	0011	1011
Z10	0,062	0010	1010
Z11	0,054	0001	0101
Z12	0,051	0000	0100

Энтропия

Среднее число символов на знак (по коду Шеннона-Фано)

Среднее число символов на знак (по коду Хаффмана)

Кодовое дерево для первого ряда

Знаки	Вероятность	Код Шеннона-Фано	Код Хаффмана
Z1	0,113	111	100
Z2	0,110	110	011
Z3	0,105	101	010
Z4	0,098	1001	000
Z5	0,092	1000	1111
Z6	0,092	011	1110
Z7	0,080	0101	1101
Z8	0,076	0100	1100
Z9	0,074	0011	1011
Z10	0,057	0010	1010
Z11	0,053	0001	0101
Z12	0,050	0000	0010

Энтропия

Среднее число символов на знак (по коду Шеннона-Фано)

Среднее число символов на знак (по коду Хаффмана)

Кодовое дерево для второго ряда

Знаки	Вероятность	Код Шеннона-Фано	Код Хаффмана
Z1	0,116	111	100
Z2	0,113	110	011
Z3	0,110	101	010
Z4	0,107	1001	000
Z5	0,088	1000	1111
Z6	0,085	0111	1110
Z7	0,080	0110	1101
Z8	0,068	0101	1100
Z9	0,063	0100	1011
Z10	0,061	001	1010
Z11	0,057	0001	0011
Z12	0,052	0000	0010

Энтропия

Среднее число символов на знак (по коду Шеннона-Фано)

Среднее число символов на знак (по коду Хаффмана)

Кодовое дерево для третьего ряда