0
16kviews
Explain Huffman algorithm with an example
1 Answer
1
895views
  • Huffman algorithm or Huffman coding is an entropy encoding algorithm.
  • It is used widely for data compression (like Winzip Compression-Winzip doesn’t use it but!)
  • Huffman coding is used in JPEG compression.
  • The key idea behind Huffman coding is to encode the most common characters using shorter strings of bits than those used for less common source characters.
  • It works by creating a binary tree stored in an array.
  • We also need to know the external path length (sum of all paths from root to external node) and internal path length (sum of all paths from root to internal node).
  • The Huffman Algorithm
  • Step 1: Create a leaf node for each character. Add the character and its weight or frequency of occurrence to the priority queue.
  • Step 2: Repeat Steps 3 to 5 while the total number of nodes in the queue is greater than 1
  • Step 3: Remove two nodes that have the lowest weight (or highest priority)
  • Step 4: Create a new internal node by merging these two nodes as children and with weight equal to the sum of the two nodes' weights.
  • Step 5: Add the newly created node to the queue.

enter image description here

enter image description here

So coding for C=00, D=01, A=100, B=101, C=11

Please log in to add an answer.