:
. , , , .
, . , , , .
, , . .
, , . , , , , , , .
2
1. ( , (.1 . 3), 6 )+ TTree
2. ( )
3. ( + )
, , / .
-, .
:
1. .
2. - .
:
1. ( )
2. m1 .
3. n0 , , ( ) n0 :
2 <= n0 <= m2
n0 = m1 - a (m2 - 1)
a , m1 m2 .
4. m2 , , .
|
|
|
5. , m2 1.
, 1, , m2 ..
m2 , , 0 m2-1. ( ). , , , .
TTree THuffman:
TTree:
TTree = class(TObject)
private
fchild0: TTree;
fchild1: TTree;
fleaf: Boolean;
fcharacter: Integer;
fweight: Integer;
public
procedure Tree(character, weight: integer; leaf: boolean);
procedure traverse(code: string; h: THuffman);
property child0: TTree read fchild0 write fchild0;
property child1: TTree read fchild1 write fchild1;
property leaf: Boolean read fleaf write fleaf;
property character: Integer read fcharacter write fcharacter;
property weight: Integer read fweight write fweight;
end;
fchild0/1 0 1
fleaf
fcharacter
fweight
THuffman:
THuffman = class(TObject)
private
fweights: array [0..ALPHABETSIZE-1] of Integer;
fcode: array [0..ALPHABETSIZE-1] of String:
ftree: array [0..ALPHABETSIZE-1] of TTree;
function GetCodeValue(Index: Integer): String;
function GetTreeValue(Index: Integer): TTree;
function GetWeightValue(Index: Integer): Integer;
procedure SetCodeValue(Index: Integer; const Value: String);
procedure SetTreeValue(Index: Integer; const Value: TTree);
procedure SetWeightValue(Index: Integer; const Value: Integer);
public
procedure makeCode;
procedure growTree(var data: array of Integer);
function getLowestTree(used: integer): integer;
function coder(var data: array of integer): string;
function decoder(data: string): string;
property weights[Index: Integer]: Integer read GetWeightValue write SetWeightValue;
property code[Index: Integer]: String read GetCodeValue write SetCodeValue;
property tree[Index: Integer]: TTree read GetTreeValue write SetTreeValue;
end;
fweights
fcode
ftree
procedure TTree.traverse(code: String; h: THuffman);
begin
if leaf then
begin
h.code[Ord(character)]:= code;
ShowMessage(': ' + Chr(character) +' '+' : '+IntToStr(weight) +' '+' :'+ code);
end;
if child0 <> nil then child0.traverse(code + '0', h);
if child1 <> nil then child1.traverse(code + '1', h);
end;
function THuffman.getLowestTree(used: integer): integer;
var
min, i: Integer;
begin
min:= 0;
for i:=1 to used-1 do if tree[i].weight < tree[min].weight then min:= i;
Result:= min;
end;
1 0
function THuffman.coder(var data: array of Integer): String;
|
|
|
var
str: String;
i: Integer;
begin
str:= '';
for i:=0 to High(data) do str:= str + code[data[i]];
Result:= str;
end;
procedure THuffman.growTree(var data: array of Integer);
var
i, c, w, min, used, weight0: Integer;
temp: TTree;
begin
for i:=0 to ALPHABETSIZE-1 do weights[i]:= 0;
for i:=0 to High(data) do weights[data[i]]:= weights[data[i]] + 1;
used:= 0;
for c:=0 to ALPHABETSIZE-1 do
begin
w:= weights[c];
if w <> 0 then
begin
inc(used);
tree[used-1]:= TTree.Create;
tree[used-1].Tree(c, w, true);
end;
end;
while used > 1 do
begin
min:= getLowestTree(used);
weight0:= tree[min].weight;
temp:= TTree.Create;
temp.child0:= tree[min];
dec(used);
tree[min]:= tree[used];
min:= getLowestTree(used);
temp.child1:= tree[min];
temp.weight:= weight0 + tree[min].weight;
tree[min]:= temp;
end;
end;
procedure THuffman.makeCode;
begin
tree[0].traverse('', self);
end;
function THuffman.GetCodeValue(Index: Integer): String;
begin
Result:= fcode[Index];
end;
function THuffman.GetTreeValue(Index: Integer): TTree;
begin
Result:= ftree[Index];
end;
function THuffman.GetWeightValue(Index: Integer): Integer;
begin
Result:= fweights[Index];
end;
procedure THuffman.SetCodeValue(Index: Integer; const Value: String);
begin
fcode[Index]:= Value;
end;
procedure THuffman.SetTreeValue(Index: Integer; const Value: TTree);
begin
ftree[Index]:= Value;
end;
procedure THuffman.SetWeightValue(Index: Integer; const Value: Integer);
begin
fweights[Index]:= Value;
end;
:
1
3
4
3
2
1
1
_ - 3
:
| 00 | 01 - | ||||||||||
| 101 _ | 111 | ||||||||||
:
4 ─
5 ─
