How Does Huffman Coding Compress Data With Example?

TL;DR

Huffman coding is a greedy technique that encodes frequently used characters with fewer bits and rare characters with more bits. For a 100-character message with frequencies A=50, B=10, C=30, D=5, E=3, F=2, ASCII needs 700 bits and fixed 3-bit coding needs 300 bits, but Huffman needs only 185 bits, or 1.85 bits per character.

Transcript

Hello friends, welcome to Gate Smashers. In this video, we are going to discuss about Huffman coding. And in this video, we are going to discuss all the important points related to Huffman coding which will be very beneficial for your competitive exams, even college or university level exams. So guys, like the video quickly, subscribe the c... Read More

Key Insights

• Huffman coding is a greedy technique used to encode and compress data. It works by assigning variable-length binary codes to characters based on their frequency, so the total number of bits needed to represent a message drops well below fixed-length schemes.
• ASCII encoding uses 7 bits per character because its range is 0 to 127, which is 128 characters, and the maximum value 127 is 1111111 in binary. Encoding a 100-character message in ASCII therefore consumes 700 bits in total.
• A custom fixed-length code can beat ASCII when the alphabet is small. Knowing the message uses only 6 character types (A, B, C, D, E, F) allows unique 3-bit codes such as A=000 and F=101, reducing the 100-character message from 700 bits to 300 bits.
• The Huffman tree is built bottom-up by repeatedly selecting the two smallest frequencies and merging them into a new node whose value is their sum. The merged node is added back into the list, and the process repeats until a single root node holds the total frequency.
• The placement convention in the example puts the smaller element on the left and the larger on the right. When two frequencies tie, either order works, but following one consistent pattern makes exam questions easier to solve reliably.
• Codes are read off the tree by labeling every left edge 0 and every right edge 1, then tracing the path from the root to each character. This yields A=0, B=100, C=11, and D=1010, and all codes are different from one another.
• The total encoded size is the sum of each character's frequency times its code length: 50x1 plus 10x3 plus 30x2 plus 5x4 plus 3x5 plus 2x5, which totals 185 bits compared with 700 bits for ASCII and 300 bits for 3-bit fixed coding.
• Average bits per character is total bits divided by total characters, giving 1.85 bits per character for Huffman versus 7 for ASCII and 3 for the fixed 3-bit scheme. This is the minimum number of bits required to represent the whole message.
• The core logic is that the highest-frequency character is placed nearest the root so it gets the fewest bits, while the lowest-frequency characters like E and F sit deepest and take the most bits, driving the overall bit count down.
• Compression improves transmission time because transmission time equals message size divided by bandwidth. Sending 185 bits instead of 700 bits over the same bandwidth cuts the time proportionally, since transmission time is directly proportional to message size.

Questions & Answers

Q: How does Huffman coding work step by step?

Start with the frequency of every character. Repeatedly pick the two minimum frequency elements and merge them into a new node whose value is their sum, placing the smaller element on the left and the larger on the right. Add the merged value back into the list and repeat. In the example, F=2 and E=3 merge into 5, that 5 merges with D=5 into 10, that 10 merges with B=10 into 20, then 20 merges with C=30 into 50, and finally 50 merges with A=50 to form the root of 100. Then label every left edge 0 and every right edge 1, and read each character's code as the path from the root down to it.

Q: Why does ASCII encoding need 7 bits per character?

ASCII encoding has a range of 0 to 127, which is 128 characters in total. To represent the largest value in that range, 127, in binary you need 1111111, which is seven 1s, and 0 is represented as seven 0s. Since the maximum value requires 7 bits, every character in the scheme is represented with 7 bits, whether it is A, B, C, or D. That means a message of 100 characters consumes 100 times 7, or 700 bits in total, to encode the whole message in digital format.

Q: What is the total number of bits for the Huffman example in the video?

The total is 185 bits. It is calculated by multiplying each character's frequency by the length of its Huffman code and summing the results: A appears 50 times with a 1-bit code giving 50, B appears 10 times with a 3-bit code giving 30, C appears 30 times with a 2-bit code giving 60, D appears 5 times with a 4-bit code giving 20, E appears 3 times with a 5-bit code giving 15, and F appears 2 times with a 5-bit code giving 10. Adding these gives 185 bits, compared with 700 bits for ASCII and 300 bits for a fixed 3-bit encoding of the same message.

