RĪGAS TEHNISKĀ UNIVERSITĀTE

Datorzinātnes un informācijas tehnoloģijas fakultāte

Informātikas un programmēšanas katedra

Praktiskais darbs

Datu struktūras

“Hafmana kods”

1. Saturs

1. Saturs................................................................................................................................................ 2

2. Ievads............................................................................................................................................... 3

3. Biogrāfija.......................................................................................................................................... 3

4. Teorija............................................................................................................................................... 4

5. Realizācija........................................................................................................................................ 5

6. Realizācija uz Pascal......................................................................................................................... 9

7. Secinājumi........................................................................................................................................ 9

8. Bibliogrāfiskais saraksts................................................................................................................... 9

2. Ievads

Hafmana kods (Hafmana alogritms) – optimālas prefiksa kodēšanas adaptējamais mantkārīgs algoritms* (Greedy algorithm) ar minimālo pārpalikumu. Tika izstrādāts 1952. gadā Masačūsetsas tehnoloģiskajā Universitātē. Mūsdienās to ļoti plaši pielieto arhivēšana un kriptogrāfijā.

Algoritms sastāv no diviem etapiem:

· Optimāla kodu koka izbūve

· Attēlojuma kods-simbols izbūve uz koka pamata

3. Biogrāfija

Algoritma autors - Davīds Hafmans (David Albert Huffman) (9.08.25 - 07.10.99)

Universitātes:

· Ogajo Universitāte

· Masačūsetsas Tehnoloģiskais Institūts

Sasniegumi:

· 1952. gadā izveidoja prefiksa kodēšanas algoritmu ar minimālo pārpalikumu – Hafmana kodu.

· 1999. gadā saņēma Ričarda Hemminga medali par ieguldījumu informācijas teorijā.

Dāvids Hafman piedzima 1925. gadā Ogajo, ASV. 18 gadu vecumā viņš guva bakalaura grādu elektrotehnikā Ogajo Universitātē. Vēlāk viņš dienēja armijā kā virsnieks radara atbalstā grupā. Viņu daļas nodarbojas ar Japānas un Ķīnas ūdeņu atbrīvošanu no mīnām pēc II.p.k. Pēc dienesta Dāvids guva maģistra grādu Ogajo Universitātē un vēlāk doktora grādu Masačūsetsas Tehnoloģijas Institūtā. Kaut vai Hafmans ir vairāk pazīstām dēļ savu algoritmu, viņš izdarīja svarīgu ieguldījumu arī citās nozarēs (galvenokārt elektronikā). Viņš ilgu laiku vadīja MTI datorzinātņu katedru. 1974. gadā, būdams jau slavens profesors viņš atkāpās no amata. 1999. gada oktobrī, 74 gadu vecumā Dāvids Hafmans mira no vēža.

Haffmans guva virkni apbalvojumu:

· 1999 – Ričarda Hemminga medaļu (Institute of Electrical and Electronics Engineers – IEEE), par ieguldījumu informācijas teorijā.

· 1999- Louis E. Levy medali (Franklin Institute) par viņa doktora darbu par virknes pārslēguma shēma.

· 1998 – Apbalvojumu W. Wallace McDowell

· 1998 – Apbalvojumu no IEEE datoru sabiedrības, par tehnoloģiskām inovācijām.

4. Teorija

· Aprakstītais algoritms ir prefiksa algoritms – tas nozīme ka katru iekodētu simbolu var interpretēt tikai vienā veida. To var paskaidrot uz piemēra – ja A ir "0110" un B ir "01", tad saņemot šos simbolus pa bitam mēs nevarēsim pateikt vai tas ir nākamais šī simbola skaitlis, vai arī nākamais simbols. Prefiksa kodēšanā simbolu secība neatkārtojas tādā veidā lai tos varētu interpretēt dažādi. To nodrošina binārais koks.

· Minētājs algoritms ir mantkārīgais algoritms (angl. Greedy algorithm) tas nozīme ka algoritms meklē lokāli optimālos risinājumus katra etapā, pieņemot, ka arī kopumā risinājums būs optimāls.

