Write code in JAVA Huffman Coding Objective: Implement the Huffman Coding algori
ID: 3692430 • Letter: W
Question
Write code in JAVA
Huffman Coding
Objective:
Implement the Huffman Coding algorithm, analyze a text file, and print out the codes for each letter. Huffman coding is used as a way to encode data in such a way that the symbols that appear more frequently have a smaller code representation vs. ones that appear more infrequently. This is generally done by constructing a binary tree, where each link has a value 0 or 1. For more information check here:
http://en.wikipedia.org/wiki/Huffman_coding
Demonstrate the algorithm works by printing out the frequency of each letter along with its code
Explanation / Answer
MakeCode.java
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileInputStream;
public class MakeCode {
public static void main(String[] args){
String content = null;
try {
//--------------------test----------------------------
File huffmanFile = new File("C:\Users\Administrator\temp\Huffman.txt");
String encodString = "GBK";
if (huffmanFile.isFile()&&huffmanFile.exists()) {
InputStreamReader reader = new InputStreamReader(new FileInputStream(huffmanFile),encodString);
BufferedReader bufferedReader = new BufferedReader(reader);
while ((content = bufferedReader.readLine())!=null) {
System.out.println(content);
//encode
HuffmanEncode huffmanEncode = new HuffmanEncode(content);
huffmanEncode.Encoding();
//decode
HuffmanDecode huffmanDecode = new HuffmanDecode(huffmanEncode.getOutputString(),huffmanEncode.getRootNode());
huffmanDecode.decoding();
}
}
//--------------------test----------------------------
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
}
}
HuffmanDecode.java
public class HuffmanDecode {
private String huffmanString = "";
private String originalString = "";
private Node root;
public String getHuffmanString() {
return huffmanString;
}
public void setHuffmanString(String huffmanString) {
this.huffmanString = huffmanString;
}
public HuffmanDecode(String string,Node root){
this.huffmanString = string;
this.root = root;
}
public void decoding(){
Node currentNode = this.root;
for (int i = 0; i < this.huffmanString.length(); i++) {
char c = this.huffmanString.charAt(i);
//find the leaf
if (c == '0') {
currentNode = currentNode.left;
}else {
currentNode = currentNode.right;
}
//decoding if currentNode is not leaf we will continue loop
if(currentNode.left != null && currentNode.right != null) {
continue;
}else {
this.originalString += currentNode.name;
currentNode = this.root;
}
}
this.printOriginalString();
}
private void printOriginalString(){
System.out.println("This original string is :");
System.out.println(this.originalString);
}
}
HuffmanEncode.java
package huffmancode;
//import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
//import java.util.PriorityQueue;
//import java.util.Queue;
public class HuffmanEncode {
//---------------------------test-------------------------------
private huffmancode.PriorityQueue<Node> priorityQueue;
//---------------------------test-------------------------------
private String inputString = "";
private String outputString = "";
private Map<Character, String> mapTable;
private Node rootNode;
public Node getRootNode() {
return rootNode;
}
public void setRootNode(Node rootNode) {
this.rootNode = rootNode;
}
public String getOutputString() {
return outputString;
}
public void setOutputString(String outputString) {
this.outputString = outputString;
}
public String getInputString() {
return inputString;
}
public void setInputString(String inputString) {
this.inputString = inputString;
}
/**
* This constructor is to compute the frequency of each character and initialize the priorityQueue
* @param inputString -input string
*/
public HuffmanEncode(String string){
this.inputString = string;
HashMap<Character, Integer> strhashMap = new HashMap<Character, Integer>();
int num = 0;
int count = 0;
//pick up a char to compute its frequency
for (int i = 0; i < string.length(); i++) {
char c = string.charAt(i);
int temp = 0;
for (int j = 0; j < string.length(); j++) {
num = string.indexOf(c,temp);
if (num!=-1) {
count++;
temp = num +1;
continue;
}else {
strhashMap.put(c,count);
count = 0;
break;
}
}
}
Iterator<Character> iteratorKey = strhashMap.keySet().iterator();
Iterator<Integer> iteratorValue = strhashMap.values().iterator();
//initliaze the priorityQueue
// priorityQueue = new PriorityQueue<Node>(strhashMap.size(),orderComparator);
//---------------------------test-------------------------------
priorityQueue = new huffmancode.PriorityQueue<Node>();
//---------------------------test-------------------------------
while (iteratorKey.hasNext()) {
Node charOfInput = new Node();
charOfInput.name = iteratorKey.next();
charOfInput.frequency = iteratorValue.next();
priorityQueue.offer(charOfInput);
}
}
/**
* This method is to encode the inputstring and construct Huffman tree
*/
public void Encoding(){
System.out.println("size is "+priorityQueue.size());
//construct the Huffman tree
while (priorityQueue.size()>1) {
Node node = new Node();
Node x = new Node();
Node y = new Node();
node.left = x = priorityQueue.poll();
node.right = y = priorityQueue.poll();
node.frequency = x.frequency+y.frequency;
priorityQueue.offer(node);
}
//process the Huffman tree
HuffmanTree huffmanTree = new HuffmanTree();
rootNode = priorityQueue.poll();
huffmanTree.setRoot(rootNode);
huffmanTree.setBinaryTreeArray(rootNode);
huffmanTree.printTree(rootNode);
huffmanTree.write();
//to output the encoding string
mapTable = huffmanTree.getNodeTable().getNodeTable();
for (int i = 0; i < this.inputString.length(); i++) {
char c = inputString.charAt(i);
String binaryString = mapTable.get(c);
this.outputString += binaryString;
}
System.out.println("This input encode string is :");
System.out.println(this.outputString);
}
}
HuffmanTree.java
package huffmancode;
public class HuffmanTree {
private Node root;
private String output = "";
private NodeTable nodeTable = new NodeTable();
public NodeTable getNodeTable() {
return nodeTable;
}
public void setNodeTable(NodeTable nodeTable) {
this.nodeTable = nodeTable;
}
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
/**
* This method is to print the node from the root element
*/
public void printTree(Node node){
if (node.left != null && node.right != null) {
printTree(node.left);
printTree(node.right);
}else {
nodeTable.put(node.name, node.binary);
output += node.name +" = "+ node.binary + " , ";
}
}
/**
* This method is to setBinary of Huffman tree
* @param node huffman node
*/
public void setBinaryTreeArray(Node node){
if (node.left != null) {
Node nodeLeft = node.left;
nodeLeft.binaryDigit(node.binary+"0");
setBinaryTreeArray(nodeLeft);
}
if (node.right != null) {
Node nodeRight = node.right;
nodeRight.binaryDigit(node.binary+"1");
setBinaryTreeArray(nodeRight);
}
}
/**
* This method is output the encoding result
*/
public void write(){
System.out.println("The Huffman tree is ");
System.out.println(output);
}
}
Node.java
public class Node {
public int frequency;
public char name;
public Node left;
public Node right;
public String binary = "";
/**
* update the binary
* @param binary
*/
public void binaryDigit(String binary) {
this.binary += binary;
}
}
NodeTable.java
import java.util.HashMap;
import java.util.Map;
public class NodeTable {
private Map<Character, String> nodeTable = new HashMap<Character, String>();
public Map<Character, String> getNodeTable() {
return nodeTable;
}
public void setNodeTable(Map<Character, String> nodeTable) {
this.nodeTable = nodeTable;
}
public void put(Character character,String string){
this.nodeTable.put(character, string);
}
}
PriorityQueue.java
import java.util.ArrayList;
import java.util.List;
public class PriorityQueue<T>{
private List<Node> list;
// private int heapSize;
public PriorityQueue(){
this.list = new ArrayList<Node>();
//we do not want to use the first place
Node placeHolder = new Node();
this.list.add(placeHolder);
}
/**
* This method is to build min-heap
* @param list store the node
*/
private void buildMinHeap(List<Node> list){
// this.heapSize = this.list.size();
for (int i = (int)(Math.floor(list.size()/2)); i>=1; i--) {
this.minHeapify(list, i);
}
}
/**
* This method is to maintain the min-heap property
* @param list store the node
* @param i the index of node which violate the min-heap property
*/
private void minHeapify(List<Node> list,int i){
int smallest = 0;
int l = left(i);
int r = right(i);
//find the minimum element
if (l<= this.list.size()-1 && this.list.get(l).frequency<this.list.get(i).frequency) {
smallest = l;
}else {
smallest = i;
}
if (r<=this.list.size()-1 && this.list.get(r).frequency<this.list.get(smallest).frequency) {
smallest = r;
}
//exchange the i and smallest
if (smallest != i) {
Node temp = new Node();
temp = this.list.get(i);
this.list.set(i, this.list.get(smallest));
this.list.set(smallest, temp);
this.minHeapify(list, smallest);
}
}
// private int parent(int i){
// return (int)(Math.floor(i));
// }
private int left(int i){
return 2*i;
}
private int right(int i){
return 2*i+1;
}
/**
* This method is to get the minimum node in the priorityQueue
* @return the minimum node
*/
public Node poll(){
Node minNode = new Node();
if (list.size()<=1) {
System.out.println("The priority is empty!");
return minNode;
}
minNode = this.list.get(1);
this.list.set(1, this.list.get(this.list.size()-1));
this.list.remove(this.list.size()-1);
this.minHeapify(this.list, 1);
return minNode;
}
/**
* This method is to add a node into priorityQueue
* @param node -the node you want to add in
* @return -true if success -false not success
*/
public boolean offer(Node node){
this.list.add(node);
this.buildMinHeap(this.list);
return true;
}
public int size(){
return this.list.size()-1;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.