Полная версия

Главная arrow Информатика arrow Теоретическая информатика arrow
Избыточность информации

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Процедуры Шеннона-Фано и Хаффмена

Процедура Шеннона-Фано.

В этом алгоритме используется следующий способ разбиения на два подмножества на каждом шаге кодирования. Предварительно производится упорядочивание сообщений по убыванию (или возрастанию) вероятностей pi. Разбиения на множества производится путем выбора разделяющей границы в упорядоченной последовательности так, чтобы суммарные вероятности подмножеств были по возможности одинаковыми. На рис. 4 приведено кодовое дерево, построенное этим методом для рассмотренного выше примера. Для наглядности в вершины дерева записаны подмножества кодируемых сообщений, а возле вершин – суммарные вероятности соответствующих подмножеств.

Кодовое дерево, построенное процедурой Шеннона-Фано

Процедура Хафмена.

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

Процедура Хаффмана представляет собой рекурсивный алгоритм, стоящий бинарное кодовое дерево в обратную сторону, т.е. от конечных вершин к корню. Конечные вершины представляют отдельные сообщения и их вероятности, корень представляет множество всех сообщений с суммарной вероятностью, равной единице, а внутренние вершины, а внутренние вершины представляют сгруппированные подмножества и их суммарные вероятности. Пусть Pm – задача кодирования сообщений, где сообщение i имеет вероятность появления pi иОсновная идея алгоритма состоит в том, чтобы объединить два сообщения с наименьшими вероятностями в одно множество и далее решать задачу Pm-1 c m-1 сообщениями и вероятностямиПрактически кодовое дерево в явном виде строится в обратном направлении, как показано на рис. 5 для нашего примера.

Кодовое дерево, построенное процедурой Хаффмана.

Прямой подсчет дает среднее значение длины кодового слова L=3.145, что совпадает с результатом, полученным с помощью процедуры Шеннона-Фано (это означает, что в данном примере процедура Шеннона-Фано также оказалась оптимальной).

 
<<   СОДЕРЖАНИЕ   >>

Похожие темы