· Adaptējamais algoritms – algoritms kas mēģina sasniegt labākus rezultātus pastāvīgi pielāgojoties ieejas datiem. Šādus algoritmus pielieto saspiešanā bez zudumiem.

5. Realizācija

1. Pirmais ko ir jāizdara kodējot failu pēc Hafmana koda ir izlasīt visu failu kopumā un saskaitīt cik reizes atkārtojas katrs simbols (pēc pilnas ASCII tabulas). Ja mēs skaitīsim visus simbolus, tad mums bus vienalga ko arhivēt: teksta failu vai exe.

2. Pēc tā ir nepieciešams sastādīt tabulu ar katru simbolu, to skaitu un sakārtot to dilstošā secībā. Piemēram:

Sākumā:

Simbols	A	B	C	D	E	F
Skaits	10	20	30	5	25	10

Rezultāts:

Simbols	C	E	B	F	A	D
Skaits	30	25	20	10	10	5

3. Katru no stabiņiem noformēsim mezglu veidā un saskaitīsim mezglus ar viszemāko sastapšanas frekvenci. Mūsu gadījumā tas būs A un D mezgli. Jauna mezgla sastapšanās frekvence – 15 (10+5). Tas ir kopējais simbolu A un D sastapšanās biežums. (skat. Att. 5‑1).

4. Tagad mēs atkal meklējam mezglus ar vismazāko sastapšanās frekvenci, bet ignorējam A un D mezglus, viņu vietā skatot jauno mezglu. Rezultāta meklētie mezgli ir F un A+D. Atkārtosim iepriekšējo operāciju. (skat. Att. 5-2).

5. Atkārtosim to pašu operāciju, kamēr mēs neatradīsim koka sakni, kura summai jābūt vienādai ar visu bloku summu. (skat. Att. 5-3).

6. Tagad, kad koks jau ir izveidots mēs varam sākt faila kodēšanu. Vienmēr ir jāsāk no saknes un jākodē lapas pēc kārtas. Piemēram sāksim ar lapu C: ejot no saknes līdz lapai mēs atcerēsimies katru kreiso pagriezienu ka 0 un katru labo kā 1. C gadījumā mums ir divi kreisie pagriezieni, attiecīgi C kods bus vienāds ar "00". Ņemsim lapu A, mums sanāk – kreisi – labi – kreisi – kreisi, tas ir "0100". Tagad sastādīsim tabulu ar visiem simboliem un to vērtībām.

Simbols	Kods	Atmiņas apjoms
C	00	2 bit
A	0100	4 bit
D	0101	4 bit
F	011	3 bit
B	10	2 bit
E	11	2 bit

7. Katrs simbols, kas agrāk sastāvēja no 8 bitiem, tagad ir krietni mazāks, attiecīgi samazinājās arī faila izmērs.

Simbols	Sast.frekvence	Bitu skaits pēc kodēšanas	Sākotnēji (bit)	Pēc kodēšanas (bit)	Izmēra samazinājums
C	30	2	240	60	180
A	10	4	80	40	40
D	5	4	40	20	20
F	10	3	80	30	50
B	20	2	160	40	120
E	25	2	200	50	150
Kopā:			800	240	560

8. Sākotnējais faila izmērs 100 byte – 800 bit. Saspiesta faila izmērs – 30 byte – 240 bit. Fails ir saspiests uz 70%. Tas ir ļoti labs rezultāts, bet problēma ir tajā, kā failu vel ir jāatkodē, un priekš tā ir vajadzīgs sākotnējais koks, kuru nāksies glābāt tajā pašā failā, kas neizbēgami palielinās tā izmēru. Mūsu gadījumā katrā mezglā atrodas 4 byte radītāju, tas nozīme ka pilnas tabulas apmērs būs aptuveni 50 byte. Pieliksim pie 30 byte saspiestas informācijas 50 byte tabulas un iegūsim 80 byte un 20% saspiešanu, kas ir pietiekoši labs rezultāts. Ko mēs īstenība izdarījām – pārveidojam ASCII tabulu, lai tas kodi aizņemtu mazāk vietās.

6. Realizācija uz Pascal