Q: How do you calculate average bits per character in Huffman coding?

Divide the total number of bits used by the total number of characters in the message. In the example, Huffman coding takes 185 bits in total and the message has 100 characters, so the average is 185 divided by 100, which equals 1.85 bits per character. The same formula applies to the other schemes: ASCII takes 700 bits for 100 characters, giving 7 bits per character, and the fixed 3-bit encoding takes 300 bits for 100 characters, giving 3 bits per character. The 1.85 figure is the minimum number of bits required to represent the whole message.

Q: What are the Huffman codes for each character in the example?

Reading paths from the root with left edges labeled 0 and right edges labeled 1, A is represented by the single bit 0 because it sits one edge from the root. B is 1, 0, 0, which is 3 bits. C is 1, 1, which is 2 bits. D is 1, 0, 1, 0, which is 4 bits. E is reached by 1, 0, 1, 1, 1 and F by 1, 0, 1, 1, 0, each taking 5 bits. All of these codes are different from one another, which is what allows each character to be uniquely identified when the message is decoded.

Q: Why do high-frequency characters get shorter codes in Huffman coding?

The character with the highest frequency ends up nearest the root of the Huffman tree, so its path is short and it needs fewer bits. In the example, A has a frequency of 50 and is represented with just 1 bit, while E and F have the lowest frequencies of 3 and 2 and are placed deepest in the tree, requiring 5 bits each. Because the frequent character is multiplied by a small bit count and the rare characters by a large one, the composite total number of bits comes out as low as possible, which is the entire point of the greedy merging strategy.

Q: How does data compression reduce transmission time?

Transmission time is calculated as message size divided by bandwidth, so it is directly proportional to the size of the message. If the message is encoded in ASCII it is 700 bits, and the transmission time is 700 divided by whatever bandwidth is available. With Huffman coding the same message is only 185 bits, so the transmission time becomes 185 divided by the same bandwidth. A bigger message size means more transmission time, so shrinking the encoded message directly shrinks the time needed to send it. Compression also means storage is utilized in a more efficient way.

Q: What is the difference between fixed-length encoding and Huffman coding?

Fixed-length encoding assigns the same number of bits to every character regardless of how often it appears. ASCII uses 7 bits for all characters, and a custom scheme for a 6-character alphabet uses 3 bits for all of them, such as A=000, B=001, C=010, D=011, E=100, F=101. Huffman coding instead uses variable-length codes driven by frequency, giving A just 1 bit and E and F 5 bits each. For the same 100-character message, the three approaches cost 700 bits, 300 bits, and 185 bits respectively, so Huffman produces the smallest encoded message.

Summary & Key Takeaways

• Data encoding converts a message into 0s and 1s so a computer can store or transmit it. ASCII encoding covers the range 0 to 127, which is 128 characters, and since 127 in binary is 1111111, every character needs 7 bits. A 100-character message therefore takes 700 bits in ASCII.

• If the message only contains 6 distinct characters (A to F), each can be uniquely identified with 3 bits: A=000, B=001, C=010, D=011, E=100, F=101. That reduces the same 100-character message from 700 bits to 300 bits, because each character now consumes 3 bits instead of 7.

• Huffman coding builds a tree by repeatedly picking the two minimum frequency elements and merging them: F=2 with E=3 gives 5, then that 5 with D=5 gives 10, then that 10 with B=10 gives 20, then 20 with C=30 gives 50, then 50 with A=50 gives the root 100. Smaller element goes left, larger goes right.

• Labeling every left edge 0 and every right edge 1 gives the codes by reading the path from the root: A=0, B=100, C=11, D=1010, E=1011 (5 bits), F=10110 path shown as 5 bits. Total bits are 50x1 + 10x3 + 30x2 + 5x4 + 3x5 + 2x5 = 185 bits.

• Average bits per character is total bits divided by total characters. ASCII gives 700/100 = 7 bits per character, the 3-bit fixed scheme gives 300/100 = 3, and Huffman gives 185/100 = 1.85 bits per character, the minimum number of bits required to represent the whole message.

• Compression benefits both storage and transmission. Fewer bits means storage is utilized in an efficient way, and since transmission time equals message size divided by bandwidth, cutting a message from 700 bits to 185 bits directly cuts transmission time because time is directly proportional to message size.