Compression Huffman Coding Aqa

Huffman Coding

What is Huffman coding?

• Huffman coding is a method of lossless compression primarily used on text based data (documents)

• A Huffman coding tree is used to compress the data whilst keeping all the data so that it can be uncompressed back to its original state

Example (step 1)

• A text file contains the following characters

• The text file contain 16 characters including spaces

• A frequency analysis shows there is some repetition in the characters, for example there are 2 x E’s

Huffman Trees

What is a Huffman tree?

• A Huffman tree is a type of binary tree used in Huffman coding to achieve lossless compression of text data

• Each character is represented as a leaf in the tree

• Internal nodes always have two children, while leaves have none

• The tree is built based on the frequency of characters in the text, so that more frequent characters are given shorter codes

• Binary trees are covered in much more detail at A-Level 

Example (step 2)

• List the frequency of each character and order them from least to most frequent:

• Combine the two least frequent characters (I + L = 2) into a new node, then reorder:

• Update the frequency data to show the combined characters

• Repeat until all characters are combined into a single tree

• Assigning bit patterns

  • Follow each branch of the tree, writing 0 on left branches and 1 on right branches

  • Each character ends up with a unique binary code

• More frequent characters get shorter codes