Описание программы кодирования Хаффмана

Этот вариант  адаптивного кодирования Хаффмана очень прост, но менее эффективен. Его идея заключается в построении множества из   кодов переменной длины на основе равных вероятностей и случайном присвоении этих кодов   символам. После чего смена кодов делается «на лету» по мере считывания и сжатия символов. Метод не слишком производителен, поскольку коды не основаны на реальных вероятностях символов входного файла. Однако его проще реализовать, и он будет работать быстрее описанного выше алгоритма, поскольку переставляет строки таблицы быстрее, чем первый алгоритм перестраивает дерево при изменении частот символов.

Рис. 4. Четыре шага алгоритма типа Хаффмана.

Основная структура  данных - это таблица размера  , в которой три столбца хранят, соответственно, имена   символов, частоты символов и их коды. Таблица все время упорядочена по второму столбцу. Когда счетчики частот во втором столбце изменяются, строки переставляются, но перемещаются только первый и второй столбцы. Коды в третьем столбце не меняются. На рис. 4 показаны примеры для четырех символов и поведение метода при сжатии строки « ».

На рис. 4а изображено начальное состояние. После считывания символа   его счетчик увеличивается, и поскольку он теперь наибольший, строки 1 и 2 меняются местами (рис. 4b). Далее считывается второй символ  , его счетчик увеличивается, и строки 2 и 4 переставляются (рис. 1.17с). Наконец, после считывания третьего символа  , его счетчик становится наибольшим, что приводит к перестановке строк 1 и 2 (рис. 4d).

В этом алгоритме  только одно место может вызвать  проблему - это переполнение счетчиков. Если переменные счетчиков имеют разрядность   бит, их максимальное значение равно  . Поэтому наступит переполнение после  -го увеличения. Это может случиться, если размер сжимаемого файла заранее не известен, что бывает часто. К счастью, нам не надо знать точные значения счетчиков. Нам нужен лишь их порядок, поэтому эту проблему переполнения легко разрешить.

Можно, например, считать входные символы, и после   символа делать целочисленное деление счетчиков на 2 (или сдвигать их содержимое на одну позицию влево, что проще).

Другой близкий  способ - это проверять каждый счетчик после его увеличения и после достижения максимального значения делать деление на 2 всех счетчиков. Этот подход требует более редкого деления, но более сложных проверок.

В любом случае, все операции должны делаться синхронно кодером и декодером.

 

 

 

 

 

 

 

 

 

Глава 3. Описание программы кодирования Хаффмана

3.1 Обоснование  выбора инструментальных средств

 

Современные программно-инструментальные средства разработки ПО характеризуются  большим разнообразием характеристик. Так, в настоящее время инструментальные средства позволяют:

• базируясь на стандартных компонентах создавать интерфейс приложения в зависимости от состояния системы передавать управление различным процессам;
• создавать базы данных и оболочки для баз данных;
• выполнять корректную обработку исключительных ситуаций, что позволяет повысить надёжность ПО.

Современные средства разработки характеризуются следующими параметрами:

• поддержка объектно-ориентированного стиля программирования;
• возможность использования CASE-технологий для проектирования разрабатываемой системы, использование визуальных компонент для наглядного проектирования интерфейса;
• наличие визуальной технологии разработки интерфейса;
• возможность использования алгоритмов реляционной алгебры для управления реляционными базами данных;
• предоставление средств синхронизации и контроля версий составных частей проекта (эти средства используются при разработке программного обеспечения группами программистов);
• создание инсталляционных пакетов для распространения разработанного программного обеспечения.

При создании прототипа  программного обеспечения главными критериями выбора программно-инструментальных средств разработки являются:

• скорость разработки приложений;
• удобство использования;
• возможность быстрого внесения изменений в программу;

Обеспечить  минимальное время разработки можно  только при выполнении этих условий. Исходя из приведенных требований, выделим следующие характеристики средств разработки программного обеспечения:

• стоимость IDE;
• невысокая потребность ресурсов;
• наглядность разработки интерфейса;
• предоставляемые возможности работы с базами данных;
• скорость работы разработанного программного обеспечения;
• обработка исключительных ситуаций;
• время создания разработанного программного обеспечения;
• удобство эксплуатации;
• средства контроля версий составных частей проекта;
• наличие удобной справочной системы.

Для выбора инструментального  средства воспользуемся методом  вариантных сетей. Этот метод предназначен для выбора наилучшего варианта из нескольких предложенных и состоит из следующих этапов:

• определение критериев, по которым будет произведено сравнение и
• степени их важности;
• каждый вариант оценивается по полученному перечню критериев (получается численное значение – оценка);
• нахождение общего количества баллов для каждого из вариантов (можно учитывать важность критериев).

Для решения  поставленной задачи будем использовать перечень характеристик, приведенный  выше. Каждую характеристику будем  оценивать балом в диапазоне [1..10], а так же весовым коэффициентом в том же диапазоне. Выбор будем проводить из таких программно-инструментальных средств разработки как: Java Eclipse,Borland Delphi 7, Microsoft VC++ 6. Лучшим будет тот вариант, который наберёт максимальное количество баллов. Выбор средств разработки методом вариантных сетей представлен в табл. 3.1.

 

Таблица 5. – Сравнение сред разработки методом вариантных сетей

Характеристика  средства разработки	Вес	Оценка средств  разработки
		Java Eclipse	Borland Delphi7	Microsoft VC++ 6
