What is Huffman Coding?

• Compress file by creating min-heap
  • Considers character frequency of input file
• used in; compressing files in UNIX, as subroutine of compressing JPEG | MP3 files

Fixed Length Code vs Prefix Code

• Fixed Length Code
  • ASCII Code
  • 8 bit length necessary
    • Limitation in application of space
      • Variable Length Code presented as solution
• Prefix Code
  • One of many Variable Length Codes
  • Binary code given to each characters can't be prefix of any other codes
    • If not, can cause error in decoding
  • Used in Huffman Coding

Application

Encoding Algorithm

1. Scan target file and calculate frequency of each characters

2. Compose Min-Heap with frequency as priority

   

3. Remove two nodes that have least frequency

4. Insert empty node with two removed nodes as child node

   

5. Repeat 3 - 4 until a node is left

6. Set left node as root node

   

• Give high frequency character with short binary code to increase efficiency
  • Low frequency character with longer binary code

Decoding Alogorithm

• Main consideration
  • No delimiter
    • ex) 01001110 instead of 01#001#110
    • Where to cut bit string
• Solution
  • Is encoded into Min-Heap
    • Binary tree structure
  • Visit right node when 1, visit left node when 0
    • until leaf node
  • When leaf node reached
    • convert to character
• Time complexity
  • Best case: O(logN)
  • Worst case: O(N)
  • Depends on tree height

Application to Deep Learning