I need help completing this assignment. Please use the methods specified for thi
ID: 3769014 • Letter: I
Question
I need help completing this assignment. Please use the methods specified for this code
HuffmanCoding
Direction below:
Building a binary tree, where the “data” is a count of the frequency of each character.
public class HuffmanNode implements Comparable
public int frequency;
public char character;
public HuffmanNode left;
public HuffmanNode right;
The Huffman Node class will also need a boolean isLeaf() method, plus a static method to actually provide a count of the characters in an input file, and place those counts into a Map, with character as the unique key mapped into the integer counts of that character:
public static Map getCounts(FileInputStream input)
Your Huffman Tree class must have the following defined:
public HuffmanTree(Map counts) // Constructor
public StringBuilder compress(InputStream inputFile) // inputFile is a text file
public StringBuilder decompress(StringBuilder inputString) //inputString 1’s & 0’s
public String printSideways()
The compress method returns a string of 1’s and 0’s (bits) as per the description below. The decompress method can take that string of 1’s and 0’s, use the Huffman tree structure and recreate the text file from those bits. Finally, the printSideways in this case we build a string to return into a graphical text area. You should actually use the String Builder class, as it is mutable.
You must comment out all System.out calls before submitting your work. The client program (HuffmanGUI.java) is provided, and you need to meet these specifications listed above.
The steps involved in Huffman coding a given text source file into a destination compressed file are the following:
1.Examine the source file's contents and count the number of occurrences of each character.
2.Place each character and its frequency (count of occurrences) into a sorted "priority" queue.
3.Convert the contents of this priority queue into a binary tree with a particular structure.
4.Traverse the tree to discover the binary encodings of each character.
5.Re-examine the source file's contents, and for each character, output the encoded binary version of that character to the destination file.
Explanation / Answer
Huffman.java
/******************************************************************************
* Compilation: javac Huffman.java
* Execution: java Huffman - < input.txt (compress)
* Execution: java Huffman + < input.txt (expand)
* Dependencies: BinaryIn.java BinaryOut.java
* Data files: http://algs4.cs.princeton.edu/55compression/abra.txt
* http://algs4.cs.princeton.edu/55compression/tinytinyTale.txt
*
* Compress or expand a binary input stream using the Huffman algorithm.
*
* % java Huffman - < abra.txt | java BinaryDump 60
* 010100000100101000100010010000110100001101010100101010000100
* 000000000000000000000000000110001111100101101000111110010100
* 120 bits
*
* % java Huffman - < abra.txt | java Huffman +
* ABRACADABRA!
*
******************************************************************************/
public class Huffman {
// alphabet size of extended ASCII
private static final int R = 256;
// Do not instantiate.
private Huffman() { }
// Huffman trie node
private static class Node implements Comparable<Node> {
private final char ch;
private final int freq;
private final Node left, right;
Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
// is the node a leaf node?
private boolean isLeaf() {
assert ((left == null) && (right == null)) || ((left != null) && (right != null));
return (left == null) && (right == null);
}
// compare, based on frequency
public int compareTo(Node that) {
return this.freq - that.freq;
}
}
public static void compress() {
// read the input
String s = BinaryStdIn.readString();
char[] input = s.toCharArray();
// tabulate frequency counts
int[] freq = new int[R];
for (int i = 0; i < input.length; i++)
freq[input[i]]++;
// build Huffman trie
Node root = buildTrie(freq);
// build code table
String[] st = new String[R];
buildCode(st, root, "");
// print trie for decoder
writeTrie(root);
// print number of bytes in original uncompressed message
BinaryStdOut.write(input.length);
// use Huffman code to encode input
for (int i = 0; i < input.length; i++) {
String code = st[input[i]];
for (int j = 0; j < code.length(); j++) {
if (code.charAt(j) == '0') {
BinaryStdOut.write(false);
}
else if (code.charAt(j) == '1') {
BinaryStdOut.write(true);
}
else throw new IllegalStateException("Illegal state");
}
}
// close output stream
BinaryStdOut.close();
}
// build the Huffman trie given frequencies
private static Node buildTrie(int[] freq) {
// initialze priority queue with singleton trees
MinPQ<Node> pq = new MinPQ<Node>();
for (char i = 0; i < R; i++)
if (freq[i] > 0)
pq.insert(new Node(i, freq[i], null, null));
// special case in case there is only one character with a nonzero frequency
if (pq.size() == 1) {
if (freq[''] == 0) pq.insert(new Node('', 0, null, null));
else pq.insert(new Node('', 0, null, null));
}
// merge two smallest trees
while (pq.size() > 1) {
Node left = pq.delMin();
Node right = pq.delMin();
Node parent = new Node('', left.freq + right.freq, left, right);
pq.insert(parent);
}
return pq.delMin();
}
// write bitstring-encoded trie to standard output
private static void writeTrie(Node x) {
if (x.isLeaf()) {
BinaryStdOut.write(true);
BinaryStdOut.write(x.ch, 8);
return;
}
BinaryStdOut.write(false);
writeTrie(x.left);
writeTrie(x.right);
}
// make a lookup table from symbols and their encodings
private static void buildCode(String[] st, Node x, String s) {
if (!x.isLeaf()) {
buildCode(st, x.left, s + '0');
buildCode(st, x.right, s + '1');
}
else {
st[x.ch] = s;
}
}
public static void expand() {
// read in Huffman trie from input stream
Node root = readTrie();
// number of bytes to write
int length = BinaryStdIn.readInt();
// decode using the Huffman trie
for (int i = 0; i < length; i++) {
Node x = root;
while (!x.isLeaf()) {
boolean bit = BinaryStdIn.readBoolean();
if (bit) x = x.right;
else x = x.left;
}
BinaryStdOut.write(x.ch, 8);
}
BinaryStdOut.close();
}
private static Node readTrie() {
boolean isLeaf = BinaryStdIn.readBoolean();
if (isLeaf) {
return new Node(BinaryStdIn.readChar(), -1, null, null);
}
else {
return new Node('', -1, readTrie(), readTrie());
}
}
public static void main(String[] args) {
if (args[0].equals("-")) compress();
else if (args[0].equals("+")) expand();
else throw new IllegalArgumentException("Illegal command line argument");
}
}
BinaryStdIn.java
/******************************************************************************
* Compilation: javac BinaryStdIn.java
* Execution: java BinaryStdIn < input > output
* Dependencies: none
*
* Supports reading binary data from standard input.
*
* % java BinaryStdIn < input.jpg > output.jpg
* % diff input.jpg output.jpg
*
******************************************************************************/
import java.io.BufferedInputStream;
import java.io.IOException;
public final class BinaryStdIn {
private static BufferedInputStream in = new BufferedInputStream(System.in);
private static final int EOF = -1; // end of file
private static int buffer; // one character buffer
private static int n; // number of bits left in buffer
// static initializer
static {
fillBuffer();
}
// don't instantiate
private BinaryStdIn() { }
private static void fillBuffer() {
try {
buffer = in.read();
n = 8;
}
catch (IOException e) {
System.out.println("EOF");
buffer = EOF;
n = -1;
}
}
public static void close() {
try {
in.close();
}
catch (IOException e) {
e.printStackTrace();
throw new RuntimeException("Could not close BinaryStdIn");
}
}
public static boolean isEmpty() {
return buffer == EOF;
}
public static boolean readBoolean() {
if (isEmpty()) throw new RuntimeException("Reading from empty input stream");
n--;
boolean bit = ((buffer >> n) & 1) == 1;
if (n == 0) fillBuffer();
return bit;
}
public static char readChar() {
if (isEmpty()) throw new RuntimeException("Reading from empty input stream");
// special case when aligned byte
if (n == 8) {
int x = buffer;
fillBuffer();
return (char) (x & 0xff);
}
// combine last n bits of current buffer with first 8-n bits of new buffer
int x = buffer;
x <<= (8 - n);
int oldN = n;
fillBuffer();
if (isEmpty()) throw new RuntimeException("Reading from empty input stream");
n = oldN;
x |= (buffer >>> n);
return (char) (x & 0xff);
// the above code doesn't quite work for the last character if n = 8
// because buffer will be -1, so there is a special case for aligned byte
}
public static char readChar(int r) {
if (r < 1 || r > 16) throw new IllegalArgumentException("Illegal value of r = " + r);
// optimize r = 8 case
if (r == 8) return readChar();
char x = 0;
for (int i = 0; i < r; i++) {
x <<= 1;
boolean bit = readBoolean();
if (bit) x |= 1;
}
return x;
}
public static String readString() {
if (isEmpty()) throw new RuntimeException("Reading from empty input stream");
StringBuilder sb = new StringBuilder();
while (!isEmpty()) {
char c = readChar();
sb.append(c);
}
return sb.toString();
}
public static short readShort() {
short x = 0;
for (int i = 0; i < 2; i++) {
char c = readChar();
x <<= 8;
x |= c;
}
return x;
}
public static int readInt() {
int x = 0;
for (int i = 0; i < 4; i++) {
char c = readChar();
x <<= 8;
x |= c;
}
return x;
}
public static int readInt(int r) {
if (r < 1 || r > 32) throw new IllegalArgumentException("Illegal value of r = " + r);
// optimize r = 32 case
if (r == 32) return readInt();
int x = 0;
for (int i = 0; i < r; i++) {
x <<= 1;
boolean bit = readBoolean();
if (bit) x |= 1;
}
return x;
}
public static long readLong() {
long x = 0;
for (int i = 0; i < 8; i++) {
char c = readChar();
x <<= 8;
x |= c;
}
return x;
}
public static double readDouble() {
return Double.longBitsToDouble(readLong());
}
public static float readFloat() {
return Float.intBitsToFloat(readInt());
}
public static byte readByte() {
char c = readChar();
byte x = (byte) (c & 0xff);
return x;
}
public static void main(String[] args) {
// read one 8-bit char at a time
while (!BinaryStdIn.isEmpty()) {
char c = BinaryStdIn.readChar();
BinaryStdOut.write(c);
}
BinaryStdOut.flush();
}
}
BinaryStdOut.java
/******************************************************************************
* Compilation: javac BinaryStdOut.java
* Execution: java BinaryStdOut
* Dependencies: none
*
* Write binary data to standard output, either one 1-bit boolean,
* one 8-bit char, one 32-bit int, one 64-bit double, one 32-bit float,
* or one 64-bit long at a time.
*
* The bytes written are not aligned.
*
******************************************************************************/
import java.io.BufferedOutputStream;
import java.io.IOException;
public final class BinaryStdOut {
private static BufferedOutputStream out = new BufferedOutputStream(System.out);
private static int buffer; // 8-bit buffer of bits to write out
private static int n; // number of bits remaining in buffer
// don't instantiate
private BinaryStdOut() { }
/**
* Write the specified bit to standard output.
*/
private static void writeBit(boolean bit) {
// add bit to buffer
buffer <<= 1;
if (bit) buffer |= 1;
// if buffer is full (8 bits), write out as a single byte
n++;
if (n == 8) clearBuffer();
}
private static void writeByte(int x) {
assert x >= 0 && x < 256;
// optimized if byte-aligned
if (n == 0) {
try {
out.write(x);
}
catch (IOException e) {
e.printStackTrace();
}
return;
}
// otherwise write one bit at a time
for (int i = 0; i < 8; i++) {
boolean bit = ((x >>> (8 - i - 1)) & 1) == 1;
writeBit(bit);
}
}
// write out any remaining bits in buffer to standard output, padding with 0s
private static void clearBuffer() {
if (n == 0) return;
if (n > 0) buffer <<= (8 - n);
try {
out.write(buffer);
}
catch (IOException e) {
e.printStackTrace();
}
n = 0;
buffer = 0;
}
public static void flush() {
clearBuffer();
try {
out.flush();
}
catch (IOException e) {
e.printStackTrace();
}
}
public static void close() {
flush();
try {
out.close();
}
catch (IOException e) {
e.printStackTrace();
}
}
public static void write(boolean x) {
writeBit(x);
}
public static void write(byte x) {
writeByte(x & 0xff);
}
public static void write(int x) {
writeByte((x >>> 24) & 0xff);
writeByte((x >>> 16) & 0xff);
writeByte((x >>> 8) & 0xff);
writeByte((x >>> 0) & 0xff);
}
public static void write(int x, int r) {
if (r == 32) {
write(x);
return;
}
if (r < 1 || r > 32) throw new IllegalArgumentException("Illegal value for r = " + r);
if (x < 0 || x >= (1 << r)) throw new IllegalArgumentException("Illegal " + r + "-bit char = " + x);
for (int i = 0; i < r; i++) {
boolean bit = ((x >>> (r - i - 1)) & 1) == 1;
writeBit(bit);
}
}
public static void write(double x) {
write(Double.doubleToRawLongBits(x));
}
public static void write(long x) {
writeByte((int) ((x >>> 56) & 0xff));
writeByte((int) ((x >>> 48) & 0xff));
writeByte((int) ((x >>> 40) & 0xff));
writeByte((int) ((x >>> 32) & 0xff));
writeByte((int) ((x >>> 24) & 0xff));
writeByte((int) ((x >>> 16) & 0xff));
writeByte((int) ((x >>> 8) & 0xff));
writeByte((int) ((x >>> 0) & 0xff));
}
public static void write(float x) {
write(Float.floatToRawIntBits(x));
}
public static void write(short x) {
writeByte((x >>> 8) & 0xff);
writeByte((x >>> 0) & 0xff);
}
public static void write(char x) {
if (x < 0 || x >= 256) throw new IllegalArgumentException("Illegal 8-bit char = " + x);
writeByte(x);
}
public static void write(char x, int r) {
if (r == 8) {
write(x);
return;
}
if (r < 1 || r > 16) throw new IllegalArgumentException("Illegal value for r = " + r);
if (x >= (1 << r)) throw new IllegalArgumentException("Illegal " + r + "-bit char = " + x);
for (int i = 0; i < r; i++) {
boolean bit = ((x >>> (r - i - 1)) & 1) == 1;
writeBit(bit);
}
}
public static void write(String s) {
for (int i = 0; i < s.length(); i++)
write(s.charAt(i));
}
public static void write(String s, int r) {
for (int i = 0; i < s.length(); i++)
write(s.charAt(i), r);
}
public static void main(String[] args) {
int T = Integer.parseInt(args[0]);
// write to standard output
for (int i = 0; i < T; i++) {
BinaryStdOut.write(i);
}
BinaryStdOut.flush();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.