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

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

      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,false);

      Top. left: =NewNode(nil,nil,Top,#0,0,0,true);

      Top. Right: =NewNode(nil,nil,Top,c,1,0,true);

      result: =true;

      end else

      begin

      if (Top. Wiegth=0) and (top. Symbol=#0) then

      begin

      Top. Left: =NewNode(nil,nil,Top,#0,0,0,true);

      Top. Right: =NewNode(nil,nil,Top,c,1,0,true);

      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.

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