Оптимальное кодирование.

Оптимальное кодирование служит для наиболее эффективного использования пропускной способности каналов, т.е. каждый символ при оптимальном кодировании несет в себе максимальное количество информации. Рассмотрим код Хафмана и алгоритм Шеннона-Фано.

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

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

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

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

Или в виде таблицы:

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

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

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

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

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