{$A+,B-,D+,E+,F-,G-,I-,L+,N-,O-,R+,S+,V+,X-}

{$M 16384,0,655360}

{* Hafmana koda realizacija *}

Program Hafman;

Uses Crt,Dos,Printer;

Type PCodElement = ^CodElement;

CodElement = record

NewLeft,NewRight,

P0, P1 : PCodElement;

LengthBiteChain : byte;

BiteChain : word;

CounterEnter : word;

Key : boolean;

Index : byte;

end;

TCodeTable = array [0..255] of PCodElement;

Var CurPoint,HelpPoint,

LeftRange,RightRange : PCodElement;

CodeTable : TCodeTable;

Root : PCodElement;

InputF, OutputF, InterF : file;

TimeUnPakFile : longint;

AttrUnPakFile : word;

NumRead, NumWritten: Word;

InBuf : array[0..10239] of byte;

OutBuf : array[0..10239] of byte;

BiteChain : word;

CRC,

CounterBite : byte;

OutCounter : word;

InCounter : word;

OutWord : word;

St : string;

LengthOutFile, LengthArcFile : longint;

Create : boolean;

NormalWork : boolean;

ErrorByte : byte;

DeleteFile : boolean;

procedure ErrorMessage;

{ --- kludas pazinojums --- }

begin

If ErrorByte <> 0 then

begin

Case ErrorByte of

2 : Writeln('File not found ...');

3 : Writeln('Path not found ...');

5 : Writeln('Access denied ...');

6 : Writeln('Invalid handle ...');

8 : Writeln('Not enough memory ...');

10 : Writeln('Invalid environment ...');

11 : Writeln('Invalid format ...');

18 : Writeln('No more files ...');

else Writeln('Error #',ErrorByte,' ...');

end;

NormalWork:=False;

ErrorByte:=0;

end;

procedure ResetFile;

{ --- faila atversana aktivacijai --- }

Var St : string;

begin

Assign(InputF, ParamStr(3));

Reset(InputF, 1);

ErrorByte:=IOResult;

ErrorMessage;

If NormalWork then Writeln('Pak file : ',ParamStr(3),'...');

end;

procedure ResetArchiv;

{ --- arhiva izveidosana vai atversana --- }

begin

St:=ParamStr(2);

If Pos('.',St)<>0 then Delete(St,Pos('.',St),4);

St:=St+'.vsg';

Assign(OutputF, St);

Reset(OutPutF,1);

Create:=False;

If IOResult=2 then

begin

Rewrite(OutputF, 1);

Create:=True;

end;

If NormalWork then

If Create then Writeln('Create archiv : ',St,'...')

else Writeln('Open archiv : ',St,'...')

end;

procedure SearchNameInArchiv;

{ --- faila meklesana arhiva --- }

begin

Seek(OutputF,FileSize(OutputF));

ErrorByte:=IOResult;

ErrorMessage;

end;

procedure DisposeCodeTable;

{ --- koda tabulas iznicinasana --- }

Var I : byte;

begin

For I:=0 to 255 do Dispose(CodeTable[I]);

end;

procedure ClosePakFile;

{ --- arhivejama faila aizversana --- }

Var I : byte;

begin

If DeleteFile then Erase(InputF);

Close(InputF);

end;

procedure CloseArchiv;

{ --- arhiva aizversana --- }

begin

If FileSize(OutputF)=0 then Erase(OutputF);

Close(OutputF);

end;

procedure InitCodeTable;

{ --- kodesanas tablicas inicializacija --- }

Var I : byte;

begin

For I:=0 to 255 do

begin

New(CurPoint);

CodeTable[I]:=CurPoint;

With CodeTable[I]^ do

begin

P0:=Nil;

P1:=Nil;

LengthBiteChain:=0;

BiteChain:=0;

CounterEnter:=1;

Key:=True;

Index:=I;

end;

For I:=0 to 255 do

begin

If I>0 then CodeTable[I-1]^.NewRight:=CodeTable[I];

If I<255 codetable="" ewleft:="CodeTable[I];<o:p" then="">

end;

LeftRange:=CodeTable[0];

RightRange:=CodeTable[255];

CodeTable[0]^.NewLeft:=Nil;

