Be able to calculate the number of bits required to store a piece of data…

The idea

Huffman coding gives frequent characters short codes and rare characters long codes, so the stored size is the sum of each character's code length multiplied by how many times it occurs. To find the total bits, take the Huffman tree, read each character's code length (the number of edges from the root to that leaf), then for every character multiply its frequency by its code length and add the products. For example, if 'A' appears 5 times with a 1-bit code and 'B' appears 3 times with a 3-bit code, those contribute 5×1 = 5 bits and 3×3 = 9 bits. Add all contributions to get the compressed total. Do not count the tree itself unless told to; the question asks for the bits storing the encoded data.

What earns the marks

• Identify each character's code length from the Huffman tree as the number of edges from root to leaf.
• Multiply each character's frequency by its code length.
• Sum all the products to obtain the total number of bits for the compressed data.
• Recognise that more frequent characters have shorter codes, so the total is less than a fixed-length encoding of the same data.

Common mistakes and how to put them right

• Adding the code lengths instead of multiplying each by its frequency.

  Put it right: Weight every code length by how often that character occurs.

• Counting the number of distinct characters rather than total occurrences.

  Put it right: Use each character's frequency across the whole message.

• Including the storage of the Huffman tree in the data total when the question asks only for the encoded data.

  Put it right: Read the question carefully and total only the encoded bits requested.

Exam tips

• Write out a small table of character, frequency and code length before multiplying, so no term is missed.
• Check that the total is smaller than the fixed-length alternative; a larger answer signals a slip.
• Re-read whether the question wants total bits or bits saved, since the two need different final steps.