Автор: Пользователь скрыл имя, 03 Ноября 2011 в 09:22, курсовая работа
Производительность существующих компьютерных сетей может быть заметно увеличена за счет повышения скорости передачи данных по каналам связи, которое обеспечивается использованием методов сжатия информации (эффективное кодирование). Для решения этой проблемы было разработано большое количество разнообразных методов кодирования информации, которые могут быть реализованы программно. Данная разработка представляет собой программный модуль, обеспечивающий комрессию и декомпрессию информации.
Аннотация 2
Введение 4
1. Постановка задачи 5
2. Основные обозначения 6
3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена 7
3.1. Динамическое кодирование хаффмена 7
3.2. Алгоритм динамического кодирования методом fgk 8
3.3. Алгоритм динамического кодирования виттера 9
Программная реализация 12
Руководство пользователя 13
Заключение 15
Библиографический список 16
Приложения 17
move(tmp,t^,sizeof(tmp))
CheckWiegth(P);
Enumerate(P);
k: =1;
end;
end;
end;
inc(k);
T: =GetNodeByNumber(P,k);
end;
end;
function GetLeafByWiegthMax(P: PTree; wiegth: integer): PTree;
var
i: integer;
Node: PTree;
begin
Result: =nil;
i: =1;
Node: =GetNodeByNumber(P, i);
while Node<>nil do
begin
if Node. Wiegth > wiegth then exit; // ???????
if Node. IsLeaf and (Node. Wiegth=wiegth) then
begin
Result: =Node;
end;
inc(i);
Node: =GetNodeByNumber(P, i);
end;
end;
function GetNodeByNumber(P: PTree; number: integer): PTree;
begin
if(P<>nil) then
begin
if P. Number=number then result: =P else
begin
Result: =GetNodeByNumber(P. Left,number);
if Result=nil then Result: =GetNodeByNumber(P. Right,number);
end;
end else Result: =nil;
end;
procedure Enumerate(P: PTree);
var
i,j,k,l,n,o,s: integer;
T: PTree;
begin
n: =0;
k: =MaxLevel(P);
for i: =k downto 1 do
begin
o: =1;
s: =1;
l: =1;
T: =GetNodeFromLevel(P, i,l,o,s);
while T<>nil do
begin
inc(n);
T. Number: =n;
inc(l);
o: =1;
s: =1;
T: =GetNodeFromLevel(P, i,l,o,s);
end;
end;
end;
function GetNodeFromLevel(P: PTREE; level,number: integer; var l,n: integer): PTree;
var
T: PTRee;
begin
result: =nil;
if(P<>nil) then
begin
if(l<level) then
begin
inc(l);
T: =GetNodeFromLevel(P. Left,level,number,l,n);
dec(l);
if(T=nil) then
begin
inc(l);
Result: =GetNodeFromLevel(P. Right,level,number,l,n);
dec(l);
end
else Result: =T;
end else
begin
if(l=level) then
begin
if(n=number) then result: =P else
begin
result: =nil;
end;
inc(n);
end else result: =nil;
end;
end else
result: =nil;
end;
procedure NodesOnLevel(Top: PTree; var qol: integer; l,level: integer);
begin
if Top<>nil then
begin
if level=l then
begin
inc(qol);
end else
begin
NodesOnLevel(top. Left,qol,l+1,Level);
NodesOnLevel(top. Right,qol,l+1,Level);
end;
end;
end;
function MaxLevel(Top: PTree): integer;
begin
if(Top=nil) then
begin
Result: =0;
end else
begin
Result: =Max(MaxLevel(Top. Left),MaxLevel(Top. Right)) +1;
end;
end;
function AddSymbol(var Top: PTree; c: char): boolean;
begin
if(not AddSymbolToTree(Top,c)) then
if(not AddNewSymbolToTree(Top,c)) then
result: =false // Error
else
result: =true // Added
else
result: =false; // Updated
end;
function AddSymbolToTree(var Top: PTree; c: char): boolean;
begin
if Top=nil then Result: =False else
begin
if Top. IsLeaf then
begin
if Top. Symbol=c then
begin
inc(Top. Wiegth);
result: =true;
end else
begin
result: =false;
end;
end else
begin
if AddSymbolToTree(Top. left,c) or AddSymbolToTree(Top. right,c) then
begin
inc(Top. Wiegth);
result: =true;
end else
result: =false;
end;
end;
end;
function AddNewSymbolToTree(var Top: PTree; c: char): boolean;
begin
if Top=nil then
begin
Top:
=NewNode(nil,nil,nil,#0,1,0,
Top.
left: =NewNode(nil,nil,Top,#0,0,0,
Top.
Right: =NewNode(nil,nil,Top,c,1,0,
result: =true;
end else
begin
if (Top. Wiegth=0) and (top. Symbol=#0) then
begin
Top.
Left: =NewNode(nil,nil,Top,#0,0,0,
Top.
Right: =NewNode(nil,nil,Top,c,1,0,
Top. IsLeaf: =false;
Top. Wiegth: =1;
Result: =true;
end else
begin
if (Top. Left<>nil) and AddNewSymbolToTree(Top. Left,c) then
begin
result: =true;
exit;
end;
if (Top. Right<>nil) and AddNewSymbolToTree(Top. Right,c) then
begin
result: =true;
exit;
end;
result: =false;
end;
end;
end;
procedure DeleteTree(var P: PTree);
begin
if P=nil then exit;
DeleteTree(P. Left);
DeleteTree(P. Right);
Dispose(P);
P: =nil;
end;
function NewNode(l,r,u: ptree; s: char; c,n: integer; i: boolean): PTree;
var
P: PTree;
begin
new(P);
P. Left: =l;
P. Right: =r;
P. Up: =u;
P. Symbol: =s;
P. Wiegth: =c;
P. Number: =n;
P. IsLeaf: =i;
result: =P;
end;
end.
Информация о работе Компрессия информации и упорядочение дерева по алгоритму Виттера