10 b IMPLEMENTATION OF HUFFMAN CODING
AIM:
To write a java program to implement
Huffman Coding
ALGORITHM:
1.Sort the
message ensemble by decreasing probability.
2. N is the cardinal of the
message ensemble (number of different messages).
3.Compute the integer n_0 such as
2<=n_0<=D and (N-n_0)/(D-1) is integer.
4. Select the n_0 least probable
messages, and assign them each a digit code.
5. Substitute the selected messages by
a composite message summing their probability, and re-order it.
6.While there remains more than one message,
do steps thru 8.
7.
Select D least probable messages, and assign them each a digit code.
8.
Substitute the selected messages by a composite message summing their
probability, and re-order it.
9. The code of each message is given by
the concatenation of the code digits of the aggregate they've been put in.
PROGRAM :
import java.util.*;
abstract class
HuffmanTree implements Comparable<HuffmanTree>
{
public final int
frequency;
public
HuffmanTree(int freq)
{
frequency = freq;
}
public int
compareTo(HuffmanTree tree)
{
return frequency -
tree.frequency;
}
}
class HuffmanLeaf
extends HuffmanTree
{
public final char
value;
public
HuffmanLeaf(int freq, char val)
{
super(freq);
value = val;
}
}
class HuffmanNode
extends HuffmanTree
{
public final
HuffmanTree left, right;
public
HuffmanNode(HuffmanTree l, HuffmanTree r)
{
super(l.frequency +
r.frequency);
left = l;
right = r;
}
}
public class
HuffmanCode
{
public static
HuffmanTree buildTree(int[] charFreqs)
{
PriorityQueue<HuffmanTree>
trees = new PriorityQueue<HuffmanTree>();
for (int i = 0; i
< charFreqs.length; i++)
if (charFreqs[i]
> 0)
trees.offer(new
HuffmanLeaf(charFreqs[i], (char)i));
assert trees.size()
> 0;
while (trees.size()
> 1)
{
HuffmanTree a =
trees.poll();
HuffmanTree b =
trees.poll();
trees.offer(new
HuffmanNode(a, b));
}
return trees.poll();
}
public static void
printCodes(HuffmanTree tree, StringBuffer prefix)
{
assert tree != null;
if (tree instanceof
HuffmanLeaf)
{
HuffmanLeaf leaf =
(HuffmanLeaf)tree;
System.out.println(leaf.value
+ "\t" + leaf.frequency + "\t" + prefix);
} else if (tree
instanceof HuffmanNode)
{
HuffmanNode node =
(HuffmanNode)tree;
prefix.append('0');
printCodes(node.left,
prefix);
prefix.deleteCharAt(prefix.length()-1);
prefix.append('1');
printCodes(node.right,
prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}
public static void
main(String[] args)
{
String test =
"this is an example for huffman encoding";
int[] charFreqs =
new int[256];
for (char c :
test.toCharArray())
charFreqs[c]++;
HuffmanTree tree =
buildTree(charFreqs);
System.out.println("SYMBOL\tWEIGHT\tHUFFMAN
CODE");
printCodes(tree, new
StringBuffer());
}
}