Министерство Образования и Науки Украины
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
на тему:
“Компрессия информации и упорядочение дерева по алгоритму Виттера”
по курсу “ Кодирование и защита информации. ”
2005

Аннотация
Пояснительная записка содержит описание разработанной программы и руководство по ее использованию. Также в ней приводится описание используемых методов компрессии информации.

Содержание
  "1-3" Аннотация...................................................................................................... 2
Введение......................................................................................................... 4
1. Постановка задачи................................................................................... 5
2. Основные обозначения............................................................................. 6
3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена........................................................ 7
3.1. Динамическое кодирование хаффмена............................................... 7
3.2. Алгоритм динамического кодирования методом fgk....................... 8
3.3. Алгоритм динамического кодирования виттера................................ 9
Программная реализация........................................................................... 13
Руководство пользователя........................................................................ 13
Заключение.................................................................................................. 15
Библиографический список....................................................................... 16
Приложения.................................................................................................. 17

Введение
В настоящее время большое внимание уделяется информации, недаром наш век называют “информационным”. Во время того, как люди познают технологии хранения и передачи информации, встает вопрос о ее компрессии.
Производительность существующих компьютерных сетей может быть заметно увеличена за счет повышения скорости передачи данных по каналам связи, которое обеспечивается использованием методов сжатия информации (эффективное кодирование). Для решения этой проблемы было разработано большое количество разнообразных методов кодирования информации, которые могут быть реализованы программно. Данная разработка представляет собой программный модуль, обеспечивающий комрессию и декомпрессию информации.

1. Постановка задачи
Необходимо разработать программу для кодирования и декодирования непрерывно поступающей информации. Для компрессии использовать алгоритм динамического кодирования Виттера. Разработать удобный интерфейс общения с пользователем.

2. Основные обозначения
m-размер алфавита источника сообщений;
zj - j-й символ алфавита;
M(k) =z(1), z(2), …, z(k) - первые к символов в сообщении;
k - число символов в сообщении, обработанных до текущего момента времени
K-количество различных символов, обработанных на текущий момент времени;
Wj-вес символов zj, поступивших на момент обработки сообщения.
lj - расстояние от корня дерева до zj – го листа.

