|
In these days almost every compression schema uses Huffman coding in one of the steps. Here you can find a basic implementation of this method. An integer array, as an input, is taken. Then using Huffman coding repeated numbers are placed into virtual tree and represented binary numbers are serially generated. This binary sequence can be used instead of original integer array.
The Algorithm 
Pascal Source Code uses crt;
type
ana= record
sayi, ytree :integer;
dur, yer :byte;
end;
var
A:array[1..50] of ana; Tree:array[1..512] of integer;
binary_dizi:array[1..10] of byte; toplam_dizi:array[1..200] of byte;
i,j,k,l,m,n,t,z,top,t_d:integer; ch:char;
Procedure oku;
begin
write('Size of array:');read(n);
for i:=1 to n do
begin
read(A[i].sayi);
end;
end;
Procedure BubbleSort;
var yedek:integer;
begin
for i:=1 to n-1 do
for j:=1 to n-i do
if A[j].sayi > A[j+1].sayi then
begin
yedek:=A[j].sayi;
A[j].sayi:=A[j+1].sayi;
A[j+1].sayi:=yedek;
end;
end;
Procedure Huffman_Tree;
begin
{******************Total Array**********************}
for i:=1 to 50 do a[i].dur:=0;
i:=1; z:=0;
while z=0 do
begin
top:=A[i].sayi+A[i+1].sayi;
k:=i+1;
t:=0;
while t=0 do
if (A[k].sayi<top)and(A[k].sayi<>0) then
inc(k)
else
begin
for l:=n+1 downto k+1 do
begin
A[l].sayi:=A[l-1].sayi;
A[l].dur:=A[l-1].dur;
end;
A[k].sayi:=top;
A[k].dur:=1;
t:=1;
inc(n);
A[k].yer:=i;
end;
inc(i,2);
if A[i+1].sayi=0 then z:=1;
end;
{------------------ Total Array ----------------------}
{******************Huffman Tree**********************}
Tree[1]:=A[n].sayi;A[n].ytree:=1;
Tree[2]:=A[A[n].yer].sayi; A[A[n].yer].ytree:=2;
Tree[3]:=A[A[n].yer+1].sayi;A[A[n].yer+1].ytree:=3;
for i:=n-1 downto 1 do
if A[i].dur=1 then
begin
j:=A[i].ytree;
t:=A[i].yer;
Tree[j+j]:=A[t].sayi;
A[t].ytree:=j+j;
Tree[j+j+1]:=A[t+1].sayi;
A[t+1].ytree:=j+j+1;
end;
{------------------Huffman Tree ----------------------}
end;
Procedure binary;
var yedek:integer;
begin
{******************Binary Code**********************}
for i:=1 to n do
begin
if A[i].dur=0 then
begin
j:=A[i].ytree;
k:=0;
while j>1 do
if (j mod 2)=0 then
begin
j:=j div 2;
inc(k);
binary_dizi[k]:=0;
end
else
begin
j:=(j-1) div 2;
inc(k);
binary_dizi[k]:=1;
end;
inc(k);
binary_dizi[k]:=1;
t:=k;
for j:=1 to (k div 2) do
begin
yedek:=binary_dizi[j];
binary_dizi[j]:=binary_dizi[t];
binary_dizi[t]:=yedek;
t:=t-1;
end;
write(A[i].sayi:3,'. numberīs equivalent: ');
for j:=1 to k do
begin
write(binary_dizi[j]);
inc(t_d);
toplam_dizi[t_d]:=binary_dizi[j];
end;
writeln;
end;
end;
{------------------Binary Code----------------------}
end;
Procedure TotalArray;
begin
writeln(' Total array...');
for i:=1 to t_d do write(Toplam_dizi[i]); writeln;
end;
Procedure decode;
begin
{******************Conversion from Binary to number**********************}
writeln('From above array original numbers are generated...');
i:=2; j:=1;
while i<=t_d do
begin
if Toplam_dizi[i]=0 then
j:=j+j
else
j:=j+j+1;
if (Tree[j+j]=0)and(Tree[j+j+1]=0) then
begin
writeln('Number:', Tree[j]);
inc(i);
j:=1;
end;
inc(i);
end;
{------------------ Conversion from Binary to number----------------------}
end;
BEGIN
clrscr;
oku;
BubbleSort;
Huffman_Tree;
t_d:=0;
binary;
TotalArray;
decode;
repeat ch:=readkey; until ch=#27; {Press Esc for exit}
END.
Sample Execution Size of array:7 65 100 160 120 45 10 15 10 . number's equivalent: 110100 15 . number's equivalent: 110101 45 . number's equivalent: 11011 65 . number's equivalent: 1100 100 . number's equivalent: 100 120 . number's equivalent: 101 160 . number's equivalent: 111 Total array... 110100110101110111100100101111 From above array original numbers are generated... Number:10 Number:15 Number:45 Number:65 Number:100 Number:120 Number:160
|
Studies 
