Huffman codes are a type of [[prefix code]] used in compression. They use a [[greedy algorithm]] and can be shown to be optimal. To generate a Huffman code 1. combine the two least frequent characters into a subtree; record the frequency for the subtree as the sum of the two character's frequencies 2. select the two characters or subtrees with lowest frequency into a subtree 3. repeat step 2 until the list of characters are exhausted Note that you are greedily building up a prefix tree where the composite character you create in step 1 and step 2 may be considered in each iteration. Huffman codes must be [[mutually exclusive and collectively exhaustive]].