Компрессия информации и упорядочение дерева по алгоритму Виттера

Автор: Пользователь скрыл имя, 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

Работа содержит 1 файл

Курсовая Работа теория.docx

— 47.88 Кб (Скачать)

      Huffman(DecodeTree);

      Vitter(DecodeTree);

      DrawTree(Form1. Panel2,DecodeTree,Form1. Panel2. ClientWidth,500);

      MakeDeCodeTable(DecodeTree);

      DString: ='';

      AddCharToDMess(c);

      DB: =false;

      break;

      end;

      end;

      end;

      end;

      end;

      procedure MakeCodeTable(Top: PTree);

      procedure CT(P: PTree; code: string);

      begin

      if P<>nil then

      begin

      if (P. Wiegth>=0) and (P. IsLeaf) then

      begin

      codetable [P. Symbol] : =code;

      end;

      if not P. IsLeaf then

      begin

      CT(P. Left,code+'0');

      CT(P. Right,code+'1');

      end;

      end;

      end;

      begin

      CT(Top,'');

      end;

      procedure ShowCT;

      var

      C: Char;

      begin

      Form1. CodeTableMemo. Clear;

      For c: =#0 to #255 do

      begin

      if CodeTable [c] <>'' then

      begin

      Form1. CodeTableMemo. Lines. Append(c+' - '+CodeTable [c]);

      end;

      end;

      end;

      procedure AddCharToMess(C: Char);

      var

      S: String;

      begin

      With Form1. MessageMemo do

      begin

      S: =Text;

      Clear;

      Text: =S+C;

      end;

      end;

      procedure AddCoded(c: char);

      var

      s: string;

      begin

      S: =Form1. CodedMsg. Lines. Text;

      Form1. CodedMsg. Clear;

      Form1. CodedMsg. Lines. Text: =S+' '+CodeTable [c];

      end;

      procedure AddASC(c: char);

      var

      i: integer;

      s: string;

      b: byte;

      begin

      s: ='';

      b: =byte(c);

      for i: =1 to 8 do

      begin

      s: =chr((b and 1) +$30) +s;

      b: =(b shr 1);

      end;

      S: =Form1. CodedMsg. Lines. Text+' '+s;

      Form1. CodedMsg. Clear;

      Form1. CodedMsg. Lines. Text: =S;

      end;

      procedure TForm1. InCharKeyPress(Sender: TObject; var Key: Char);

      var

      B: Boolean;

      begin

      B: =AddSymbol(Tree,Key);

      CheckWiegth(Tree);

      Enumerate(Tree);

      Huffman(Tree);

      DrawTree(Panel1,Tree,Panel1. ClientWidth,500);

      Application. MessageBox('stop','stop',MB_OK);

      Vitter(Tree);

      DrawTree(Panel1,Tree,Panel1. ClientWidth,500);

      if B then

      begin

      AddCoded(#0);

      AddASC(key);

      end else

      begin

      AddCoded(key);

      end;

      MakeCodeTable(Tree);

      AddCharToMess(Key);

      ShowCT;

      InChar. Clear;

      end;

      procedure TForm1. Button1Click(Sender: TObject);

      var

      s: string;

      c: char;

      begin

      s: =CodedMsg. Text;

      if(s<>'') then

      begin

      while s [1] =' ' do Delete(s,1,1);

      while ((s<>'') and (s [1] <>' ')) do

      begin

      Decode(s [1]);

      Delete(s,1,1);

      end;

      CodedMsg. Clear;

      CodedMsg. Text: =s;

      end;

      end;

      procedure TForm1. FormResize(Sender: TObject);

      begin

      Panel1. Top: =20;

      Panel1. Height: =(ClientHeight div 2) - 20;

      Label2. Top: =(ClientHeight div 2);

      Panel2. top: =(ClientHeight div 2) +20;

      Panel2. Height: =(ClientHeight div 2) - 20;

      end;

      procedure TForm1. FormPaint(Sender: TObject);

      begin

      DrawTree(Panel1,Tree,Panel1. ClientWidth,500);

      DrawTree(Panel2,DecodeTree,Panel2. ClientWidth,500);

      end;

      procedure TForm1. Button2Click(Sender: TObject);

      var

      s: string;

      c: char;

      begin

      s: =CodedMsg. Text;

      if(s<>'') then

      begin

      while s [1] =' ' do Delete(s,1,1);

      if ((s<>'') and (s [1] <>' ')) then

      begin

      Decode(s [1]);

      Delete(s,1,1);

      end;

      CodedMsg. Clear;

      CodedMsg. Text: =s;

      end;

      end;

      end.

      unit Core;

      {$B-}

      interface

      uses Graphics;

      type

      PTree = ^TTree;

      TTree = record

      Left,Right,Up: PTree;

      Symbol: char;

      Wiegth: integer;

      Number: integer;

      IsLeaf: boolean;

      end;

      function NewNode(l,r,u: PTree; s: char; c,n: integer; i: boolean): PTree;

      procedure DeleteTree(var P: PTree);

      function AddNewSymbolToTree(var Top: PTree; c: char): boolean;

      function AddSymbolToTree(var Top: PTree; c: char): boolean;

      function AddSymbol(var Top: PTree; c: char): boolean;

      function MaxLevel(Top: PTree): integer;

      procedure NodesOnLevel(Top: PTree; var qol: integer; l,level: integer);

      function GetNodeFromLevel(P: Ptree; level,number: integer; var l,n: integer): PTree;

      procedure Enumerate(P: PTree);

      function CheckWiegth(P: PTree): integer;

      function GetNodeByNumber(P: PTree; number: integer): PTree;

      function GetLeafByWiegthMax(P: PTree; wiegth: integer): PTree;

      procedure Vitter(P: PTree);

      procedure Huffman(P: PTree);

      implementation

      Uses Math,SysUtils;

      {$B-}

      function CheckWiegth(P: PTree): integer;

      begin

      Result: =0;

      if P<>nil then

      begin

      if not P. Isleaf then

      begin

      Result: =CheckWiegth(P. left) +CheckWiegth(P. right);

      P. Wiegth: =Result;

      end else Result: =P. Wiegth;

      end else

      Result: =0;

      end;

      procedure Huffman(P: PTree);

      var

      i,j,k: integer;

      t,tt: PTree;

      tmp: TTree;

      begin

      k: =1;

      t: =GetNodeByNumber(P,k);

      while t<>nil do

      begin

      tt: =GetNodeByNumber(P,k+1);

      if tt<>nil then

      begin

      if tt. Wiegth<t. Wiegth then

      begin

      move(tt^,tmp,sizeof(tmp));

      move(t^,tt^,sizeof(tmp));

      move(tmp,t^,sizeof(tmp));

      CheckWiegth(P);

      Enumerate(P);

      k: =1;

      end;

      end;

      inc(k);

      T: =GetNodeByNumber(P,k);

      end;

      end;

      procedure Vitter(P: PTree);

      var

      i,j,k,l: integer;

      t,tt,ttt: PTree;

      tmp: TTree;

      begin

      k: =1;

      t: =GetNodeByNumber(P,1);

      while t<>nil do

      begin

      if not T. IsLeaf then

      begin

      tt: =GetLeafByWiegthMax(P,t. wiegth);

      if(tt<>nil) then

      begin

      if(tt. Number>T. Number) then

      begin

      move(tt^,tmp,sizeof(tmp));

      move(t^,tt^,sizeof(tmp));

Информация о работе Компрессия информации и упорядочение дерева по алгоритму Виттера