3. Обзор и характеристика существующих методов сжатия информации, основанные на процедуре кодирования хаффмена
Алгоритм динамического кодирования Виттера представляет собой усовершенствование динамического кодирования Хаффмена.
Класический метод кодирования Хаффмена предпологает до начала преобразования знание вероятностей появления символов на выходе источника информации. Символы упорядочиваются по убыванию вероятностей их возникновения. На передающей и приемной сторонах должны быть известны кодовые деревья для каждого сообщения. Таким образом для его реализации требуется два прохода кодируемого массива. При 1-м просмотре вычисляются вероятности появления каждого знака в сообщении и составляется таблица кода Хаффмена. На следуещем этапе осуществляется кодирование на основании статистической структуры дерева Хаффмена и передача символов в сжатом виде. Выйгрыш полученный за счет сжатия данных может заметно снижаться, особенно при передачи коротких сообщений, в связи с необходимостью передавать декодеру дополнительную информацию о кодовом дереве. Еще один недостаток это наличие задержки от момента поступления данных от источника до выдачи соответствующих кодовых комбинаций, что ограничивает использование неравномерного кодирования в системах реального времени.
3.1. Динамическое кодирование хаффмена
В начале 70-х годов были разработаны однопроходные методы сжатия информации. Суть состоит в том, что передатчик строит дерево Хаффмена в темпе поступления данных от источника. В процессе кодирования происходит “обучение” кодера на основе статистических характеристик источника сообщений в ходе которого вычисляются оценки исходных вероятностей сообщения и производится модификация кодового дерева Хаффмена. Т. к. происходит непрерывное изменение дерева, этот процесс получил название динамического кодирования Хаффмена. Декодер должен непрерывно “учиться” наряду с кодером осуществляя синхронное изменение дерева. Для обеспечения синхронности процессов кодирования и декодирования кодер выдает символ в несжатом виде, если он впервые появился на выходе источника, и отмечает его на кодовом дереве. При повторном появлении символа на входе декодера он передается неравномерной кодовой комбинацией, определяемой позицией символа на текущем кодовом дереве.
На одном уровне не может быть меньше 2-х узлов, пара узлов является дочерней, т.к. имеет общий родительский узел, вес которого равен сумме весов дочерних узлов.
Хаффменское дерево должно обладать следующими свойствами:
Листья имеют неотрицательный вес W>0, каждый родительский узел имеет дочерние узлы, а его вес равен сумме дочерних весов.
На каждом уровне дерева, кроме корневого должно быть не менее одной пары узлов, имеющих общий родительский узел.
Все узлы нумеруются в возрастающем порядке, узлы с номерами (2j-1) и 2j являются узлами одного уровня для 1<=j<=m-1, их общий родительский узел имеет более высокий уровень.
3.2. Алгоритм динамического кодирования методом fgk
Суть алгоритма состоит в процедуре вычисления листьев и построения бинарного дерева с минимальным весом пути åWjlj.
На 1-м этапе дерево Хаффмена преобразуется в эквивалентное исходному, которое может быть преобразовано в хаффменовское дерево для M(k+1).
1-й этап начинается после получения от источника символа z(k+1), который получает статус текущего узла. Затем происходит обмен текущего узла (включаю поддерево) с узлом имеющим наибольший порядковый номер с таким же весом. В качестве нового текущего узла иницилизируется родительский узел последнего текущего узла. Обмен в случае необходимости многократно повторяется пока не будет достигнут корень дерева. Максимальное количество перестановок, которые могут понадобиться равна высоте дерева. На 2-м этапе инкрементируется лист дерева соответствующий обрабатываемому символу и последующие промежуточные узлы, расположенные на пути движения от листа к корню дерева.
3.3. Алгоритм динамического кодирования виттера
Данный алгоритм позволяет построить динамическое хаффменское дерево таким образом, что бы минимизировать сумарную длину внешнего пути и расстояние от корня дерева до листа. Число обменов узлов в процессе модификации сводится к минимуму. Минимизация высоты дерева h= max{ lj} позволит предотвратить образование длинных кодовых комбинаций при кодировании очередного символа в сообщении.
Алгоритм Виттера обладает следующими преимуществами по сравнению с алгоритмом FGK:
Количество обменов узлами, при котором текущий узел перемещается в верх по кодовому дереву в процессе его модификации ограничивается еденицей.
Алгоритм Виттера минимизирует длину внешнего пути дерева lj и гарантирует дерево минимальной высоты h= max{ lj} при условии минимизации суммарной длины внешнего пути дерева.
По алгоритму Виттера осуществляется так называемая неявная нумерация (implicit numbering) узлов кодового дерева. При неявной нумерации узлы хаффменского дерева нумеруются в порядке увелечения по уровням слева направо и снизу вверх. Важнейшим условием неявной нумерации является соблюдение необходимого условия построения дерева:
Для каждого веса W все листья дерева с весом W должны предшествовать всем внутренним узлам веса W.
Структурная схема алгоритма динамического кодирования Виттера приведена на рисунке 1.
На рисунке 2 приведена структурная схема процедуры скольжения и приращения.

А

Начало

LeafToIncrement :=0 Установка начального значения

q:=Zi(k+1) q соответствующий символу Zi(k+1)

If q яв-ся 0-м узлом и (K<N-1)

Заменить q на внутрений 0-й узел и создать 2 его дочерних узла. Левый-0-й узел. Правый- Zi(k+1)

q:=внутр-й толко что созданный узел

LeafToIncrement:=правый дочерний узел текущего узла q

Обменять q c лидером его блока

If q образ-т пару с нулевым уз-м

LeafToIncrement:=q

q:=родитель q

While q не является корнем хаффменского дерева

Вызов скольжен.,-преращение SlideAndIncrement

А

LeafToIncrement<>0

SlideAndIncrement(LeafToIncrement)

Начало

Рисунок 1 - Блок - схема алгоритма динамического кодирования Виттера

 

SlideAndIncremt

Wt:= вес p p-текущий узел дерева

b:=следующий за текущим узлом блок в компонуемом списке

