fork download
copy 
  1. import java.util.Comparator;
  2. import java.util.HashMap;
  3. import java.util.Map;
  4. import java.util.PriorityQueue;
  5.  
  6. // A Tree node
  7. class Node
  8. {
  9.     char ch;
  10.     int freq;
  11.     Node left = null, right = null;
  12.  
  13.     Node(char ch, int freq)
  14.     {
  15.         this.ch = ch;
  16.         this.freq = freq;
  17.     }
  18.  
  19.     public Node(char ch, int freq, Node left, Node right) {
  20.         this.ch = ch;
  21.         this.freq = freq;
  22.         this.left = left;
  23.         this.right = right;
  24.     }
  25. };
  26.  
  27. class Huffman
  28. {
  29.     // traverse the Huffman Tree and store Huffman Codes
  30.     // in a map.
  31.     public static void encode(Node root, String str,
  32.                               Map<Character, String> huffmanCode)
  33.     {
  34.         if (root == null)
  35.             return;
  36.  
  37.         // found a leaf node
  38.         if (root.left == null && root.right == null) {
  39.             huffmanCode.put(root.ch, str);
  40.         }
  41.  
  42.  
  43.         encode(root.left, str + "0", huffmanCode);
  44.         encode(root.right, str + "1", huffmanCode);
  45.     }
  46.  
  47.     // traverse the Huffman Tree and decode the encoded string
  48.     public static int decode(Node root, int index, StringBuilder sb)
  49.     {
  50.         if (root == null)
  51.             return index;
  52.  
  53.         // found a leaf node
  54.         if (root.left == null && root.right == null)
  55.         {
  56.             System.out.print(root.ch);
  57.             return index;
  58.         }
  59.  
  60.         index++;
  61.  
  62.         if (sb.charAt(index) == '0')
  63.             index = decode(root.left, index, sb);
  64.         else
  65.             index = decode(root.right, index, sb);
  66.  
  67.         return index;
  68.     }
  69.  
  70.     // Builds Huffman Tree and huffmanCode and decode given input text
  71.     public static void buildHuffmanTree(String text)
  72.     {
  73.         // count frequency of appearance of each character
  74.         // and store it in a map
  75.         Map<Character, Integer> freq = new HashMap<>();
  76.         for (int i = 0 ; i < text.length(); i++) {
  77.             if (!freq.containsKey(text.charAt(i))) {
  78.                 freq.put(text.charAt(i), 0);
  79.             }
  80.             freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
  81.         }
  82.  
  83.         // Create a priority queue to store live nodes of Huffman tree
  84.         // Notice that highest priority item has lowest frequency
  85.         PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
  86.             @Override
  87.             public int compare(Node l, Node r) {
  88.                 return l.freq - r.freq;
  89.             }
  90.         });
  91.  
  92.         // Create a leaf node for each character and add it
  93.         // to the priority queue.
  94.         for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
  95.             pq.add(new Node(entry.getKey(), entry.getValue()));
  96.         }
  97.  
  98.         // do till there is more than one node in the queue
  99.         while (pq.size() != 1)
  100.         {
  101.             // Remove the two nodes of highest priority
  102.             // (lowest frequency) from the queue
  103.             Node left = pq.poll();
  104.             Node right = pq.poll();
  105.  
  106.             // Create a new internal node with these two nodes as children
  107.             // and with frequency equal to the sum of the two nodes
  108.             // frequencies. Add the new node to the priority queue.
  109.             int sum = left.freq + right.freq;
  110.             pq.add(new Node('\0', sum, left, right));
  111.         }
  112.  
  113.         // root stores pointer to root of Huffman Tree
  114.         Node root = pq.peek();
  115.  
  116.         // traverse the Huffman tree and store the Huffman codes in a map
  117.         Map<Character, String> huffmanCode = new HashMap<>();
  118.         encode(root, "", huffmanCode);
  119.  
  120.         // print the Huffman codes
  121.         System.out.println("Huffman Codes are :\n");
  122.         for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
  123.             System.out.println(entry.getKey() + " " + entry.getValue());
  124.         }
  125.  
  126.         System.out.println("\nOriginal string was :\n" + text);
  127.  
  128.         // print encoded string
  129.         StringBuilder sb = new StringBuilder();
  130.         for (int i = 0 ; i < text.length(); i++) {
  131.             sb.append(huffmanCode.get(text.charAt(i)));
  132.         }
  133.  
  134.         System.out.println("\nEncoded string is :\n" + sb);
  135.  
  136.         // traverse the Huffman Tree again and this time
  137.         // decode the encoded string
  138.         int index = -1;
  139.         System.out.println("\nDecoded string is: \n");
  140.         while (index < sb.length() - 2) {
  141.             index = decode(root, index, sb);
  142.         }
  143.     }
  144.  
  145.     public static void main(String[] args)
  146.     {
  147.         String text = "Huffman coding is a data compression algorithm.";
  148.  
  149.         buildHuffmanTree(text);
  150.     }
  151. }
Success #stdin #stdout 0.1s 27776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Huffman Codes are :

  100
a 010
c 0011
d 11001
e 110000
f 0000
g 0001
H 110001
h 110100
i 1111
l 101010
m 0110
n 0111
. 10100
o 1110
p 110101
r 0010
s 1011
t 11011
u 101011

Original string was :
Huffman coding is a data compression algorithm.

Encoded string is :
11000110101100000000011001001111000011111011001111101110001100111110111000101001100101011011010100001111100110110101001011000010111011111111100111100010101010000111100010111111011110100011010100

Decoded string is: 

Huffman coding is a data compression algorithm.
https://ideone.com/cfJNeU
Huffman coding data compression algorithm
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!