Методы арифметического кодирования информации и сравнение их коэффициентов сжатия
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ллов для каждого из вариантов (можно учитывать важность критериев).
Для решения поставленной задачи будем использовать перечень характеристик, приведенный выше. Каждую характеристику будем оценивать балом в диапазоне [1..10], а так же весовым коэффициентом в том же диапазоне. Выбор будем проводить из таких программно-инструментальных средств разработки как: Java Eclipse,Borland Delphi 7, Microsoft VC++ 6. Лучшим будет тот вариант, который наберёт максимальное количество баллов. Выбор средств разработки методом вариантных сетей представлен в табл. 3.1.
Таблица 3.1 - Сравнение сред разработки методом вариантных сетей
Характеристика средства разработкиВесОценка средств разработкиJava EclipseBorland Delphi7Microsoft VC++ 6Минимальная стоимость IDE71055Невысокая потребность ресурсов6788Наглядность разработки интерфейса5596Скорость работы разработанного программного обеспечения8789Обработка исключительных ситуаций8988Минимальное время создания разработанного программного обеспечения8595Удобство эксплуатации7886Наличие удобной справочной системы5689Итого391424376
В результате применения метода вариантных сетей установлено, что лучшим инструментальным средством с точки зрения разработчика в данном случае является среда Borland Delphi7.
.2 Описание основных функций программы, реализующей алгоритмы кодирования по методу Хаффмана
Для программирования алгоритмов кодирования и декодирования с помощью кода Хаффмана реализованы два класса:
. Класс Tree реализует структуру бинарного дерева, а также осуществляет обход дерева.
Tree = class child0: Tree; // левый потомок child1: Tree; // правый потомокleaf:boolean; // признак листаcharacter:integer; // входной символweight: integer; // частота вхождений символаconstructor Create;overload;// создание пустого дереваconstructor Create( character:integer; weight:integer; leaf:boolean);overload; // создание дерева с определенными параметрамиprocedure traverse( code:String ; h:Huffman); // обход дерева, //формирование таблицы кодировок символов;
процедура Tree.traverse(code:String; h:Huffman);
if (leaf) then //если добрались до листа
nil)thenchild0.traverse(code+0,h);////(child1 nil) then child1.traverse(code + 1, h);//обход по правой //ветви
end;
. Класс Huffman реализует всю логику построения и обработки бинарного дерева, а также осуществляет принципы кодирования и декодирования методом Хаффмана.
Huffman = class
weights:array[0..ALPHABETSIZE] of integer; // массив частот //вхождений символов в последовательности
public code:array[0..ALPHABETSIZE]of string; // массив строк-кодов //для символов последовательности
public procedure growTree (data:array of integer);// рост дерева из //источника datafunction coder(data:array of integer):string;//кодирование //последовательности data по деревуfunction decoder(data:String):string;//декодирование кода data по //дереву
end;
Gtree -массив деревьев, глобальная переменная.
-процедура построения дерева Huffman.growTree( data:array of integer );i,used,c,w,min,weight0:integer ;:Tree;i:=0 to length(data)-1 do[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;;(used > 1)do // просмотр всех деревьев в массиве:= getLowestTree( used ); //поиск дерева с мин.частотой 0 := Gtree[min].weight;
temp := Tree.Create; //создаем узел, связывающего деревья с //минимальными частотами
temp.child0 := Gtree[min]; // создаем левого потомка узла
used:=used-1;[min] := Gtree[used];:= getLowestTree( used );.child1 := Gtree[min];.weight := weight0 + Gtree[min].weight;
Gtree[min] := temp; //ставим узел на место правого потомка узла
end; ;
функция кодирования Huffman.coder( data:array of integer ):string;
var str:string; :integer;:= ;i:=0 to length(data)-1 do // просмотр всех символов посл-ти data :=str+ code[data[i]]; // извлечение кода из полученной таблицы
//code и накопление строки-кода всей посл-ти
result:=str;;
функция декодирования Huffman.decoder(data:String):string;
var str:string;:integer;
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;:=str;;
.3 Описание основных функций программы, реализующей алгоритмы кодирования по методу Голомба
Golomb_M - параметр M в кодировании методом Голомба
функция кодирования одного целого положительного числа
function GolombCodingOne(n:integer):string;
// n - число, которое следует закодировать
// возвращаемый результат - строка-код числа
var q,r,b,cutoff,i:integer;:string;
begin
q:= n div Golomb_M; //нахождение частного от деления числа n на
//параметр Golomb_M
r:= n mod Golomb_M; //нахождение остатка от деления числа n на
//параметр Golomb_M
result:=UnaringCode(q); //получаем первую часть кода - унарный код
//частного q
b:= ceil(math.Log2(Golomb_M));// получаем параметр b
cutoff:=round(power(2,b))-Golomb_M; // получаем параметр с
if (r<cutoff) then // диапазон 0 ? r < c
begin
bin:=GetBinary(r); //получаем бинарный код числа r в виде строки
for i:=1 to (b-1)-length(bin) do:=result+0;:=result+bin; // наращивание строки-кода// диапазон r ? c: