Huffman Coding – Basic Implementation
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