CodeTable[255]^.NewRight:=Nil;

end;

procedure SortQueueByte;

{ --- booble atlase --- }

Var Pr1,Pr2 : PCodElement;

begin

CurPoint:=LeftRange;

While CurPoint <> RightRange do

begin

If CurPoint^.CounterEnter > CurPoint^.NewRight^.CounterEnter then

begin

HelpPoint:=CurPoint^.NewRight;

HelpPoint^.NewLeft:=CurPoint^.NewLeft;

CurPoint^.NewLeft:=HelpPoint;

If HelpPoint^.NewRight<>Nil then HelpPoint^.NewRight^.NewLeft:=CurPoint;

CurPoint^.NewRight:=HelpPoint^.NewRight;

HelpPoint^.NewRight:=CurPoint;

If HelpPoint^.NewLeft<>Nil then HelpPoint^.NewLeft^.NewRight:=HelpPoint;

If CurPoint=LeftRange then LeftRange:=HelpPoint;

If HelpPoint=RightRange then RightRange:=CurPoint;

CurPoint:=CurPoint^.NewLeft;

If CurPoint = LeftRange then CurPoint:=CurPoint^.NewRight

else CurPoint:=CurPoint^.NewLeft;

end

else CurPoint:=CurPoint^.NewRight;

end;

procedure CounterNumberEnter;

{ --- frekvences saskaitisana --- }

Var C : word;

begin

For C:=0 to NumRead-1 do

Inc(CodeTable[(InBuf[C])]^.CounterEnter);

end;

function SearchOpenCode : boolean;

{ --- minimalo vertibu meklesana --- }

begin

CurPoint:=LeftRange;

HelpPoint:=LeftRange;

HelpPoint:=HelpPoint^.NewRight;

While not CurPoint^.Key do

CurPoint:=CurPoint^.NewRight;

While (not (HelpPoint=RightRange)) and (not HelpPoint^.Key) do

begin

HelpPoint:=HelpPoint^.NewRight;

If (HelpPoint=CurPoint) and (HelpPoint<>RightRange) then

HelpPoint:=HelpPoint^.NewRight;

end;

If HelpPoint=CurPoint then SearchOpenCode:=False else SearchOpenCode:=True;

end;

procedure CreateTree;

{ --- frekvencu koka izveidosana --- }

begin

While SearchOpenCode do

begin

New(Root);

With Root^ do

begin

P0:=CurPoint;

P1:=HelpPoint;

LengthBiteChain:=0;

BiteChain:=0;

CounterEnter:=P0^.CounterEnter + P1^.CounterEnter;

Key:=True;

P0^.Key:=False;

P1^.Key:=False;

end;

HelpPoint:=LeftRange;

While (HelpPoint^.CounterEnter < Root^.CounterEnter) and

(HelpPoint<>Nil) do HelpPoint:=HelpPoint^.NewRight;

If HelpPoint=Nil then { pielikt beigas }

begin

Root^.NewLeft:=RightRange;

RightRange^.NewRight:=Root;

Root^.NewRight:=Nil;

RightRange:=Root;

end

else

begin { ielikt pirms HelpPoint }

Root^.NewLeft:=HelpPoint^.NewLeft;

HelpPoint^.NewLeft:=Root;

Root^.NewRight:=HelpPoint;

If Root^.NewLeft<>Nil then Root^.NewLeft^.NewRight:=Root;

end;

procedure ViewTree( P : PCodElement );

{ --- kodesanas virknu pieskirsana lapam --- }

Var Mask,I : word;

begin

Inc(CounterBite);

If P^.P0<>Nil then ViewTree( P^.P0 );

If P^.P1<>Nil then

begin

Mask:=(1 SHL (16-CounterBite));

BiteChain:=BiteChain OR Mask;

ViewTree( P^.P1 );

Mask:=(1 SHL (16-CounterBite));

BiteChain:=BiteChain XOR Mask;

end;

If (P^.P0=Nil) and (P^.P1=Nil) then

begin

P^.BiteChain:=BiteChain;

P^.LengthBiteChain:=CounterBite-1;

end;

Dec(CounterBite);

