Write a program to implement Huffman coding and decoding. It should do the follo
ID: 3555686 • Letter: W
Question
Write a program to implement Huffman coding and decoding. It should do the
following:
Accept a text message, possibly of more than one line.
Create a Huffman tree for this message.
Create a code table.
Encode the message into binary.
Decode the message from binary back to text.
Hello. I have written the code for class Tree. I got errors here:
package programmingassignment4;
import java.util.*; //Stack
class Tree implements Comparable
{
private Node root; //1st Node
public Tree(char data, int frequency)
{
root = new Node();
root.iData = frequency;
root.iData = data;
}
public Tree(Tree leftChild, Tree rightChild)
{
root = new Node();
root.leftChild = leftChild.root;
root.rightChild = rightChild.root;
root.iData = leftChild.root.iData + rightChild.root.iData;
}
protected Tree(Node root)
{
this.root = root;
}
public Tree getRightTree()
{
if(root != null)
return new Tree(root.rightChild);
else
return null;
}
public char getRootChar()
{
if(root != null)
return root.dData;
else
return '';
}
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println("........................................");
while(isRowEmpty == false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j = 0; j
System.out.print(' ');
while(globalStack.isEmpty() == false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
if(temp.dData == '')
{
System.out.print("\0");
}
else if(temp.dData == ' ')
{
System.out.print("sp");
}
else if(temp.dData == ' ')
{
System.out.print("If");
}
else
{
System.out.print(" "
+ temp.dData);
}
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j = 0; j
System.out.print(' '),
}
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println("........................................");
}
@Override
public int compareTo(Tree arg0)
{
Integer freq1 = new Integer(this.root.iData);
Integer freq2 = new Integer(arg0.root.iData);
return freq1.compareTo(freq2);
}
}
I believe Comparable is missing, but I don't know where to put it and the Huffman code had more errors.
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Huffman
{
Tree tree;
TreeMap codeTable;
protected HashMap calculateFrequency(String message)
{
int messageLen = message.length();
char ch;
int count;
HashMap charCounts = new HashMap();
for(int i = 0; i < messageLen; ++i)
{
ch = message.charAt(i);
if(charCounts.containsKey(ch))
{
count = charCounts.get(ch);
++count;
charCounts.put(ch, count);
}
else
{
charCounts.put(ch,1);
}
}
return charCounts;
}
protected void createHuffmanTree(String message)
{
HashMap charCounts = calculateFrequency(message);
PriorityQueue trees = new PriorityQueue();
Tree temp;
for (Map.Entry e:
charCounts.entrySet() )
{
temp = new Tree(e.getKey(), e.getValue());
trees.add(temp);
}
while(trees.size() > 1)
{
temp = new Tree(trees.remove(),
trees.remove());
trees.add(temp);
}
tree = trees.remove();
}
public void displayHuffmanTree()
{
if (tree != null)
tree.displayTree();
else
System.out.println("Tree hasn't been created. " +
"You need to use createCodeTable first.");
}
public void createCodeTable(String message)
{
createHuffmanTree(message);
codeTable = new TreeMap();
createCodeTable(tree, "");
}
protected void createCodeTable(Tree tree, String code)
{
if (tree == null)
{
return;
}
char c = tree.getRootChar();
if(c != '')
{
codeTable.put(c, code);
}
else
{
createCodeTable(tree.getLeftTree()), code + "0");
createCodeTable(tree.getLeftTree()), code + "1");
}
}
public void displayCodeTable()
{
System.out.println("Character Code");
for(Map.Entry entry: codeTable.entrySet())
{
char key = entry.getKey();
if (key == '')
{
System.out.println("sp " + entry.getValue());
}
else if (key == '')
{
System.out.println("If " + entry.getValue());
}
else
{
System.out.println(key + " " + entry.getValue());
}
}
public String encodeMessage(String message)
{
if(codeTable == null)
{
System.out.println("No code table created.");
return "";
}
String codedMessage = "";
for (int i =0; i < message.length(); ++i)
{
char c = message.charAt(i);
codedMessage += codeTable.get(c);
}
return codedMessage;
}
public String decodeMessage(String codedMessage)
{
String decodedMessage = "";
Tree temp = tree;
for (int i = 0; i < codedMessage.length(); ++i)
{
if(codedMessage.charAt(i) == '0')
{
temp = temp.getLeftTree();
}
else
{
temp = temp.getRightTree();
}
if(temp.getRootChar() != '')
{
decodedMessage += temp.getRootChar();
temp = tree;
}
}
return decodedMessage;
}
}
This is the class Node btw:
package programmingassignment4;
class Node
{
public int iData; //holds frequency
public char dData; //holds char
public Node leftChild;
public Node rightChild;
public void displayNode() //displays itself
{
System.out.print("{");
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("}");
}
}
Could anyone please help me figure out how to resolve these errors and get my code running smoothly?
Explanation / Answer
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
import programmingassignment4.Tree;
public class Huffman
{
Tree tree;
TreeMap codeTable;
protected HashMap calculateFrequency(String message)
{
int messageLen = message.length();
char ch;
int count;
HashMap charCounts = new HashMap();
for(int i = 0; i < messageLen; ++i)
{
ch = message.charAt(i);
if(charCounts.containsKey(ch))
{
count = Integer.parseInt((String)charCounts.get(ch));
++count;
charCounts.put(ch, count);
}
else
{
charCounts.put(ch,1);
}
}
return charCounts;
}
protected void createHuffmanTree(String message)
{
HashMap charCounts = calculateFrequency(message);
PriorityQueue trees = new PriorityQueue();
Tree temp;
for (Map.Entry<K, V> e:charCounts.entrySet()) //give values of K and V
{
temp = new Tree((Tree)e.getKey(), (Tree)e.getValue());
trees.add(temp);
}
while(trees.size() > 1)
{
temp = new Tree((Tree)trees.remove(),(Tree)trees.remove());
trees.add(temp);
}
tree = (Tree) trees.remove();
}
public void displayHuffmanTree()
{
if (tree != null)
tree.displayTree();
else
System.out.println("Tree hasn't been created. " +
"You need to use createCodeTable first.");
}
public void createCodeTable(String message)
{
createHuffmanTree(message);
codeTable = new TreeMap();
createCodeTable(tree, "");
}
protected void createCodeTable(Tree tree, String code)
{
if (tree == null)
{
return;
}
char c = tree.getRootChar();
if(c != '')
{
codeTable.put(c, code);
}
else
{
createCodeTable(tree.getLeftTree()), code + "0");//implement the method
createCodeTable(tree.getLeftTree()), code + "1");//implement the method
}
}
public void displayCodeTable()
{
System.out.println("Character Code");
for(Map.Entry<K, V> entry:codeTable.entrySet())//give values of K and V
{
char key = ((String)entry.getKey()).charAt(0);
if (key == ' ')//check here if its correct
{
System.out.println("sp " + entry.getValue());
}
else if (key == ' ')//check here
{
System.out.println("If " + entry.getValue());
}
else
{
System.out.println(key + " " + entry.getValue());
}}
}
public String encodeMessage(String message)
{
if(codeTable == null)
{
System.out.println("No code table created.");
return "";
}
String codedMessage = "";
for (int i =0; i < message.length(); ++i)
{
char c = message.charAt(i);
codedMessage += codeTable.get(c);
}
return codedMessage;
}
public String decodeMessage(String codedMessage)
{
String decodedMessage = "";
Tree temp = tree;
for (int i = 0; i < codedMessage.length(); ++i)
{
if(codedMessage.charAt(i) == '0')
{
temp = temp.getLeftTree();//implement
}
else
{
temp = temp.getRightTree();
}
if(temp.getRootChar() != '')
{
decodedMessage += temp.getRootChar();
temp = tree;
}
}
return decodedMessage;
}
}
---------------------------------------------------------------------------------------------------------------------
package programmingassignment4;
public class Node
{
public int iData; //holds frequency
public char dData; //holds char
public Node leftChild;
public Node rightChild;
public void displayNode() //displays itself
{
System.out.print("{");
System.out.print(iData);
System.out.print(", ");
System.out.print(dData);
System.out.print("}");
}
}
----------------------------------------------------------------------------------------------------------------------------------
package programmingassignment4;
import java.util.*; //Stack
public class Tree implements Comparable
{
private Node root; //1st Node
public Tree(char data, int frequency)
{
root = new Node();
root.iData = frequency;
root.iData = data;
}
public Tree(Tree leftChild, Tree rightChild)
{
root = new Node();
root.leftChild = leftChild.root;
root.rightChild = rightChild.root;
root.iData = leftChild.root.iData + rightChild.root.iData;
}
protected Tree(Node root)
{
this.root = root;
}
public Tree getRightTree()
{
if(root != null)
return new Tree(root.rightChild);
else
return null;
}
public char getRootChar()
{
if(root != null)
return root.dData;
else
return '';
}
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println("........................................");
while(isRowEmpty == false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j = 0; j<32;j++)//check if this loop is correct or not
System.out.print(' ');
while(globalStack.isEmpty() == false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
if(temp.dData == '')
{
System.out.print("\0");
}
else if(temp.dData == ' ')
{
System.out.print("sp");
}
else if(temp.dData == ' ')
{
System.out.print("If");
}
else
{
System.out.print(" "
+ temp.dData);
}
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j = 0; j<32;j++)//check if this loop is correct or not
System.out.print(' ');
}
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push(localStack.pop());
}
System.out.println("........................................");
}
public int compareTo(Tree arg0)
{
Integer freq1 = new Integer(this.root.iData);
Integer freq2 = new Integer(arg0.root.iData);
return freq1.compareTo(freq2);
}
@Override
public int compareTo(Object arg0) {
// TODO Auto-generated method stub
return 0;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.