I can solve similar problem with 4 symbols. But I cannot solve it when the number of symbols is more than 4. However, here is the probability of the symbols:
I need to develop optimal code with the Huffman method.
The tree which I got looks like this:
Here is how I reduced the symbols:
On
Just follow the algorithm: combine the least frequent pair, and keep doing so. Here the least frequent are $X_1$ and $X_{11}$; they combine to make a new node $\{X_1,X_{11}\}$ with weight $0,01+0,02=0,03$. Now your list of nodes looks like this, after I reorder it by weight:
$$\begin{array}{rcc} X_i:&X_8&\{X_1,X_{11}\}&X_7&X_5&X_3&X_{10}&X_{12}&X_2&X_6&X_9&X_4\\ p_i:&0,03&0,03&0,04&0,05&0,06&0,07&0,08&0,1&0,11&0,2&0,23 \end{array}$$
The smallest two are $X_8$ and $\{X_1,X_{11}\}$, so we combine them to make a new node $\{X_1,X_8,X_{11}\}$ of weight $0,03+0,03=0,06$, and we now have the following list:
$$\begin{array}{rcc} X_i:&X_7&X_5&X_3&\{X_1,X_8,X_{11}\}&X_{10}&X_{12}&X_2&X_6&X_9&X_4\\ p_i:&0,04&0,05&0,06&0,06&0,07&0,08&0,1&0,11&0,2&0,23 \end{array}$$
Now combine $X_7$ and $X_5$ to make a node $\{X_5,X_7\}$ of weight $0,09$, reducing the list to this:
$$\begin{array}{rcc} X_i:&X_3&\{X_1,X_8,X_{11}\}&X_{10}&X_{12}&\{X_5,X_7\}&X_2&X_6&X_9&X_4\\ p_i:&0,06&0,06&0,07&0,08&0,09&0,1&0,11&0,2&0,23 \end{array}$$
The next step combines $X_3$ with $\{X_1,X_8,X_{11}\}$, and the one after that combines $X_{10}$ and $X_{12}$ to produce the list
$$\begin{array}{rcc} X_i:&\{X_5,X_7\}&X_2&X_6&\{X_1,X_3,X_8,X_{11}\}&\{X_{10},X_{12}\}&X_9&X_4\\ p_i:&0,09&0,1&0,11&0,12&0,15&0,2&0,23 \end{array}$$
At this stage your your graph looks like this:
* * * * * * *
/ \ X2 X6 / \ / \ X9 X4
/ \ / \ / \
X5 X7 * * X10 X12
X3 / \
/ \
* *
/ \ X8
/ \
* *
X1 X11
Can you finish it now? Just keep on doing the same thing until it becomes a single tree. There are seven separate pieces now, so that will take six more steps. Once you have the tree, we can worry about how to get the actual Huffman code from it.
Added: There are two possible trees; here’s a rough sketch of one of them.
On
In response to the request for a drawing of the tree as opposed to a list I am sending some Perl code that outputs an ASCII tree. I hope it can be of use to those studying Huffman codes and perhaps make it easier to understand what is going on.
Here are some examples:
$ ./huffman-tree.pl 0.1 0.1 0.1 0.4 0.3
+-0--X004 0.400000 0
|
+-1--+-0--X005 0.300000 10
|
+-1--+-0--X003 0.100000 110
|
+-1--+-0--X001 0.100000 1110
|
+-1--X002 0.100000 1111
$ ./huffman-tree.pl 0.01 0.1 0.06 0.23 0.05 0.11 0.04 0.03 0.2 0.07 0.02 0.08
+-0--+-0--X009 0.200000 00
| |
| +-1--+-0--X006 0.110000 010
| |
| +-1--+-0--X003 0.060000 0110
| |
| +-1--+-0--X008 0.030000 01110
| |
| +-1--+-0--X001 0.010000 011110
| |
| +-1--X011 0.020000 011111
|
+-1--+-0--X004 0.230000 10
|
+-1--+-0--+-0--X010 0.070000 1100
| |
| +-1--X012 0.080000 1101
|
+-1--+-0--+-0--X007 0.040000 11100
| |
| +-1--X005 0.050000 11101
|
+-1--X002 0.100000 1111
$ ./huffman-tree.pl 15 7 6 6 5
scaling by a factor of 39 at ./huffman-tree.pl line 87.
+-0--X001 0.384615 0
|
+-1--+-0--+-0--X005 0.128205 100
| |
| +-1--X003 0.153846 101
|
+-1--+-0--X004 0.153846 110
|
+-1--X002 0.179487 111
This is the code.
#! /usr/bin/perl -w
#
sub max {
my ($a, $b) = @_;
return ($a<$b ? $b : $a);
}
sub calc_dims {
my ($path, $t) = @_;
$t->{path} = $path;
if(exists($t->{label})){
$t->{sumstr} = sprintf "%05f", $t->{sum};
$t->{width} = 2 + length($t->{label}) + length($path)
+ length($t->{sumstr});
$t->{height} = 1;
return;
}
calc_dims($path . '0', $t->{left});
calc_dims($path . '1', $t->{right});
$t->{width} =
5 + max($t->{left}{width}, $t->{right}{width});
$t->{height} =
1 + $t->{left}{height} + $t->{right}{height};
}
sub draw_tree {
my ($b, $x, $y, $t) = @_;
if(exists($t->{label})){
my (@letters) =
split(//, $t->{label} . ' ' . $t->{sumstr} .
' ' . $t->{path});
for(my $ltr=0; $ltr<scalar(@letters); $ltr++){
$b->[$y][$x+$ltr] = $letters[$ltr];
}
return;
}
$b->[$y][$x] = '+';
$b->[$y][$x+1] = '-';
$b->[$y][$x+2] = '0';
$b->[$y][$x+3] = '-';
$b->[$y][$x+4] = '-';
draw_tree($b, $x+5, $y, $t->{left});
my $pos;
for($pos=1; $pos<=$t->{left}{height}; $pos++){
$b->[$y+$pos][$x] = '|';
}
$y += $pos;
$b->[$y][$x] = '+';
$b->[$y][$x+1] = '-';
$b->[$y][$x+2] = '1';
$b->[$y][$x+3] = '-';
$b->[$y][$x+4] = '-';
draw_tree($b, $x+5, $y, $t->{right});
}
MAIN: {
my @freq = @ARGV;
die "need at least one symbol "
if scalar(@freq) == 0;
my $n = scalar(@freq);
my $total = 0;
for(my $pos=0; $pos<$n; $pos++){
my $val = $freq[$pos];
die "not a decimal number: $val"
if $val !~ /^\d+(\.\d*)?$/;
$total += $freq[$pos];
}
if(abs(1-$total) > 1e-12){
warn "scaling by a factor of $total";
for(my $pos=0; $pos<$n; $pos++){
$freq[$pos] /= $total;
}
}
my @pool;
for(my $pos=0; $pos<$n; $pos++){
my $label = sprintf "X%03d", ($pos+1);
push @pool,
{ sum => $freq[$pos], label => $label };
}
@pool = sort { $a->{sum} <=> $b->{sum} } @pool;
while(scalar(@pool) >= 2){
my ($ma, $mb);
$ma = shift @pool; $mb = shift @pool;
my $node = {
sum => $ma->{sum} + $mb->{sum},
left => $ma, right => $mb
};
my $pos;
for($pos = 0; $pos<scalar(@pool); $pos++){
last if $node->{sum} < $pool[$pos]->{sum};
}
splice @pool, $pos, 0, $node;
}
calc_dims('', $pool[0]);
my $board = [];
for(my $row=0; $row<$pool[0]->{height}; $row++){
push @$board, [(' ') x ($pool[0]->{width})];
}
draw_tree($board, 0, 0, $pool[0]);
for(my $row=0; $row<$pool[0]->{height}; $row++){
for(my $col=0; $col<$pool[0]->{width}; $col++){
print $board->[$row][$col];
}
print "\n";
}
1;
}
This algorithm is very simple, as the other posts point out. Doing your example on paper takes almost as long as writing a program, so here is the program.
First, some sample runs including your example.
The algorithm follows, implemented in Perl. There is not much to say about it: start with a forest of singleton trees and iteratively keep merging the two with the smallest sum value, recording the cumulative sums. Traverse the resulting tree with the path to a leaf giving the Huffman code of that leaf.
#! /usr/bin/perl -w # sub buildcode { my ($cref, $pref, $t) = @_; if(exists($t->{label})){ $cref->{$t->{label}} = $pref; return; } buildcode($cref, $pref . '0', $t->{left}); buildcode($cref, $pref . '1', $t->{right}); } MAIN: { my @freq = @ARGV; die "need at least one symbol " if scalar(@freq) == 0; my $n = scalar(@freq); my $total = 0; for(my $pos=0; $pos<$n; $pos++){ my $val = $freq[$pos]; die "not a decimal number: $val" if $val !~ /^\d+(\.\d*)?$/; $total += $freq[$pos]; } if(abs(1-$total) > 1e-12){ warn "scaling by a factor of $total"; for(my $pos=0; $pos<$n; $pos++){ $freq[$pos] /= $total; } } my @pool; for(my $pos=0; $pos<$n; $pos++){ push @pool, { sum => $freq[$pos], label => "X" . ($pos+1), }; } @pool = sort { $a->{sum} <=> $b->{sum} } @pool; while(scalar(@pool) >= 2){ my ($ma, $mb); $ma = shift @pool; $mb = shift @pool; my $node = { sum => $ma->{sum} + $mb->{sum}, left => $ma, right => $mb }; my $pos; for($pos = 0; $pos<scalar(@pool); $pos++){ last if $node->{sum} < $pool[$pos]->{sum}; } splice @pool, $pos, 0, $node; } my $code = {}; buildcode $code, '', $pool[0]; for(my $pos=0; $pos<$n; $pos++){ printf "X%02d %05f %s\n", $pos+1, $freq[$pos], $code->{'X' . ($pos+1)}; } 1; }