end;

procedure CreateCompressCode;

{ --- mainigo anulesana un koka lasisana no augsas --- }

begin

BiteChain:=0;

CounterBite:=0;

Root^.Key:=False;

ViewTree(Root);

end;

procedure DeleteTree;

{ --- koka dzesana --- }

Var P : PCodElement;

begin

CurPoint:=LeftRange;

While CurPoint<>Nil do

begin

If (CurPoint^.P0<>Nil) and (CurPoint^.P1<>Nil) then

begin

If CurPoint^.NewLeft <> Nil then

CurPoint^.NewLeft^.NewRight:=CurPoint^.NewRight;

If CurPoint^.NewRight <> Nil then

CurPoint^.NewRight^.NewLeft:=CurPoint^.NewLeft;

If CurPoint=LeftRange then LeftRange:=CurPoint^.NewRight;

If CurPoint=RightRange then RightRange:=CurPoint^.NewLeft;

P:=CurPoint;

CurPoint:=P^.NewRight;

Dispose(P);

end

else CurPoint:=CurPoint^.NewRight;

end;

procedure SaveBufHeader;

{ --- bufera ieraksta arhiva nos --- }

Type

ByteField = array[0..6] of byte;

Const

Header : ByteField = ( $56, $53, $31, $00, $00, $00, $00 );

begin

If Create then

begin

Move(Header,OutBuf[0],7);

OutCounter:=7;

end

else

begin

Move(Header[3],OutBuf[0],4);

OutCounter:=4;

end;

procedure SaveBufFATInfo;

{ --- bufera ieraksta informaciju par failuзапись --- }

Var I : byte;

St : PathStr;

R : SearchRec;

begin

St:=ParamStr(3);

For I:=0 to Length(St)+1 do

begin

OutBuf[OutCounter]:=byte(Ord(St[I]));

Inc(OutCounter);

end;

FindFirst(St,$00,R);

Dec(OutCounter);

Move(R.Time,OutBuf[OutCounter],4);

OutCounter:=OutCounter+4;

OutBuf[OutCounter]:=R.Attr;

Move(R.Size,OutBuf[OutCounter+1],4);

OutCounter:=OutCounter+5;

end;

procedure SaveBufCodeArray;

{ --- saglabat frekfencu sastapsanas masivu failaa --- }

Var I : byte;

begin

For I:=0 to 255 do

begin

OutBuf[OutCounter]:=Hi(CodeTable[I]^.CounterEnter);

Inc(OutCounter);

OutBuf[OutCounter]:=Lo(CodeTable[I]^.CounterEnter);

Inc(OutCounter);

end;

procedure CreateCodeArchiv;

{ --- saspiesanas koda veidosana --- }

begin

InitCodeTable; { koda tabulas veidosana }

CounterNumberEnter; { sastapsanas frekvencu skaitisana }

SortQueueByte; { sortesana pec sastapsanas biezuma }

SaveBufHeader; { salgabat arhiva nos bufera }

SaveBufFATInfo; { saglaba FAT informaciju par failu }

SaveBufCodeArray; { saglaba masivu ar sastapsanas frekvenci failaa }

CreateTree; { frekvencu koka izveidosana }

CreateCompressCode; { saspiesta koda veidosana }

DeleteTree; { frekvena koka dzesana }

end;

procedure PakOneByte;

{ --- saspiesana un parsutisana uz izejas buferu baitu --- }

Var Mask : word;

Tail : boolean;

begin

CRC:=CRC XOR InBuf[InCounter];

Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHR CounterBite;

OutWord:=OutWord OR Mask;

CounterBite:=CounterBite+CodeTable[InBuf[InCounter]]^.LengthBiteChain;

If CounterBite>15 then Tail:=True else Tail:=False;

While CounterBite>7 do

begin

OutBuf[OutCounter]:=Hi(OutWord);

Inc(OutCounter);

If OutCounter=(SizeOf(OutBuf)-4) then

begin

BlockWrite(OutputF,OutBuf,OutCounter,NumWritten);

OutCounter:=0;

end;

CounterBite:=CounterBite-8;

