Недостатки методов эффективного кодирования
Несмотря на все положительные стороны методов эффективного кодирования им присущи определенные недостатки:
Обычно знаки на вход устройства кодирования поступают через равные промежутки времени. Если им соответствуют комбинации различной длины, то для обеспечения полной загрузки канала при передаче без потерь необходимо предусмотреть буферное устройство, как на передающей, так и на приемной стороне.
Как было показано, достоинства эффективного кодирования проявляются в полной мере при кодировании длинными блоками. Для этого необходимо накапливать знаки, как при кодировании, так и при декодировании, что приводит к значительным задержкам.
Даже одиночная ошибка, возникшая в процессе передачи, может нарушить свойство префиксности кода и повлечь за собой неправильное декодирование ряда последующих комбинаций. Это явление называют трекомошибки.
Использование буферных устройств, для обеспечения равномерной загрузки канала, при разной длине кодовых комбинаций и организация кодирования блоками для повышения эффективности приводят к усложнению реализации систем эффективного кодирования. Если вдобавок применяются некоторые аппаратные решения, обеспечивающие повышение помехозащищенности, то все это в совокупности можетсвести на нет основное достоинство систем эффективного кодирования, связанное с тем, что знаки, имеющие большую вероятность, кодируются более короткими кодовыми словами.
2 гшлава
1. Постановка задачи(необходимо разработать программную реализацию……, про проанализировав алгоритм Х (гл.1 п. 3), можно придти к выводу об использовании при реавлизации ДСТ бинарные упорядоченные де6ревья деревья)+описание класса TTree
2. Разработка ПО (описание методов)
3. Тестиирование (пример вручную+ проверка программно)
Реализация программы эффективного кодирования методом Хаффмана
Постановка задачи
Изучив методы эффективного кодирования можно прийти к выводу, что методика Хаффмана является наиболее простой в реализации и, как следствие её скорость кодирования/декодирования наиболее высока.
В отличие от алгоритма Шеннона-Фано, алгоритм Хаффмана остаётся всегда оптимальным и для вторичных алфавитов с более чем двумя символами.
Этот метод кодирования состоит из двух основных этапов:
1. Построение оптимального кодового дерева.
2. Построение отображения код-символ на основе построенного дерева.
Алгоритм:
1. Подсчитываются вероятности появления символов первичного алфавита в исходном тексте (если они не заданы заранее)
2. Символы первичного алфавита m1 выписывают в порядке убывания вероятностей.
3. Последние n0 символов объединяют в новый символ, вероятность которого равна суммарной вероятности этих символов, удаляют эти символы и вставляют новый символ в список остальных на соответствующее место (по вероятности) n0 вычисляется из системы:
2 <= n0 <= m2
n0 = m1 - a (m2 - 1)
где a — целое число, m1 и m2 — мощность первичного и вторичного алфавита соответственно.
4. Последние m2 символов снова объединяют в один и вставляют его в соответствующей позиции, предварительно удалив символы, вошедшие в объединение.
5. Предыдущий шаг повторяют до тех пор, пока сумма всех m2 символов не станет равной 1.
Этот процесс можно представить как построение дерева, корень которого — символ с вероятностью 1, получившийся при объединении символов из последнего шага, его m2 потомков — символы из предыдущего шага и т.д.
Каждые m2 элементов, стоящих на одном уровне, нумеруются от 0 до m2-1. Коды получаются из путей (от первого потомка корня и до листка). При декодировании можно использовать то же самое дерево, считывается по одной цифре и делается шаг по дереву, пока не достигается лист — тогда выводится символ, стоящий в листе и производится возврат в корень.
Разработка ПО
В качестве «дерева Хаффмана» был создан класс TTree и THuffman:
TTree:
TTree = class(TObject)
private
fchild0 : TTree;
fchild1 : TTree;
fleaf : Boolean;
fcharacter : Integer ;
fweight : Integer ;
public
procedure Tree(character, weight : integer; leaf : boolean);
procedure traverse(code : string; h : THuffman);
property child0 : TTree read fchild0 write fchild0;
property child1 : TTree read fchild1 write fchild1;
property leaf : Boolean read fleaf write fleaf;
property character : Integer read fcharacter write fcharacter;
property weight : Integer read fweight write fweight;
end;
fchild0/1 – потомки 0 и 1
fleaf – признак листового дерева
fcharacter – входной символ
fweight – вес этого символа
THuffman:
THuffman = class(TObject)
private
fweights : array [0..ALPHABETSIZE-1] of Integer;
fcode : array [0..ALPHABETSIZE-1] of String:
ftree : array [0..ALPHABETSIZE-1] of TTree;
function GetCodeValue(Index: Integer): String;
function GetTreeValue(Index: Integer): TTree;
function GetWeightValue(Index: Integer): Integer;
procedure SetCodeValue(Index: Integer; const Value: String);
procedure SetTreeValue(Index: Integer; const Value: TTree);
procedure SetWeightValue(Index: Integer; const Value: Integer);
public
procedure makeCode;
procedure growTree(var data : array of Integer);
function getLowestTree(used : integer) : integer;
function coder(var data : array of integer) : string;
function decoder(data : string) : string;
property weights[Index: Integer] : Integer read GetWeightValue write SetWeightValue;
property code[Index: Integer] : String read GetCodeValue write SetCodeValue;
property tree[Index: Integer] : TTree read GetTreeValue write SetTreeValue;
end;
fweights – веса символов
fcode – коды Хаффмана
ftree – рабочий массив деревьев
Обход дерева с генерацией кодов
procedure TTree.traverse(code: String; h: THuffman);
begin
if leaf then
begin
h.code[Ord(character)] := code;
ShowMessage('Символ: ' + Chr(character) +' '+' Вес: '+IntToStr(weight) +' '+'Двоичный код:'+ code);
end;
if child0 <> nil then child0.traverse(code + '0', h);
if child1 <> nil then child1.traverse(code + '1', h);
end;
Ищем самое «легкое» дерево
function THuffman.getLowestTree(used: integer): integer;
var
min, i : Integer;
begin
min := 0;
for i:=1 to used-1 do if tree[i].weight < tree[min].weight then min := i;
Result := min;
end;
Кодируем данные строкой из 1 и 0
function THuffman.coder(var data: array of Integer): String;
var
str : String;
i : Integer;
begin
str := '';
for i:=0 to High(data) do str := str + code[data[i]];
Result := str;
end;
Растим «дерево»
procedure THuffman.growTree(var data: array of Integer);
var
i, c, w, min, used, weight0 : Integer;
temp : TTree;
begin
for i:=0 to ALPHABETSIZE-1 do weights[i] := 0;
for i:=0 to High(data) do weights[data[i]] := weights[data[i]] + 1;
used := 0;
for c:=0 to ALPHABETSIZE-1 do
begin
w := weights[c];
if w <> 0 then
begin
inc(used);
tree[used-1] := TTree.Create;
tree[used-1].Tree(c, w, true);
end;
end;
while used > 1 do
begin
min := getLowestTree(used);
weight0 := tree[min].weight;
temp := TTree.Create;
temp.child0 := tree[min];
dec(used);
tree[min] := tree[used];
min := getLowestTree(used);
temp.child1 := tree[min];
temp.weight := weight0 + tree[min].weight;
tree[min] := temp;
end;
end;
Запускаем вычисление кодов Хаффмана
procedure THuffman.makeCode;
begin
tree[0].traverse('', self);
end;
function THuffman.GetCodeValue(Index: Integer): String;
begin
Result := fcode[Index];
end;
function THuffman.GetTreeValue(Index: Integer): TTree;
begin
Result := ftree[Index];
end;
function THuffman.GetWeightValue(Index: Integer): Integer;
begin
Result := fweights[Index];
end;
procedure THuffman.SetCodeValue(Index: Integer; const Value: String);
begin
fcode[Index] := Value;
end;
procedure THuffman.SetTreeValue(Index: Integer; const Value: TTree);
begin
ftree[Index] := Value;
end;
procedure THuffman.SetWeightValue(Index: Integer; const Value: Integer);
begin
fweights[Index] := Value;
end;
Тестирование
Рассмотрим кодирование строки «побрёл бобёр в бор»
«вручную»:
проверим частоту встречаемости символов
п – 1
о – 3
б – 4
р – 3
ё – 2
л – 1
в – 1
“_” - 3
Исходя из частоты построим дерево Хаффмана:
| корень | |||||||||||
| 00 – р | 01 - б | ||||||||||
| 101 – “_” | 111 – “о” | ||||||||||
| в | л | п | ё | ||||||||
Программно:
Введем строку «побрёл бобёр в бор» и нажмём клавишу «кодирование»
Рисунок 4 ─ строка кодирования
Получим закодированную строку
Рисунок 5 ─ строка декодирования