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