Минимальная стоимость IDE	7	10	5	5
Невысокая потребность  ресурсов	6	7	8	8
Наглядность разработки интерфейса	5	5	9	6
Скорость работы разработанного программного обеспечения	8	7	8	9
Обработка исключительных ситуаций	8	9	8	8
Минимальное время  создания разработанного программного обеспечения	8	5	9	5
Удобство эксплуатации	7	8	8	6
Наличие удобной  справочной системы	5	6	8	9
Итого		391	424	376

 

В результате применения метода вариантных сетей установлено, что лучшим инструментальным средством  с точки зрения разработчика в данном случае является среда Borland Delphi7.

 

 

 

 

 

 

3.2 Описание  основных функций программы, реализующей  алгоритмы кодирования по методу  Хаффмана 

 

Для программирования алгоритмов кодирования и декодирования  с помощью кода Хаффмана реализованы два класса:

1. Класс Tree реализует структуру бинарного дерева, а также осуществляет обход дерева.

Tree = class

public child0: Tree; // левый потомок

public child1: Tree; // правый потомок

public leaf:boolean; // признак листа

public character:integer; // входной символ

public weight: integer; // частота вхождений символа

public constructor Create;overload;// создание пустого дерева

public constructor Create( character:integer; weight:integer; leaf:boolean);overload; // создание дерева с определенными параметрами

public procedure traverse( code:String ; h:Huffman); // обход дерева, //формирование таблицы кодировок символов

end;

процедура Tree.traverse(code:String; h:Huffman);

begin

if (leaf) then //если добрались до листа

begin

writeln(Gf, chr(character),' ',weight ,' ', code); //сохраняем в файл

h.code[character] := code; // запоминаем код листа

end;

if ( child0 <> nil) then child0.traverse(code + '0', h); //обход по левой //ветви

if ( child1 <> nil) then child1.traverse(code + '1', h);//обход по правой //ветви

end;

2. Класс Huffman реализует всю логику построения и обработки бинарного дерева, а также осуществляет принципы кодирования и декодирования методом Хаффмана.

Huffman = class

weights:array[0..ALPHABETSIZE] of integer; // массив частот //вхождений символов в последовательности

public code:array[0..ALPHABETSIZE]of string; // массив строк-кодов //для символов последовательности

public procedure growTree (data:array of integer);// рост дерева из //источника data

public function coder(data:array of integer):string;//кодирование //последовательности data по дереву

public function decoder(data:String):string;//декодирование кода data по //дереву

end;

Gtree –массив деревьев, глобальная переменная.

-процедура построения дерева Huffman.growTree( data:array of integer );

var i,used,c,w,min,weight0:integer ;

temp:Tree;

begin

for i:=0 to length(data)-1 do

weights[data[i]]:= weights[data[i]]+1; //вычисление и запоминание //частот в массив weights

used := 0; // количество ненулевых частот символов

for c:=0 to ALPHABETSIZE-1 do //обход по всевозможным символам

begin

w := weights[c];

if (w <> 0)then begin // если частота символа с не равна 0

Gtree[used] := Tree.Create(c, w, true); //в массив деревьев

//добавляем  новое дерево

used:=used+1;

end;

end;

while (used > 1)do // просмотр всех деревьев в массиве

begin

min := getLowestTree( used ); //поиск дерева с мин.частотой

weight0 := Gtree[min].weight;

temp := Tree.Create; //создаем узел, связывающего деревья с //минимальными частотами

temp.child0 := Gtree[min]; // создаем левого потомка узла

used:=used-1;

Gtree[min] := Gtree[used];

min := getLowestTree( used );

temp.child1 := Gtree[min];

temp.weight := weight0 + Gtree[min].weight;

Gtree[min] := temp; //ставим  узел на место правого потомка  узла

end;

end;

-функция кодирования Huffman.coder( data:array of integer ):string;

var str:string;

i:integer;

begin

str := '';

for i:=0 to length(data)-1 do // просмотр всех символов посл-ти data

str :=str+ code[data[i]]; // извлечение кода из полученной таблицы

//code и накопление строки-кода всей посл-ти

result:=str;

end;

-функция декодирования Huffman.decoder(data:String):string;

var str:string;

c:integer;

begin

str:='';

while(length(data) > 0)do // пока строка для декодирования существует

for c:=0 to ALPHABETSIZE-1 do //просмотр всевозможных символов

if (weights[c]>0) and (Pos(code[c],data)=1) then // если символ с хотя бы //раз встречался и его код стоит вначале строки-кода, то можно его //преобразовать

begin

data:= copy(data,Length(code[c])+1,length(data)); //сокращаем //строку-код на код символа с

str := str+chr(c); //формируем строку-декодинг

end;

result:=str;

end;

// name – имя файла, в котором содержится закодированная //последовательность;

//возвращаемое  значение – строка-декодинг

var kol,i,M,q,b,b1,b2,cutoff:integer;

s_temp:string;

f:textfile;

c:char;

begin

assignfile(f,name); //привязка логического файла к физическому

reset(f); // открытие файла для чтения

readln(f); // пропускаем первую строку в файле

readln(f,M); // считываем с файла число Голомба - М

b:=ceil(math.Log2(M)); //считаем параметр b

cutoff:=round(power(2,b))-M; //считаем параметр с

s_temp:=''; result:='';

read(f,c);

while not(eof(f)) do //идем до конца файла

begin