The Shannon–Fano algorithm doesn't always generate an optimal code. In 1952, David A. Huffman gave a different algorithm that always
produces an optimal tree for
any given probabilities. While the Shannon–Fano tree is created from the root
to the leaves, the Huffman
ü Procedure for Huffman Algorithm:
1. Create a
leaf node for each symbol algorithm works from leaves to the root in the
opposite direction and add it to frequency of occurrence.
there is more than one node in the queue:
Remove the two nodes of lowest probability or
frequency from the queue
Prepend 0 and 1 respectively to any code already
assigned to these nodes
Create a new internal node with these two nodes as
children and with probability equal to the sum of the two nodes' probabilities.
Add the new node to the queue.
The remaining node is the root node and the tree is
ü Tree diagram: