Huffman Coding: Shorter Codes for Frequent Characters

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 16.11 Free with a free account

Huffman Coding: Shorter Codes for Frequent Characters

Data Structures and Algorithms · Chapter 16: Sorting, Selection, and Text ProcessingSection 16.11 · lesson 77 of 879 min · free with a free account

← Tries: Storing Vocabularies in Prefix TreesNext lesson: Graphs and Their Representations →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

How Huffman coding builds optimal prefix-free codes from frequencies.

  • Explain why variable-length codes must be prefix-free
  • Build a Huffman tree with a priority queue and read off its codewords
  • Decode a bit stream using the encoder's Huffman tree
  • Compare Huffman's average code length with the entropy and the file's header cost

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,317 words). Read along, or search it.

Opening Question

Eight Bits for Every Character

A plain text file spends eight bits on every character, whether it's the very common letter e, or the rare letter q. If common characters got short codes, and rare ones got long codes, the same text would take fewer bits. Huffman coding finds the best such code. But once codes have different lengths, how does a reader tell where each one ends?

Fixed-Length Codes

Three Bits Each for abracadabra

A fixed-length code gives every symbol a codeword of the same length. With k distinct symbols, b bits are enough when two to the power b is at least k. Twenty-six letters need five bits. All 256 byte values need eight. The word abracadabra has just five distinct letters, so three bits each would do: 33 bits, instead of 88. But the letters aren't equally common. a makes up five of the eleven, while c and d appear once. A fixed code spends three bits on a, just as on d.

The Catch

When One Codeword Begins Another

Variable lengths have a catch. With no separators between codewords, the reader must work out where each one ends. Take a = 0, b = 1, and c = 01. Now read the bits 0101. They could be a b a b, or a b c, or c a b, or c c. Four different texts, and the receiver can't know which was meant. The cause: the codeword 0 is the beginning of the codeword 01.

Prefix-Free Codes

Symbols on the Leaves of a Tree

The fix is a prefix-free code, where no codeword is the beginning of another. Then a codeword, once read, can't be the start of a longer one. With a = 0, b = 10, and c = 11, the bits 0101100 read only one way: a, b, c, a, a. A binary tree guarantees this. Label every left edge 0, every right edge 1, and put the symbols on the leaves. Each codeword is the path from the root to its leaf. A path can't continue past a leaf, so no codeword can begin another. Every fixed-length code is prefix-free too, since words of equal length can't begin one another.

Huffman's Method

Join the Two Lightest Trees

Huffman's goal is the smallest total length: each symbol's frequency, times its codeword length, added up. So the rarest symbols should sit deepest. Start with one leaf per symbol, weighted by its frequency. Then repeat one step: take the two lightest trees, and join them under a new node. The new node weighs the sum of the two. A priority queue, from chapter 13, hands back the lightest tree each time. When one tree is left, that's the Huffman tree.

Worked Example

Building the Tree for abracadabra

Take abracadabra. Its counts are a 5, b 2, r 2, and c and d 1 each. Step one joins the two rarest, c and d, under a node of weight two. Step two joins b and r, for weight four. Now the queue holds c d at two, b r at four, and a at five. Step three takes the two lightest, c d and b r: weight six. Step four joins a with that six, for weight eleven: the root. The common letter a waited until the very end, so it sits closest to the root.

Reading Codewords

Twenty-Three Bits in Total

Now read each codeword from the root, with 0 for a left edge and 1 for a right edge. a is just 0. c is 100, and d is 101. b is 110, and r is 111. The total is five a's at one bit, plus six other letters at three bits each: 5 plus 18, or 23 bits. That's 2.09 bits per symbol, against 3 for the fixed code, and 8 for plain text.

Optimality

Why the Greedy Choice Is Safe

Most of the saving comes from a, the most common letter, which costs a single bit. Is grabbing the two lightest trees always safe? Yes. Huffman's code has the smallest total of any prefix-free code. In some best tree, the two rarest symbols are siblings at the very bottom, since moving a rarer symbol deeper never raises the total. Joining them leaves a smaller problem of the same kind, which the same rule solves. Building the tree costs order k log k, for k distinct symbols.

Quick Check

Huffman Code for mississippi

Quick check. Build the Huffman code for mississippi. The counts are i 4, s 4, p 2, and m 1. How many bits do its codewords take, in all? Pause, and decide. 21 bits. First m and p join, for weight three. That joins i, for seven. Then s joins at the root. So s gets one bit, i gets two, and m and p get three each: 4, plus 8, plus 3, plus 6. 22 is what a fixed two-bit code would spend. These counts are fairly even, so Huffman saves only one bit here.