If CounterBite<>0 then OutWord:=OutWord SHL 8 else OutWord:=0;

end;

If Tail then

begin

Mask:=CodeTable[InBuf[InCounter]]^.BiteChain SHL

(CodeTable[InBuf[InCounter]]^.LengthBiteChain-CounterBite);

OutWord:=OutWord OR Mask;

end;

Inc(InCounter);

If (InCounter=(SizeOf(InBuf))) or (InCounter=NumRead) then

begin

InCounter:=0;

BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead);

end;

procedure PakFile;

{ --- faila saspiesana --- }

begin

ResetFile;

SearchNameInArchiv;

If NormalWork then

begin

BlockRead(InputF,InBuf,SizeOf(InBuf),NumRead);

OutWord:=0;

CounterBite:=0;

OutCounter:=0;

InCounter:=0;

CRC:=0;

CreateCodeArchiv;

While (NumRead<>0) do PakOneByte;

OutBuf[OutCounter]:=Hi(OutWord);

Inc(OutCounter);

OutBuf[OutCounter]:=CRC;

Inc(OutCounter);

BlockWrite(OutputF,OutBuf,OutCounter,NumWritten);

DisposeCodeTable;

ClosePakFile;

end;

procedure ResetUnPakFiles;

{ --- faila atversana --- }

begin

InCounter:=7;

St:='';

repeat

St[InCounter-7]:=Chr(InBuf[InCounter]);

Inc(InCounter);

until InCounter=InBuf[7]+8;

Assign(InterF,St);

Rewrite(InterF,1);

ErrorByte:=IOResult;

ErrorMessage;

If NormalWork then

begin

WriteLn('UnPak file : ',St,'...');

Move(InBuf[InCounter],TimeUnPakFile,4);

InCounter:=InCounter+4;

AttrUnPakFile:=InBuf[InCounter];

Inc(InCounter);

Move(InBuf[InCounter],LengthArcFile,4);

InCounter:=InCounter+4;

end;

procedure CloseUnPakFile;

{ --- faila aizversana --- }

begin

If not NormalWork then Erase(InterF)

else

begin

SetFAttr(InterF,AttrUnPakFile);

SetFTime(InterF,TimeUnPakFile);

end;

Close(InterF);

end;

procedure RestoryCodeTable;

{ --- koda tabulas veidosana pec arhivu faila --- }

Var I : byte;

begin

InitCodeTable;

For I:=0 to 255 do

begin

CodeTable[I]^.CounterEnter:=InBuf[InCounter];

CodeTable[I]^.CounterEnter:=CodeTable[I]^.CounterEnter SHL 8;

Inc(InCounter);

CodeTable[I]^.CounterEnter:=CodeTable[I]^.CounterEnter+InBuf[InCounter];

Inc(InCounter);

end;

procedure UnPakByte( P : PCodElement );

{ --- baita atpakosana --- }

Var Mask : word;

begin

If (P^.P0=Nil) and (P^.P1=Nil) then

begin

OutBuf[OutCounter]:=P^.Index;

Inc(OutCounter);

Inc(LengthOutFile);

If OutCounter = (SizeOf(OutBuf)-1) then

begin

BlockWrite(InterF,OutBuf,OutCounter,NumWritten);

OutCounter:=0;

end;

end

else

begin

Inc(CounterBite);

If CounterBite=9 then

begin

Inc(InCounter);

If InCounter = (SizeOf(InBuf)) then

begin

InCounter:=0;

BlockRead(OutputF,InBuf,SizeOf(InBuf),NumRead);

end;

CounterBite:=1;

end;

Mask:=InBuf[InCounter];

Mask:=Mask SHL (CounterBite-1);

Mask:=Mask OR $FF7F; { visu bitu uzst iznemot vecako }

If Mask=$FFFF then UnPakByte(P^.P1)

else UnPakByte(P^.P0);

end;

procedure UnPakFile;

{ --- faila atpakosana --- }

begin

BlockRead(OutputF,InBuf,SizeOf(InBuf),NumRead);

ErrorByte:=IOResult;

ErrorMessage;

If NormalWork then ResetUnPakFiles;

If NormalWork then

begin

