Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Huffman code, Huffman Tree, Huffman encoading
package com.tutorial.protobuf;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Huffman {
public static void main (String [] arguments){
String input = "hello";
//Step 1: Find the count of the characters in the input string
int[] countOfCharacters = getCountOfCharacters(input);
//Step 2: Build Huffman Tree using the count of characters
TreeNode huffmanTree = getHuffmanTree(countOfCharacters, input);
//Step 3: Build Huffman Code using the Huffman Tree
Map<String, String> huffmanCode = new HashMap<>();
getHuffmanCode(huffmanCode, huffmanTree, "", true);
//Step 4: Encode the String using Huffman code
String encodedString = getEncodedString(huffmanCode, input);
System.out.println("Encoded String is "+encodedString);
}
private static String getEncodedString(Map<String, String> huffmanCode, String input) {
char [] inputCharArray = input.toCharArray();
StringBuffer encoadedString = new StringBuffer();
for(int i = 0; i < inputCharArray.length; i++){
encoadedString.append(huffmanCode.get(String.valueOf(inputCharArray[i])));
}
return encoadedString.toString();
}
private static void getHuffmanCode(Map<String, String> huffmanCode, TreeNode huffmanTree, String bit, Boolean isLeft) {
if(huffmanTree == null)
return;
if(huffmanTree.isLeaf()){
if(isLeft) {
if(bit.isEmpty())
bit = "0";
else
bit.concat("0");
}
else
bit.concat("1");
huffmanCode.put(String.valueOf(huffmanTree.character), bit);
}
getHuffmanCode(huffmanCode,huffmanTree.leftLeaf, bit.concat("0"), true);
getHuffmanCode(huffmanCode,huffmanTree.rightLeaf, bit.concat("1"), false);
}
private static TreeNode getHuffmanTree(int[] countOfCharacters, String input) {
//This priority queue will store tree nodes with lowest frequency character first
PriorityQueue<TreeNode> priorityQueue = new PriorityQueue<>();
int length = countOfCharacters.length;
int inputLength = input.length();
int uniqueChaCount = 0;
for(int i = 0; i < length; i++){
int ascii = i;
int count = countOfCharacters[ascii];
double frequency = (double) count/inputLength;
if(frequency > 0D) {
TreeNode treeNode = new TreeNode((char) i, frequency);
priorityQueue.add(treeNode);
uniqueChaCount = uniqueChaCount + 1;
}
}
TreeNode huffmanTree = null;
while(priorityQueue.size() > 1){
TreeNode leftLeaf = priorityQueue.poll();
TreeNode rightLeaf = priorityQueue.poll();
TreeNode root = new TreeNode(leftLeaf.frequency + rightLeaf.frequency, leftLeaf, rightLeaf);
priorityQueue.add(root);
}
return priorityQueue.peek();
}
private static int[] getCountOfCharacters(String input) {
//256 is total number of ascii characters
int [] countOfCharacters = new int [256];
char [] inputCharArray = input.toCharArray();
int length = inputCharArray.length;
for(int i = 0; i < length ; i++){
//Type casting char in integer gives the ascii of the character
int ascii = (int)inputCharArray[i];
//Increase the count of the character encountered
countOfCharacters[ascii] = countOfCharacters[ascii] + 1;
}
return countOfCharacters;
}
/**
* This class will help to build huffman tree based
* on priority queue
*/
private static class TreeNode implements Comparable<TreeNode>{
char character;
double frequency;
TreeNode leftLeaf;
TreeNode rightLeaf;
public TreeNode() {
}
public TreeNode(char character, double frequency) {
this.character = character;
this.frequency = frequency;
}
public TreeNode(double frequency, TreeNode leftLeaf, TreeNode rightLeaf) {
this.frequency = frequency;
this.leftLeaf = leftLeaf;
this.rightLeaf = rightLeaf;
}
public boolean isLeaf(){
if(leftLeaf == null && rightLeaf == null)
return true;
return false;
}
@Override
public int compareTo(TreeNode o) {
if(this.frequency > o.frequency)
return 1;
return -1;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.