39. Коды с минимальной избыточностью (коды Хаффмана), метод построения.

Пусть р₁, р₂,…, р_r– частоты (вероятности), с которыми буквы алфавитавстречаются в исходных сообщениях. Частоты неотрицательны и удовлетворяют равенству.

Определение. Избыточностью схемы алфавитного кодирования Σ с длинами кодовых словl₁,l₂,…,l_r при заданных частотах р₁, р₂,…, р_rназывается число.

Избыточность схемы согласно определению равна .

Пример 1. При заданных частотах р₁= 0.4, р₂= 0.25, р₃= 0.2, р₄= 0.15 сравнить избыточность двух схем Σ₁и Σ₂, где

Заметим, что Σ₁– равномерная схема, а Σ₂– префиксная, поэтому обе эти схемы однозначно декодируемы. В схеме Σ₁длины кодовых словl₁ =l₂ =l₃ =l₄= 2, следовательно, её избыточность равна.

В схеме Σ₂длины кодовых словl₁ = 1,l₂ = 2,l₃ =l₄= 3, поэтому её избыточность равна.

Пример 2. Для набора частот р₁ = 0.4, р₂ = 0.25, р₃ = 0.2, р₄ = 0.1, р₅ = 0.05 требуется построить суффиксный код Хафмана с исходным алфавитоми кодирующим алфавитом.

Теперь построим бинарное дерево, корень которого располагается в самом верхнем ярусе. Каждая вершина, кроме корня, помечается числом из таблицы. Построение дерева и расстановка пометок его вершин выполняется рекурсивно. Сначала к единственной вершине – корню дерева – добавляются две смежные с ней вершины, которые помечаются числами из последнего столбца таблицы..

Около каждой концевой вершины дерева указана частота, а в скобках - соответствующее ей кодовое слово кода Хафмана. В итоге получаем префиксную схему Σ_пкода Хафмана

Однако по условию задачи требовалось построить суффиксную схему кодирования. Она легко получается «зеркальным отражением» префиксной схемы Σ_п.Следовательно, искомый суффиксный код Хафмана задается схемой Σ_с, где.

Избыточность построенного кода равна