126. Introducing the Huffman Coding data structure

The Huffman Coding algorithm was developed by David A. Huffman in 1950 and can easily be understood via an example. Let’s assume that we have the string shown in the following figure.

Figure 5.41: Initial string

Let’s assume that each character needs 8 bits to be represented. Since we have 14 characters, we can say that we need 8*14=112 bits to send this string over a network.

Encoding the string

The idea of Huffman Coding is to compress (shrink) such strings to a smaller size. For this, we create a tree of character frequencies. A Node of this tree can be shaped as follows:

public class Huffman {
  private Node root;
  private String str;
  private StringBuilder encodedStr;
  private StringBuilder decodedStr;
  private final class Node {
    private Node left;
    private Node right;
    private final Character character;
    private final Integer frequency;
    //  constructors
  }
  ...
}...