How to count the bits in a Huffman tree
I am looking at the below Huffman tree, the corresponding frequency table and the subtotal table. That table calculates the subtotal bits. I want to know how to count the subtotal bits.
In the first row of the subtotal table, code 0 maps to 15. I understand that because A has a count of 15. But why code 100 maps to 21? 100 represents the node B and B has a count of 7. I would think that for 100 we should calculate 7 + 15 = 22, but the table has 21. Why?
Solution
The column "Subtotal (#bits)" is the product of bit-length and count (frequency), and this represents how many bits in the encoded message are dedicated to represent all symbols B.
So we can derive the numbers as follows:
| Symbol | Count | Code | #bits in Code | Subtotal (#bits) |
|---|---|---|---|---|
| A | 15 | 0 | 1 | 15 x 1 = 15 |
| B | 7 | 100 | 3 | 7 x 3 = 21 |
| C | 6 | 101 | 3 | 6 x 3 = 18 |
| D | 6 | 110 | 3 | 6 x 3 = 18 |
| E | 5 | 111 | 3 | 5 x 3 = 15 |
| TOTAL = 87 |
87 is thus the length of the encoded message.
- Detecting Duplicates Using Divide and Conquer - Merge Sort
- Dijkstra's algorithm for directed graph with positive weights and a cycle
- How to find level order traversal from Preorder and Inorder Traversal
- Visual C++ equivalent of GCC's __attribute__ ((__packed__))
- I am trying to reverse the stack using recursion. What is being passed in function fun()? s is an object of class stack
- Modify 2d array to create nested datasets when specific key is encountered
- JS - recursive function on multidimensional array to filter out only "checked" items (and its parents if a child is selected)
- Comparing two similar objects (holding same keys) and returning key value pairs that are different
- Linked List Replacement Function with Head, Tail, and Size Management
- Efficient Array Storage for Binary Tree
- How to render data and initialize an UI event handling upon this data after the data has been loaded by an asynchronous API call?
- Hackerrank Repeated String infinite loop problem
- Using asterisk and spaces print the letter R [ 21*20]
- Split a collection into `n` parts with LINQ?
- How can I enhance the time complexity of arranging bricks into stacks based on specific conditions?
- List-like data-structure with O(1) access in practice but O(N) access for huge sizes; What is it?
- Octree implementation in Rust: why is the insert function duplicating insertions and how could I go about fixing this?
- Data structures for compiled XPath queries
- how to traverse an NxN grid diagonally
- Name of binary data structures that contain fixed-length components?
- Insert after specific element in LinkedList java
- inserting in binary tree doesn't work using java
- Generate simple URL patterns from a list of examples
- Explain time complexity of permutations using the mathematical expression
- segfault with no reason in sight while implementing a dsu in c (probably a silly mistake)
- Why AddAfter() has constant time?
- 2D peak finding algorithm in O(n) worst case time?
- C# Multiway Linked List
- Find Elements occurring odd number of times in a list
- Difference between back tracking and dynamic programming