RestoryCodeTable;

SortQueueByte;

CreateTree; { frekvencu koka veidosana }

CreateCompressCode;

CounterBite:=0;

OutCounter:=0;

LengthOutFile:=0;

While LengthOutFile

UnPakByte(Root);

BlockWrite(InterF,OutBuf,OutCounter,NumWritten);

DeleteTree;

DisposeCodeTable;

end;

CloseUnPakFile;

end;

{ ------------------------- main text ------------------------- }

begin

DeleteFile:=False;

NormalWork:=True;

ErrorByte:=0;

WriteLn;

ResetArchiv;

If NormalWork then

begin

St:=ParamStr(1);

Case St[1] of

'a','A' : PakFile;

'm','M' : begin

DeleteFile:=True;

PakFile;

end;

'e','E' : UnPakFile;

else ;

end;

CloseArchiv;

end.

7. Secinājumi

Tagad izskatīsim maksimumu, kuru mēs varam sasniegt ar dažādam kombinācijām no optimāla koka, kas nav simetrisks. Sanāks ka mēs varam dabūt:

Simbolu Skaits	Bitu skaits
4	2
8	3
16	4
32	5
64	6
128	7
2	8
256

Iznāk 254 optimizēti simbolu kodi. Ir nepieciešami kodi vēl 2 simboliem. Mēs varam paņemt 2 8 bit simbolus, lai pilnība pārklāt ASCII tabulu. Sanāk kā mums ir 256 kombinācijas ar kuram mēs varam kodēt baitu, no tām ir tikai 2 ar 8 bitiem. Ja mēs saskaitīsim bitu skaitu, kas to ļauj, tad dabūsim 1554 bitus vai 195 baitus. Tas nozīmē, kā mēs varam saspiest 256 byte līdz 195 vai arī uz 33%, tas nozīmē, ka ideāla gadījumā Hafmana algoritms ļauj sasniegt 33% saspiešanu, kad tas tiek pielietots baitu līmeni.

Visi aprēķini tika veikti neprefikses Hafmana kodam, tas ir kodam, kuru nevar identificēt viennozīmīgi. Piemēram kodu A – 01011 un B – 0101. Ja mēs saņemsim šos kodus pa vienam bitam, tad saņemot bitus 0101 mēs nevārēsim viennozīmīgi pateikt kuru no kodiem mēs saņemam, t.k. Nākamais bits var būt gan turpinājums, gan nākamais kods.

Ir nepieciešams piebilst, ka visvienkāršākais veids ka uztaisīt prefiksa kodu ir parastais binārais koks. Ja uzmanīgi izpētīt iegūto koku, tad kļūs skaidrs ka kodi tajā ir prefiksie.

Vēl viena īpašība – Hafmana algoritms pieprasa lasīt ieejas failu divas reizes. Pirmo reizi skaitot simbolus un otro reizi veicot kodēšanu.

Kopumā var secināt kā Hafmana pats par sevi labi optimizē kodu, bet neļauj sasniegt pietiekoši lielu saspiešanās pakāpi, bet kopā ar citiem algoritmiem rezultativitāte ievērojami pieaug. Vienā no galvenām Hafmana koda priekšrocībām ir algoritma adaptivitāte, tas nozīme, ka kods vienmēr ir optimāls, strādājot ar jebkuru avotu.

8. Bibliogrāfiskais saraksts

1. http://en.wikipedia.org/wiki/David_A._Huffman

2. http://algolist.manual.ru/compress/standard/huffman.php

3. http://www.codenet.ru/progr/alg/huffcode.php

* Mantkarīgs algaritms (Greedy algorithm) - algoritms kas ļāuj atrāst lokāli optimālus risinājumus katrā etapā, pieļaujot, ka arī gala risinājums būs optimāls.

Bezmaksas referāti skolai

Hafmana kods

RĪGAS TEHNISKĀ UNIVERSITĀTE

1. Saturs

2. Ievads

3. Biogrāfija

4. Teorija

5. Realizācija

6. Realizācija uz Pascal

7. Secinājumi

8. Bibliogrāfiskais saraksts

Nav komentāru:

Ierakstīt komentāru