Decoding

Walking the Tree One Bit at a Time

Encoding just joins the codewords. abracadabra becomes a stream of 23 bits. Decoding needs the tree. Start at the root, and go left on 0, right on 1. At a leaf, write its symbol, and jump back to the root. Read 0110111. The first 0 reaches a at once. Then 110 passes two inner nodes, to b. Then 111 reaches r. Decoding takes one tree step per bit, so its time is proportional to the length of the compressed stream.

Ties

Different Trees, Equal Totals

When two trees weigh the same, either can be taken first. Break the ties the other way, and abracadabra gets a different code. a is still 0. But b is 10, d is 1100, c is 1101, and r is 111. It's 23 bits again. Both codes are optimal. Now decode the first tree's bits with the second tree. Out comes a c c a a a b b c: garbage, and not even the right length. So the decoder must use exactly the encoder's tree. A compressed file has to carry it.

File Format

Storing the Tree in the Header

A simple file writes the tree first, in preorder: 0 for an inner node, and 1 plus eight bits for a leaf. With k symbols, that's 10 k minus 1 bits. Next comes the character count, in 32 bits, so the decoder knows where to stop. Then the codewords, packed eight bits to a byte. For abracadabra, that's 49 bits of tree, 32 of count, and 23 of codewords: 104 bits, or 13 bytes. Thirteen bytes is more than the 11 bytes of plain text. For a short text, the header's fixed cost swamps the saving.

Quick Check

Compressing banana

Quick check. Compress banana in this same format. a gets 0, and b and n get two bits each. How many bytes is the whole file? Pause, and decide. Nine bytes. The tree takes ten times three, minus one: 29 bits. The count takes 32. The codewords take 3 bits for the a's, 2 for b, and 4 for the n's: 9 bits. That's 70 bits, rounded up to 9 bytes. That's more than banana's six bytes of plain text. Two bytes would hold only the codewords.

Entropy

How Close Huffman Gets to the Floor

To judge a code, there's a floor that no symbol-by-symbol code can beat: the entropy. It's minus the sum of p times log base two of p. For two or more symbols, Huffman's average length is at least the entropy, and less than one bit above it. An English paragraph needs 4.18 bits per symbol, against an entropy of 4.14. Its file, header included, is about 60 percent of the plain text. Random DNA letters need exactly 2 bits, no better than a fixed two-bit code. Huffman earns its keep through skew. Text that's 90 percent a, 7 percent b and 3 percent c has entropy near 0.55 bits, but Huffman needs 1.1. Every symbol costs at least one whole bit.

Key Takeaways

Huffman Coding in Brief

To sum up. A variable-length code must be prefix-free: symbols on the leaves of a binary tree. Huffman joins the two lightest trees again and again, with a priority queue, and the result is optimal. The decoder needs the same tree, so the file stores it, and a short file can grow. Huffman gains through skew, and never spends less than one bit per symbol.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Huffman Coding: Shorter Codes for Frequent Characters

What is a prefix-free code?
A prefix-free code is a set of codewords in which no codeword is the beginning of another, so a bit stream can be read only one way. Without that property, the code a = 0, b = 1, c = 01 lets the bits 0101 mean abab, abc, cab, or cc. Placing symbols on the leaves of a binary tree, with 0 for left and 1 for right, gives a prefix-free code.
How do you build a Huffman tree?
Start with one leaf per symbol, weighted by its frequency, and repeatedly join the two lightest trees under a new node whose weight is their sum. A priority queue hands back the lightest tree each time. When one tree remains, read each codeword from root to leaf, using 0 for left and 1 for right. For abracadabra this gives a one-bit code for a and 23 bits in total.
Why must the Huffman tree be stored with the compressed data?
The decoder must use exactly the encoder's tree, because ties between equal weights can be broken in different ways, giving different but equally optimal codes. Decoding one tree's bits with the other tree produces garbage. A simple file stores the tree in preorder, a 32-bit character count, and the packed codewords, so for a short text like abracadabra the file ends up larger than plain text.
How does Huffman coding compare to entropy?
For two or more symbols, Huffman's average code length is at least the entropy and less than one bit above it. Entropy, minus the sum of p log2 p over the symbol probabilities, is the floor for any symbol-by-symbol code. Because every symbol costs at least one whole bit, skewed data can lose ground: text that is 90 percent a, 7 percent b, and 3 percent c has entropy near 0.55 bits but needs 1.1.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →