Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks

Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-legth codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.
The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character. This is how Huffman Coding makes sure that there is no ambiguity when decoding the generated bit stream.
Applications

Huffman coding today is often used as a "back-end" to some other compression methods. DEFLATE (PKZIP's algorithm) and multimedia codecs such as JPEG and MP3 have a front-end model and quantization followed by Huffman coding (or variable-length prefix-free codes with a similar structure, although perhaps not necessarily designed by using Huffman's algorithm[clarification needed]).

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete

Steps to print codes from Huffman Tree:

Traverse the tree formed starting from the root. Maintain an auxiliary array. While moving to the left child, write 0 to the array. While moving to the right child, write 1 to the array. Print the array when a leaf node is encountered.

EPI Java Solution:

Implement Huffman coding

Huffman_encoding.cpp HuffmanEncoding.java

  public static void huffmanEncoding(List<Ref<Symbol>> symbols) {
    // Initially assigns each symbol into min->heap.
    PriorityQueue<BinaryTree> minHeap = new PriorityQueue<>();
    for (Ref<Symbol> s : symbols) {
      minHeap.add(new BinaryTree(s.value.prob, s, null, null));
    }

    // Keeps combining two nodes until there is one node left.
    while (minHeap.size() > 1) {
      BinaryTree l = minHeap.remove();
      BinaryTree r = minHeap.remove();
      minHeap.add(new BinaryTree(l.prob + r.prob, null, l, r));
    }

    // Traverses the binary tree and assign code.
    assignHuffmanCode(minHeap.peek(), "");
  }

  // Traverses tree and assign code.
  private static void assignHuffmanCode(BinaryTree r, String s) {
    if (r != null) {
      // This node (i.e.,leaf) contains symbol.
      if (r.s != null) {
        r.s.value.code = s;
      } else { // Non-leaf node.
        assignHuffmanCode(r.left, s + "0");
        assignHuffmanCode(r.right, s + "1");
      }
    }
  }
  
   public static class Symbol {
    public char c;
    public double prob;
    public String code;

    public String toString() {
      return c + " " + prob + " " + code;
    }
  }
  public static class BinaryTree implements Comparable<BinaryTree> {
    public double prob;
    public Ref<Symbol> s;
    public BinaryTree left, right;

    public BinaryTree(double prob, Ref<Symbol> s, BinaryTree left,
                      BinaryTree right) {
      this.prob = prob;
      this.s = s;
      this.left = left;
      this.right = right;
    }
    public int compareTo(BinaryTree o) {
      return Double.compare(o.prob, prob);
    }

  }

Java Implementation from http://rosettacode.org/wiki/Huffman_coding#Java

HuffmanTree: HuffmanLeaf, HuffmanNode

abstract class HuffmanTree implements Comparable<HuffmanTree> {
    public final int frequency; // the frequency of this tree
    public HuffmanTree(int freq) { frequency = freq; }
    // compares on the frequency
    public int compareTo(HuffmanTree tree) {
        return frequency - tree.frequency;
    }
}
class HuffmanLeaf extends HuffmanTree {
    public final char value; // the character this leaf represents
    public HuffmanLeaf(int freq, char val) {
        super(freq);
        value = val;
    }
}
class HuffmanNode extends HuffmanTree {
    public final HuffmanTree left, right; // subtrees
    public HuffmanNode(HuffmanTree l, HuffmanTree r) {
        super(l.frequency + r.frequency);
        left = l;
        right = r;
    }
}
public class HuffmanCode {
    // input is an array of frequencies, indexed by character code
    public static HuffmanTree buildTree(int[] charFreqs) {
        PriorityQueue<HuffmanTree> trees = new PriorityQueue<HuffmanTree>();
        // initially, we have a forest of leaves
        // one for each non-empty character
        for (int i = 0; i < charFreqs.length; i++)
            if (charFreqs[i] > 0)
                trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
        assert trees.size() > 0;
        // loop until there is only one tree left
        while (trees.size() > 1) {
            // two trees with least frequency
            HuffmanTree a = trees.poll(); // case: when there is only one node.
            HuffmanTree b = trees.poll();
            // put into new node and re-insert into queue
            trees.offer(new HuffmanNode(a, b));
        }
        return trees.poll();
    }
 
    public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
        assert tree != null;
        if (tree instanceof HuffmanLeaf) {
            HuffmanLeaf leaf = (HuffmanLeaf)tree;
            // print out character, frequency, and code for this leaf (which is just the prefix)
            System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);
        } else if (tree instanceof HuffmanNode) {
            HuffmanNode node = (HuffmanNode)tree;
            // traverse left
            prefix.append('0');
            printCodes(node.left, prefix);
            prefix.deleteCharAt(prefix.length()-1);
 
            // traverse right
            prefix.append('1');
            printCodes(node.right, prefix);
            prefix.deleteCharAt(prefix.length()-1);
        }
    }

http://algs4.cs.princeton.edu/55compression/Huffman.java.html

    private static final int R = 256;
    // Huffman trie node
    private static class Node implements Comparable<Node> {
        private final char ch;
        private final int freq;
        private final Node left, right;

        Node(char ch, int freq, Node left, Node right) {
            this.ch    = ch;
            this.freq  = freq;
            this.left  = left;
            this.right = right;
        }

        // is the node a leaf node?
        private boolean isLeaf() {
            assert ((left == null) && (right == null)) || ((left != null) && (right != null));
            return (left == null) && (right == null);
        }

        // compare, based on frequency
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

    // build the Huffman trie given frequencies
    private static Node buildTrie(int[] freq) {

        // initialze priority queue with singleton trees
        MinPQ<Node> pq = new MinPQ<Node>();
        for (char i = 0; i < R; i++)
            if (freq[i] > 0)
                pq.insert(new Node(i, freq[i], null, null));

        // special case in case there is only one character with a nonzero frequency
        if (pq.size() == 1) {
            if (freq['\0'] == 0) pq.insert(new Node('\0', 0, null, null));
            else                 pq.insert(new Node('\1', 0, null, null));
        }

        // merge two smallest trees
        while (pq.size() > 1) {
            Node left  = pq.delMin();
            Node right = pq.delMin();
            Node parent = new Node('\0', left.freq + right.freq, left, right);
            pq.insert(parent);
        }
        return pq.delMin();
    }

Also read http://nayuki.eigenstate.org/page/huffman-coding-java
Read full article from Greedy Algorithms | Set 3 (Huffman Coding) | GeeksforGeeks