скачать doc
1.5. Реализация алгоритмов кодирования
Рассмотрим реализацию алгоритмов кодирования Фано-Шеннона и Хаффмана. Для записи алгоритмов будем использовать псевдокод, основанный на языке Паскаль.
Для представления кодовых деревьев удобно использовать бинарные деревья с размеченными листьями. Эти деревья изоморфны рассмотренным в [*] иерархическим спискам. Их внутренние узлы не содержат иной информации, кроме ссылок на левое и правое поддеревья (деревья строго бинарные), а листья (внешние узлы) содержат собственно элементы базового типа. Рекурсивные типы данных, представляющие такие деревья, используют структуру размеченного объединения (записи с вариантами в языке Паскаль или структуру Union в языках C и C++). Определим для представления размеченного бинарного дерева типы данных
type TBT = Node;
Node = record
case Tag: (Inter, Leaf) of
Inter: (Left, Right: TBT);
Leaf: (Info: Num)
end {Node};
где Num = 0..nMax – тип данных для нумерации символов алфавита. Далее для типа TBT считаем определенными функции Null, Create, ConsTBT, LeftTBT, RightTBT, а также функцию MakeLeaf, создающую дерево из одного листа. При этом функция ConsTBT создает внутренний узел, т. е. узел типа Node с полем Tag = Inter, а функция MakeLeaf создает узел типа Node с полем Tag = Leaf.
Для представления двоичного кода используем абстрактный тип SeqB = Sequence of Bit, для которого определены соответствующие базовые функции, в том числе Null, Create, First, Rest, Postfix (см. [*], раздел 2). Функция-конструктор Postfix(S, b) дописывает бит b в конец последовательности S.
Первым рассмотрим алгоритм построения кода Фано-Шеннона. Вспомогательная процедура Middle разделяет набор символов (с учетом их весов) на две части, которым далее будут соответствовать левое и правое поддеревья. Входными параметрами процедуры Middle являются:
упорядоченный по неубыванию массив весов w[1..n], имеющий тип w_vector = array [Num1] of weight, где Num1 = 1..nMax;
индексы начала L и конца H сегмента массива w[1..n], соответствующего поддереву для группы символов от L до H;
сумма весов сегмента
.
Для описания выходных данных введем обозначения
. Выходными параметрами процедуры Middle являются:
индекс k, такой, что разность
имеет минимальное по абсолютной величине значение;
суммы весов
и 
для выходного значения k.
При этом выполняется соотношение
, а и используются далее при рекурсивном построении левого и правого поддеревьев.Итак
procedure Middle ({in:}w: w_vector; S: weight; L, H: Num;
{out:} var k: Num; var SL, SR: weight);
begin
SL := 0; SR:= S;
k := L – 1;
while SL < SR do
begin
k := k + 1;
SL := SL + w[k];
SR := SR w[k]
end {while};
{ SL ≥ SR }
if SL ≥ SR + w[k] then
begin
k := k 1;
SL := SL w[k];
SR := SR + w[k]
end {if}
end {Middle}
Отметим, что выход из цикла происходит при смене знака разности
, затем если после выхода предыдущее значение abs( ) было меньше, чем новое , то k уменьшается на единицу, а и принимают предыдущие значения.Следующая рекурсивная процедура F_Sh строит кодовое дерево b и коды Фано-Шеннона символов алфавита, размещаемые в глобальном массиве CodeFS. Параметр Code, в котором формируется код текущего узла дерева, используется как накапливающий.
Procedure F_Sh ( {in:} w: w_vector; S: weight; L, H: Num; Code: SeqB;
{out:} var b: TBT);
{Global: CodeFS: array [Num] of SeqB}
begin
if L = H then
begin
b := MakeLeaf (L);
CodeFS[L] := Code
end
else
begin
Middle (w, S, L, H, k, SL, SR); {S = SL + SR }
{построить левое поддерево:}
F_Sh (w, SL, L, k, Postfix(Code, 0), bL);
{построить правое поддерево:}
F_Sh (w, SR, k + 1, H, Postfix(Code, 1), bR);
{построить новый узел}
b := ConsTBT (bL, bR)
end
end {F_Sh}
Стартовый вызов процедуры построения кода Фано-Шеннона происходит следующим образом:
Code := Create;
S := 0;
for i := 1 to n do S := S + w[i];
F_Sh (w, S, 1, n, Code, b)
В результате будет построено дерево b и заполнен массив кодовых слов CodeFS[1..n].
Рассмотрим теперь реализацию алгоритма Хаффмана. Для организации действий с узлами дерева и их весами будем использовать специальную структуру данных SW, в которой для каждого узла b хранится запись с двумя полями: b.tree – ссылка на узел и b.w – вес узла. Веса используются на этапе построения дерева, но в само дерево не включаются. Кодовое дерево представляется бинарным деревом с размеченными листьями. Для структуры данных SW, содержащей набор записей, определены следующие операции:
функция Create, порождающая пустой набор данных, и функция Size(SW) – мощность набора;
процедура MinElem(SW, b), выделяющая из набора SW узел b.tree с минимальным значением b.w и исключающая запись b из набора;
процедура Insert(SW, b), добавляющая запись b в набор данных SW, так чтобы дальнейшее извлечение данных с помощью процедуры MinElem происходило корректно.
Тогда алгоритм Хаффмана может быть представлен в следующем итеративном виде:
SW := Create;
{инициализация SW листьями дерева}
for i := 1 to n do
begin
b.tree := MakeLeaf (i);
b.w := w[i];
Insert(SW, b)
end {for};
{построение дерева Хаффмана}
while Size(SW) > 1 do
begin
MinElem(SW, b1);
MinElem(SW, b2);
b.tree := ConsTBT(b1.tree, b2.tree);
b.w := b1.w + b2.w;
Insert(SW, b)
end {while};
{ Size(SW) = 1 и b.tree корень дерева Хаффмана}
После завершения построения дерева Хаффмана кодирование можно осуществить, например, следующей рекурсивной процедурой:
procedure Coder (b: TBT; c: SeqB);
{Global: CodeH: array [Num] of SeqB}
begin
if IsLeaf (b) then CodeH[b.Info] := c
else
begin
Coder (LeftTBT (b), Postfix(c, 0));
Coder (RightTBT (b), Postfix(c, 1))
end
end {Coder}
со стартовым вызовом
c := Create;
Coder (b.tree, c)
В процедуре Coder использована функция (предикат) IsLeaf (b), определяющая является ли узел дерева листом: если b.Tag = Leaf, то «да».
Процедура декодирования полученного кода для восстановления входной последовательности (a1, a2, …, am) по кодовому дереву (Фано-Шеннона или Хаффмана) приведена далее. В ней использован глобальный массив Alpha[1..n] исходных кодов алфавита A = {1, 2, …, n}.
procedure DeCoder ({in:} c: SeqB; b: TBT; {out:} var AS: SeqA);
{ in: c закодированное сообщение; b кодовое дерево}
{ out: AS декодированная последовательность символов алфавита}
var x: Bit;
begin
while not Null(c) do
begin {обработка (декодирование) кода}
p := b;
while not IsLeaf (p) do
begin
x := First (c); c := Rest (c);
if x=0 then p := Left (p) else p := Right (p)
end {while}
{ IsLeaf (p) }
AS := Postfix (AS, Alpha[p.Info])
end {while}
end {DeCder}
Стартовый вызов процедуры декодирования есть:
A := Create;
DeCoder (c, b, A);
Затем оценка количества операций и т.п.