MHB Build Huffman Tree with Ternary System

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Algorithm
AI Thread Summary
The discussion outlines the process of building a Huffman Tree, starting with an array of unique characters and their frequencies. The initial steps involve creating leaf nodes for each character and constructing a min heap to prioritize nodes by frequency. The algorithm extracts the two nodes with the lowest frequencies, combines them into a new internal node, and continues this process until only one node remains, which becomes the root of the tree.An extension of the Huffman algorithm for a ternary system is proposed, where nodes can have three children instead of two. The modified steps include creating a min heap, extracting three nodes with the lowest frequencies, and forming a new internal node with these nodes as left, middle, and right children. The process repeats until a single node remains.The discussion raises the question of how to prove that this modified algorithm yields optimal ternary codes, indicating a need for further exploration into the theoretical foundations of the algorithm's efficiency in this context.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Wave)

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.


  • 1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

    2. Extract two nodes with the minimum frequency from the min heap.

    3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

    4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.
At a heap, a node can have at most $2$ children, right?So if we would like to generalize the Huffman algorithm for coded words in ternary system (i.e. coded words using the symbols $0$ , $1$ and $2$ ) what could we do? Do we have to create a tree all the nodes of which have $3$ children? (Thinking)
 
Technology news on Phys.org
I think that it would be as follows.

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.


  • 1. Create a leaf node for each unique character and build a min heap of all leaf nodes

    2. Extract three nodes with the minimum frequency from the min heap.

    3. Create a new internal node with frequency equal to the sum of the three nodes frequencies. Make the first extracted node as its left child, the second extracted node as its middle child and the third extracted node as its right child. Add this node to the min heap.

    4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.
How can we prove that the algorithm yields optimal ternary codes? (Thinking)
 
Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
I have a quick questions. I am going through a book on C programming on my own. Afterwards, I plan to go through something call data structures and algorithms on my own also in C. I also need to learn C++, Matlab and for personal interest Haskell. For the two topic of data structures and algorithms, I understand there are standard ones across all programming languages. After learning it through C, what would be the biggest issue when trying to implement the same data...
Back
Top