huffman coding

Concept

Huffman coding

• lossless compression
• high frequency symbols are given the shortest length code
• prefix code, symbols can have different length codes
• need to provide dictionary (overhead)
• used in:
  • PNG
  • JPEG (end)

Algorithm

1. sort the symbols by frequency
2. join the two smallest groups together, add the total frequency
   • a group is either:
     • a symbol
     • a pair of groups
3. repeat step 2 until there is only one group encompassing all the symbols
4. form the huffman tree
5. form the dictionary
   

abaabc

• frequency table

• huffman tree

huffman trees defer from prefix trees since only the leaf nodes

• dictionary

the code is a prefix code, so no prefix of any code is another code that encodes a symbol

  abaabc -> 0 10 0 0 10 11
6×8 bits    9 bits + dict

Application

Encoding text (short)

this is an example for huffman encoding

Encoding text (long)

data compression is the process of encoding information using fewer bits than the original representation compression can be either lossy or lossless