Ternary Huffman. Trimedia Disks Inc. has developed “ternary” hard disks. Each cell on a disk can now store values 0, 1, or 2 (instead of just 0 or 1). To take advantage of this new technology, provide a modified Huffman algorithm for compressing sequences of characters from an alphabet of size n, where the characters occur with known frequencies f1; f2,..., fn. Your algorithm should encode each character with a variable-length codeword over the values 0, 1 , 2 such that no codeword is a prefix of another codeword and so as to obtain the maximum possible compression. Prove that your algorithm is correct.
Ternary Huffman encoding algorithm:
The ternary tree is a tree which contains the nodes in odd number. That is, each node contains either 0 or 3 children.
• It is labeled with the left child as “0”, mid child as “1”, and right child as “2”.
Constructing the codes for ternary Huffman tree:
• List all possible symbols with their frequencies.
• Find three symbols with the least frequency.
• Replace these by single set which contains all the three symbols, whose frequency is the sum of the individual frequency.
• Repeat the step until the list contains only one member.
Proof:
Initially, check whether the number of symbols is odd. If it is, then encode the symbol to form the full ternary tree.
• If need then, add a symbol with frequency 0 to make the number of symbols is odds.
• It is guaranteed to form the full optimal tree then, precede with binary case by a combination of three nodes left child as “0”, mid child as “1”, and right child as “2” with minimum frequency for each step to form the single node.
o Then, decreases the number of nodes by 2. If the symbol remains odd then, it continues the process.
Assume that the number of symbols is odd and non-leaf node “u” is an optimal tree. That is, it does not have three leaves (child nodes). Then,
• There is no loss of generality; assume that all children from node “u” are considered as leaves and that the “u” node contains the two children.
• If we delete the children of node “u” to get the better code, that is, full ternary tree.
• The full ternary tree is constructed by adding the 3 nodes to some current leaf, and it must have an odd number of nodes (child).
• It can be started from the root node.
o For every step, the number of nodes increased by 2.
Therefore, the modified Ternary Huffman encoding algorithm is correct.