Extract from INT 4097 Module Handbook p37

Part of the compression of JPEG involves a technique called "Huffman Encoding" This technique works by calculating the frequency of particular characters in a piece of text and allocating short codes to those characters which occur most frequently.
The algorithm is as follows:

1. For each character in the text, calculate how frequently it occurs by counting up the number of times is occurs and dividing that number by the total number of characters in the text.

2. Create a league table, ranked with the highest occurring character at the top and the lowest occurring character at the bottom.

3. Take the bottom two items from the table and combine them, recreating a new version of the league table containing the new combined entry ranked with the sum of the frequencies of its individual components.

4. Repeat step 3 until the table consists of only one item 5. Unpack the final item as a binary tree, starting with the outer bracket. Label every right branch "1" and every left branch "O".

The code for a particular character can now be found by starting at the root and tracing the branches to the desired character.