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.
- What is the advantage to using Bloom filters?
- Why isn't the space complexity of program adding values to a letter keyed hash map linear?
- Why is O(n) better than O( nlog(n) )?
- How to check if a struct is NULL in C or C++
- Fastest way to generate binomial coefficients
- Enumerate all full (labeled) binary tree
- A way to resize a stack (or other dynamically resizable types)
- How to implement deque data structure in javascript?
- Circular buffer in JavaScript
- npm-hosted libraries for circular/ring buffers
- How can the accuracy of a Bloom filter be improved by introducing other data structures?
- Stack pop using linked list - Python
- Having trouble understanding Linked List in C
- Simplest code for array intersection in javascript
- Converting entity list into JTree model
- Most efficient algorithm to compute set difference?
- Strategies for tracking N quasi-periodic samples over an unbounded duration
- When should I use the HashSet<T> type?
- Efficient algorithm that returns a list of unique lists given a list of of lists as input
- What is the difference between Lists, ArrayLists, Maps, HashMaps, Collections etc..?
- how to properly initialize an array?
- Does a standard implementation of a Circular List exist for C++?
- Add a node to a linked list that is implemented with two lists
- PHP Solution to Leetcode "Group Anagrams" without Set Data Structure
- Visual C++ equivalent of GCC's __attribute__ ((__packed__))
- Debugging algorithm that merges two lists that are already sorted using circular shifts
- Change all occurrences of an Int in a linked list using IntNode Java
- How to index into second level of data structure
- Is there a way to do an Excel INDEX/MATCH within Python using two dataframes as inputs
- Double-Array Trie Question