I have almost done with this code to Implement Huffman Coding. However I have an
ID: 3696128 • Letter: I
Question
I have almost done with this code to Implement Huffman Coding. However I have an error at the "Heap<Tree>". Could anyone help with solving this issue, really appreciated. Thank you!!
import java.util.Scanner;
public class HuffmanEncoding {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.print("Enter a text: ");
String text = input.nextLine();
int[] counts = getCharacterFrequency(text); // Count frequency
System.out.printf("%-15s%-15s%-15s%-15s ",
"ASCII Code", "Character", "Frequency", "Code");
Tree tree = getHuffmanTree(counts); // Create a Huffman tree
String[] codes = getCode(tree.root); // Get codes
for (int i = 0; i < codes.length; i++)
if (counts[i] != 0) // (char)i is not in text if counts[i] is 0
System.out.printf("%-15d%-15s%-15d%-15s ",
i, (char)i + "", counts[i], codes[i]);
}
/** Get Huffman codes for the characters
* This method is called once after a Huffman tree is built
*/
public static String[] getCode(Tree.Node root) {
if (root == null) return null;
String[] codes = new String[2 * 128];
assignCode(root, codes);
return codes;
}
/* Recursively get codes to the leaf node */
private static void assignCode(Tree.Node root, String[] codes) {
if (root.left != null) {
root.left.code = root.code + "0";
assignCode(root.left, codes);
root.right.code = root.code + "1";
assignCode(root.right, codes);
}
else {
codes[(int)root.element] = root.code;
}
}
/** Get a Huffman tree from the codes */
public static Tree getHuffmanTree(int[] counts) {
// Create a heap to hold trees
Heap<Tree> heap = new Heap<Tree>(); // Defined in Listing 24.10
for (int i = 0; i < counts.length; i++) {
if (counts[i] > 0)
heap.add(new Tree(counts[i], (char)i)); // A leaf node tree
}
while (heap.getSize() > 1) {
Tree t1 = heap.remove(); // Remove the smallest weight tree
Tree t2 = heap.remove(); // Remove the next smallest weight
heap.add(new Tree(t1, t2)); // Combine two trees
}
return heap.remove(); // The final tree
}
/** Get the frequency of the characters */
public static int[] getCharacterFrequency(String text) {
int[] counts = new int[256]; // 256 ASCII characters
for (int i = 0; i < text.length(); i++)
counts[(int)text.charAt(i)]++; // Count the character in text
return counts;
}
/** Define a Huffman coding tree */
public static class Tree implements Comparable<Tree> {
Node root; // The root of the tree
/** Create a tree with two subtrees */
public Tree(Tree t1, Tree t2) {
root = new Node();
root.left = t1.root;
root.right = t2.root;
root.weight = t1.root.weight + t2.root.weight;
}
/** Create a tree containing a leaf node */
public Tree(int weight, char element) {
root = new Node(weight, element);
}
@Override /** Compare trees based on their weights */
public int compareTo(Tree t) {
if (root.weight < t.root.weight) // Purposely reverse the order
return 1;
else if (root.weight == t.root.weight)
return 0;
else
return -1;
}
public class Node {
char element; // Stores the character for a leaf node
int weight; // weight of the subtree rooted at this node
Node left; // Reference to the left subtree
Node right; // Reference to the right subtree
String code = ""; // The code of this node from the root
/** Create an empty node */
public Node() {
}
/** Create a node with the specified weight and character */
public Node(int weight, char element) {
this.weight = weight;
this.element = element;
}
}
}
}
Explanation / Answer
Solution: Please follow these coding as shown in below...
import java.io.*;
import java.util.BitSet;
/**
* HuffmanCoding class, the main class for the Huffman coding..
*/
public class HuffmanCoding
{
public static void main (String [] args)
{
BufferedReader in = new BufferedReader(
new InputStreamReader(System.in));
try
{
// file name and create a file object
System.out.print("Please input the text file name: ");
String fileName = in.readLine();
System.out.println();
File f = new File(fileName);
// Exit the program if the file cannot be found
if (!f.exists() )
{
System.err.println("Error: File not found!");
System.exit(1);
}
// New instance of a HuffmanCoding class
HuffmanCoding hc = new HuffmanCoding(f);
// Print out the frequency table
System.out.print("Print out the frequency table (y/n)?");
String yOrn = in.readLine();
System.out.println();
if(yOrn.charAt(0) == 'Y' || yOrn.charAt(0) == 'y')
{
hc.printOriginMessage(f);
System.out.println();
hc.printFreqs();
}
System.out.println("");
HuffmanTree ht = new HuffmanTree(hc.freqs, hc.charCounter);
System.out.println("");
// Print the Huffman tree
System.out.print("Print out the Huffman tree (y/n)?");
yOrn = in.readLine();
System.out.println();
if(yOrn.charAt(0) == 'Y' || yOrn.charAt(0) == 'y')
{
ht.printHuffmanTree();
}
System.out.println("");
System.out.println("");
// Print the code table
System.out.print("Print out the code table(y/n)?");
yOrn = in.readLine();
System.out.println();
if(yOrn.charAt(0) == 'Y' || yOrn.charAt(0) == 'y')
{
hc.printOriginMessage(f);
ht.printCodeTable();
}
System.out.println("");
System.out.println("");
// Print the bit pattern of the input message
System.out.print("Print the bit pattern for the input file (y/n)?");
yOrn = in.readLine();
System.out.println();
BitSet bs = hc.encode(f, ht);
// The logical size of a BitSet; used only for JDK1.2
//int bssize = bs.length();
// The logical size of a BitSet; used for JDK1.1.
int bssize = CodeTable.lengthOf(bs);
if(yOrn.charAt(0) == 'Y' || yOrn.charAt(0) == 'y')
{
System.out.println("Here is the coded message: ");
hc.printBitPattern(bs, 32);
System.out.println(" "+(f.length()+1)+" characters encoded in "+
(bssize-1)+ " bits, "+ ((float)(bssize-1))/f.length() +
" bits per char.");
}
System.out.println("");
System.out.println("");
// Translate the bit pattern to ascii message
System.out.print("Translate the bit pattern back to its original form(y/n)?");
yOrn = in.readLine();
System.out.println();
if(yOrn.charAt(0) == 'Y' || yOrn.charAt(0) == 'y')
{
System.out.println("DECODED MESSAGE: ");
String ds = hc.decode(bs, ht);
System.out.println(ds);
System.out.println();
System.out.println("Note: <EOF> indicates the EOF of the input message file.");
}
System.out.println("");
}
catch (Exception e) // Catch all the exceptions
{
System.out.println(e);
}
}
/**
* Constructor for HuffmanCoding
* @param txtFile the file to be coded
*/
public HuffmanCoding(File txtFile)
{
this.txtFile = txtFile;
freqs = new int[256];
for( int i = 0; i < 256; i++) freqs[i] = 0;
charCounter = 0;
try
{
// Get file size
int fileSize = (int)txtFile.length();
// Include EOF in the file size
fileSize ++;
// Open the fileinput stream
FileInputStream in = new FileInputStream(txtFile);
int index = -1;
for(int i = 0; i < fileSize; i++)
{
// Read the file byte by byte
index = (int)in.read();
// Read the EOF simbol and put into freqs[0]
if (index == -1)
{
if(freqs[0] == 0) charCounter ++;
freqs[0] ++;
}
else if (index > 0 && index < 256)
{
if (freqs[index] == 0) charCounter ++;
// Put the byte into the array
freqs[index]++;
}
}
// Report erro if NULL appears in the file; should never happen
if(freqs[0] != 1) System.out.println("There should not be a "
+ "NULL character and only one EOF character in the file! "
+ freqs[0]);
}
catch (IOException e)
{
System.out.println("Error: Cannot read file!");
}
}
/**
* Print out the original message
*/
public void printOriginMessage(File f)
{
System.out.println("ORIGINAL INPUT MESSAGE:");
try
{
// Get file size
int fileSize = (int)f.length();
// Open the fileinput stream
FileInputStream in = new FileInputStream(f);
char [] b = new char[fileSize];
for(int i=0;i<fileSize;i++) b[i] = (char)in.read();
// Output the message in the file and a <EOF> indicating
// the EOF character of the file
System.out.print(String.copyValueOf(b, 0, fileSize)+"<EOF>");
System.out.println();
}
catch (IOException e)
{
System.out.println("Error: Cannot read file!");
}
}
/**
* Print out the frequency table of the file
*/
public void printFreqs()
{
System.out.println(" Frequency Table ");
System.out.println("==============================");
System.out.println("CHARACTER | ASCII | FREQUENCY ");
System.out.println("==============================");
for(int i = 0; i < 256; i++)
{
if(freqs[i] > 0)
{
char c = (char)i;
String s = String.valueOf(c);
if( i < 33 || i > 126)
{
if( i == 10 ) s = "NL";
else if( i == 13 ) s = "CR";
else if( i == 32 ) s = "SB";
else if( i == 0 ) s = "EOF";
else s = "CC";
}
String sp1 = space(3);
String sp2;
if( i > 0 )
sp2 = space(13-lenOfInt(i)-s.length());
else
sp2 = space(13-5-s.length());
String sp3 = space(9-lenOfInt(freqs[i]));
if( i > 0 )
System.out.print(sp1 + s + sp2 + i + sp3 + freqs[i]);
else
System.out.print(sp1 + s + sp2 +"-1(*)"+ sp3 + freqs[0]);
System.out.println();
}
}
System.out.println();
System.out.println("* Not indicate the real ASCII code");
}
/**
* Return the BitSet of a text file
* @param f, the file to be coded
* @param ht, the Huffman tree for the file
*/
public BitSet encode( File f, HuffmanTree ht )
{
return ht.encode(f);
}
/**
* Return the ascii string for the bit pattern
* @param bs, the bitset
* @param ht, the Huffman tree
*/
public String decode( BitSet bs, HuffmanTree ht )
{
return ht.decode(bs);
}
/**
* Print the bitSet in a bit pattern
* @param bs, the BitSet
* @param lineWidth, the line width when printing with word wrapped manner
*/
public void printBitPattern( BitSet bs , int lineWidth)
{
PrintStack ps = new PrintStack(lineWidth);
// The logical size of a BitSet; used only in JDK1.2
//int n = bs.length();
// The logical size of a BitSet; used only in JDK1.1.*
int n = CodeTable.lengthOf(bs);
if(!bs.get(n-1)) System.err.println("Wrong code!");
else for(int i = n - 2; i >= 0; i--)
ps.printWord(bs.get(i)?"1":"0");
}
File txtFile; // The file to be coded
int [] freqs; // Integer array to store character frequencies
int charCounter; // Number of different characters
/**
* Used when print the frequency table
*/
private String space( int i )
{
char [] c = new char[i];
for (int j = 0; j< i; j++) c[j]=' ';
return String.copyValueOf(c);
}
/**
* Used when print the frequency table
*/
private int lenOfInt( int i)
{
int tmp = i;
int len = 0;
if(i == 0) return 1;
while(tmp > 0)
{
tmp /= 10;
len ++;
}
return len;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.