If (p-лист)and(b-блоквнутр.узлов весом wt

Скольжение p в главу блока узлов b

p-й вес:=wt+1

If p является листом

P:=новый родитель p, После скольжения

P:=прежний родитель p, до скольжения

конец

Рисунок 1 - Блок - схема процедуры скольжения и приращения.

Программная реализация
Для разработки программы был выбран язык программирования высокого уровня Delphi 5.0 (Object Pascal).
Он весьма полно выражает идеи структурного программирования. Это проявляется в том, что Delphi может успешно использоваться для записи программ на разных уровнях ее детализации, не прибегая к помощи блок-схем или специального языка проектирования программ. Средства языка Delphi позволяют осуществлять достаточный контроль правильности использования данных различных типов и программных объектов как на этапе трансляции так и на этап ее выполнения.
Delphi позволяет без особых трудностей реализовать удобный пользовательский интерфейс, не пребигая к написанию низкоуровневого кода.
В проекте предпологается кодирование непрерывно поступающей информации, поэтому программа позволяет пользователю вводить исходное сообщение с клавиатуры, которое кодируется и отображает структуру кодового дерева хаффмена.
Декодировку сообщения можно производить по символьно и по битам.
В программе есть так же возможность считать данные для кодирования из фыйла.
Руководство пользователя
Программа работает под управлением операционной системы Windows 9. x.
Программа имеет удобный пользовательский интерфейс.
Программа имеет две основные области: кодировка и декодировка. Справа расположено поле для ввода сообщения. В процессе поступления сообщения в окне кодировка строится кодовое дерево. В поле Сообщение отображаются поступающие данные. В поле Закодированное отображается закодированное сообщение.
Декодировку можно производить как по символам, так и по битам. Для этого используются соответствующие кнопки: Символ и Бит.
Результат декодировки отображается в поле Декодирование. В процессе декодирования строится кодовое дерево.

Заключение
В ходе выполнения курсовой работы были закреплены знания, полученные в ходе изучения дисциплины “Кодирование и защита информации”. Работа выполнена в соответствии с постановкой задачи на курсовое проектирование.
Для проверки работоспособности программы и правильности обработки входных данных разработан тестовый пример. Тестирование программы подтвердило, что программа правильно выполнила обработку данных и выдает верные результаты.

Библиографический список
1.     Конспект лекций по курсу “Кодирование и защита информации”
2.     Цымбал В.П. “Теория информации и кодирование. ” – Киев: “Вища школа”, 1982 – 303с.
3.     В.С. Чернега “Сжатие информации в компьютерных сетях” - СевГТУ, Севастополь 1997.

Приложения
ПРИЛОЖЕНИЕ A
Тестирование программы
Исходное сообщение: Hello world!
Таблица 1. Итерация№1

Итерация №1

Сообщение: H

Закодировнное сообщение: 01101000

1

 

                        *                   3

1

0

                                                  H            
                      
1                 2
Таблица 2. Итерация№2

Итерация №2

Сообщение: He

Закодировнное сообщение: 01101000 001100101

2

 

1

1

 H                 5        

0

1

 

                         3                            4
                             *                                e
1             2
Таблица 3. Итерация№3

Итерация №3

Сообщение: Hel

Закодировнное сообщение: 01101000 001100101 1001101100

3

 

2

1

7

0

1

1

1

 

                           5                                              6 
*                                 l              H                                 e      
1                             2                  3                                4
Таблица 4. Итерация№4

Итерация №4

Сообщение: Hell

Закодировнное сообщение: 01101000 001100101 1001101100 01

1

0

2

1

1

2

4

                                     7
 
                  l
            
               5                                         6
                                         e
                                  
                                              3                                 4
                                                               *                                   H
                                             
1    2
Таблица 5. Итерация№5

Итерация №5

Сообщение: Hello

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111

5

1

1

0

2

3

1

2

1

 

                                                  9
 

              7                                                                         8
e                              h                                                                          l
 

3                          4                                 5                                         6
                                       *                                        o
1               2
Таблица 6. Итерация№6

Итерация №6

Сообщение: Hello_

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111 100 00100000

               

1

2

2

4

2

1

 

6

                                                                             11
 

                               9                                                                                      10
  e                                                                                        l
 

         5                                          6                                         7                                            8
                               *                                             -                                      h                                           o
                                        
                                 1                                    2                                                 3                                4

1

1

1

10

Таблица 7. Итерация№7

Итерация №7

Сообщение: Hello_ w

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111 100 00100000  01001110111

7

3

4

2

1

2

2

0

1

1

1

1

1

                                                                                13
                                         11                                                                                        12
                                                                        l
                7                                                8                                      9                                                  10
*                                   w                                     e                                         -          h                            o     
1                              2                                        3                                4                   5                         6            
Таблица 8. Итерация№8

Итерация №8

Сообщение: Hello_ wo

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111 100 00100000  01001110111 111

8

 

4

2

2

2

2

4

                                                                                    13
 

                                                 11                                                                 12
                       o                                   l

1

1

1

1

 

                           7                                 8                              9                                        10
                                                                      e                                            h   

0

1

 

                                                                           3                              4           5                             6 
                                                                                                                             *                                   w   
1                        2

Таблица 9. Итерация№9

Итерация №9

Сообщение: Hello_ wor

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111 100 00100000  01001110111 111  1110 01110010

2

2

9

4

5

3

2

 

                                                                                        15
 

               o                        13                                                                            14

0

0

 

                 9                                           10                                   11                                          12

1

                                     h                                       w              e                                  -                           l         

2

1

10

0

1

 

                                           3                              4               5                     6                7                           8     
                                                                                                                  *                                  r     
                                                                                                                       1                          2
Таблица 10. Итерация№10

8 Итерация №10

Сообщение: Hello_ worl

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111 100 00100000  01001110111 111  1110 01110010 111

6

4

10

                                                                                           15

2

3

3

2

 

                                        13                                                        l                               14

1

1

1

2

1

1

 

                9                                            10                                      11                                           12
h                              w           e                            -                                                                                       o 

0

1

 

3                           4                 5                         6                   /                              7                                   8     
                                                                                                                  *                                    r
                                                                                                                    1                                   2       
Таблица 11. Итерация№11

Итерация №11

Сообщение: Hello_ world

Закодировнное сообщение: 01101000 001100101 1001101100 01 110 01101111 100 00100000  01001110111 111  1110 01110010 111 1100 01100100

                                                                                               17
                                                      15                                                                    16    
                                                                                                   l

1

1

2

2

1

1

 

                          11                                            12                         13                                  14

4

2

4

3

7

 

2

   h                                      w                   e                                                      o              

0

1

1

 

1

         5                           6                   7                        8                                        9                         10  
                                                                *                                         d                 -                                        r

11

                                                                      1                                2                             3                             4 

ПРИЛОЖЕНИЕ В
Текст программы
unit Form;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ExtCtrls, Core;
type
TForm1 = class(TForm)
InChar: TEdit;
Panel1: TPaintBox;
Panel2: TPaintBox;
Label1: TLabel;
Label2: TLabel;
CodeTableMemo: TMemo;
MessageMemo: TMemo;
Label3: TLabel;
Label4: TLabel;
CodedMsg: TMemo;
Button1: TButton;
DecodedMsg: TMemo;
Button2: TButton;
Label5: TLabel;
procedure InCharKeyPress(Sender: TObject; var Key: Char);
procedure Button1Click(Sender: TObject);
procedure FormResize(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
Tree, DecodeTree: PTree;
codetable: array [char] of string;
decodetable: array [char] of string;
procedure MakeCodeTable(Top: PTree);
implementation
{$R *. DFM}
procedure DrawTree(D: TPaintBox; P: Ptree; w,h: integer);
var
C: TCanvas;
procedure Draw(T: PTree; x,y,level,ofs: integer);
begin
if(T<>nil) then
begin
if(T. Left<>nil) then
begin
c. MoveTo(x,y);
c. LineTo(x-(ofs div 2),y+30);
end;
if(T. Right<>nil) then
begin
c. MoveTo(x,y);
c. LineTo(x+(ofs div 2),y+30);
end;
C. Ellipse(x-12,y-12,x+12,y+12);
if t. isleaf then if t. symbol=#0 then C. TextOut(x-4,y-25,'*') else C. TextOut(x-4,y-25,t. Symbol);
C. TextOut(x-6,y-7, inttostr(T. wiegth));
C. TextOut(x-6,y+12, inttostr(T. number));
Draw(T. Left,x-(ofs div 2),y+30,level+1,ofs div 2);
Draw(T. Right,x+(ofs div 2),y+30,level+1,ofs div 2);
end;
end;
begin
C: =D. Canvas;
C. Brush. Color: =clBtnFace;
C. FillRect(D. ClientRect);
Draw(P,w div 2,30,1,w div 2);
end;
procedure MakeDeCodeTable(Top: PTree);
procedure CT(P: PTree; code: string);
begin
if P<>nil then
begin
if (P. Wiegth>=0) and (P. IsLeaf) then
begin
decodetable [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;
var
DCounter: integer;
DString: String;
DByte: byte;
DB: Boolean;
procedure AddCharToDMess(C: Char);
var
S: String;
begin
With Form1. DecodedMsg do
begin
S: =Text;
Clear;
Text: =S+C;
end;
end;
procedure Decode(BIT: Char);
var
i,j: integer;
c: char;
begin
if DB then
begin
if DCounter=0 then
DCounter: =7 else
dec(DCounter);
DByte: =((DByte shl 1) or (byte(bit) and 1));
if DCounter=0 then
begin
AddSymbol(DecodeTree,chr(DByte));
CheckWiegth(DecodeTree);
Enumerate(DecodeTree);
Huffman(DecodeTree);
Vitter(DecodeTree);
DrawTree(Form1. Panel2,DecodeTree,Form1. Panel2. ClientWidth,500);
MakeDeCodeTable(DecodeTree);
AddCharToDMess(chr(DByte));
DString: ='';
DB: =false;
end;
end else
if DecodeTree=nil then
begin
DB: =true;
Decode(BIT);
end else
begin
DString: =DString + Bit;
for c: =#0 to #255 do
begin
if DecodeTable [c] =DString then
begin
if c=#0 then
begin
DB: =true;
DCounter: =0;
end else
begin
AddSymbol(DecodeTree,c);
CheckWiegth(DecodeTree);
Enumerate(DecodeTree);
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));
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.