A ternary code for an alphabet is a wayof writing each of its symbols as a distinct ternary string (i.e as a sequence of 0's, 1's and 2's). Design a greedy algorithm that, given an alphabet and symbol frequencies as input, outputs a prefix-free ternary code with the minimum-possible average encoding length. Pls share a sample with symbols and frequencies and prove that algorithm works. Important Note to the solution: Instead of grouping together the two with lowest frequency into pairs that have the smallest total frequency, we will group together the three with lowest frequency in order to have a final result that is a ternary tree. The analysis of optimality is almost identical to the binary case. We are placing the symbols of lowest frequency lower down in the final tree and so they will have longer codewords than the more frequently occurring symbols.
A ternary code for an alphabet is a wayof writing each of its symbols as a distinct ternary string (i.e as a sequence of 0's, 1's and 2's). Design a greedy
Important Note to the solution:
Instead of grouping together the two with lowest frequency into pairs that have the smallest total frequency, we will group together the three with lowest frequency in order to have a final result that is a ternary tree. The analysis of optimality is almost identical to the binary case. We are placing the symbols of lowest frequency lower down in the final tree and so they will have longer codewords than the more frequently occurring symbols.
The problem you've described is similar to Huffman coding, a well-known algorithm for constructing variable-length prefix-free codes. In this case, we'll adapt Huffman coding to create a ternary tree, where symbols are encoded with ternary strings (sequences of 0's, 1's, and 2's). The goal is to minimize the average encoding length. The algorithm is as follows:
Greedy Ternary Huffman Coding Algorithm:
Start with a list of nodes, each representing a symbol and its frequency from the input alphabet and frequencies.
While there are more than three nodes in the list, do the following: a. Select the three nodes with the lowest frequencies. b. Merge these three nodes into a new node, creating a ternary tree. c. Set the frequency of the new node to be the sum of the frequencies of the merged nodes. d. Add the new node back to the list.
The remaining node in the list is the root of the ternary tree.
Traverse the tree to assign ternary codes to symbols:,a. Select the three nodes with the lowest frequencies. b. Merge these three nodes into a new node, creating a ternary tree. c. Set the frequency of the new node to be the sum of the frequencies of the merged nodes. d. Add the new node back to the list.
The remaining node in the list is the root of the ternary tree.
Traverse the tree to assign ternary codes to symbols: a. Starting at the root, traverse the tree to each leaf node. b. For each left branch taken, append '0' to the code, for each middle branch append '1', and for each right branch append '2'.
The ternary codes for each symbol are the paths from the root to the respective leaf nodes.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
