Simple Huffman Coding algorithm in Java
Algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
package com.omt.learn.algo.util.huffman; public class HuffmanNode implements Comparable<HuffmanNode> { public int frequency = 0; public char c;// Default Value is u0000 public boolean isInternalNode = false; public HuffmanNode left = null; public HuffmanNode right = null; @Override public int compareTo(HuffmanNode o) { return this.frequency - o.frequency; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
package com.omt.learn.geekforgeek.greedy; import java.util.PriorityQueue; import com.omt.learn.algo.util.huffman.HuffmanNode; public class HuffmanCodingOne { public static void main(String... args) { char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; printHuffmanCodes(charArray, charfreq); } private static void printHuffmanCodes(char[] c, int[] f) { PriorityQueue<HuffmanNode> huffmanNodes = new PriorityQueue<HuffmanNode>(); int i = 0; for (char ch : c) { HuffmanNode huffmanNode = new HuffmanNode(); huffmanNode.c = ch; huffmanNode.frequency = f[i++]; huffmanNodes.add(huffmanNode); } // Create Huffman Tree while (huffmanNodes.size() > 1) { HuffmanNode huffmanNode = new HuffmanNode(); huffmanNode.isInternalNode = true; huffmanNode.left = huffmanNodes.poll(); huffmanNode.frequency = huffmanNode.left.frequency; huffmanNode.right = huffmanNodes.poll(); huffmanNode.frequency += huffmanNode.right.frequency; huffmanNodes.add(huffmanNode); } // Print code for each char printCharAndCode(huffmanNodes.poll(), ""); } private static void printCharAndCode(HuffmanNode root, String code) { if (root == null) { return; } else if (!root.isInternalNode) { System.out.println(root.c + ":" + code); return; } printCharAndCode(root.left, code + "0"); printCharAndCode(root.right, code + "1"); } } |
Output :
|
1 2 3 4 5 6 |
f:0 c:100 d:101 a:1100 b:1101 e:111 |