Can anyone help me with this assignment Huffman coding, there six classes ------
ID: 3756456 • Letter: C
Question
Can anyone help me with this assignment Huffman coding, there six classes
----------------------------------------------------------------------------------------------------------------------------------
import java.io.*;
public class HuffmanOutputStream {
//add additional private variables as needed
//do not modify the public methods signatures or add public methods
DataOutputStream d;
public HuffmanOutputStream(String filename, String tree, int totalChars) {
try {
d = new DataOutputStream(new FileOutputStream(filename));
d.writeUTF(tree);
d.writeInt(totalChars);
}
catch (IOException e) {
}
//add other initialization statements as needed
}
public void writeBit(char bit) {
//PRE:bit == '0' || bit == '1'
}
public void close() {
//write final byte (if needed)
//close the DataOutputStream
}
}
----------------------------------------------------------------------------------------------------------------------------------
import java.io.*;
public class HuffmanInputStream {
private String tree;
private int totalChars;
private DataInputStream d;
public HuffmanInputStream(String filename) {
try {
d = new DataInputStream(new FileInputStream(filename));
tree = d.readUTF();
totalChars = d.readInt();
}
catch (IOException e) {
}
//add other initialization statements as needed
}
public int readBit() {
//returns the next bit is the file
//the value returned will be either a 0 or a 1
}
public String getTree() {
//return the tree representation read from the file
}
public int getTotalChars() {
//return the character count read from the file
}
}
----------------------------------------------------------------------------------------------------------------------------------
import java.util.*;
public class HuffmanTree {
// DO NOT include the frequency or priority in the tree
private class Node {
private Node left;
private char data;
private Node right;
private Node parent;
private Node(Node L, char d, Node R, Node P) {
left = L;
data = d;
right = R;
parent = P;
}
}
private Node root;
private Node current; // this value is changed by the move methods
public HuffmanTree() {
root = null;
current = null;
}
public HuffmanTree(char d) {
// makes a single node tree
}
public HuffmanTree(String t, char nonLeaf) {
// Assumes t represents a post order representation of the tree as discussed
// in class
// nonLeaf is the char value of the data in the non-leaf nodes
// in classs we used (char) 128 for the non-leaf value
}
public HuffmanTree(HuffmanTree b1, HuffmanTree b2, char d) {
// makes a new tree where b1 is the left subtree and b2 is the right subtree
// d is the data in the root
}
// use the move methods to traverse the tree
// the move methods change the value of current
// use these in the decoding process
public void moveToRoot() {
// change current to reference the root of the tree
}
public void moveToLeft() {
// PRE: the current node is not a leaf
// change current to reference the left child of the current node
}
public void moveToRight() {
// PRE: the current node is not a leaf
// change current to reference the right child of the current node
}
public void moveToParent() {
// PRE: the current node is not the root
// change current to reference the parent of the current node}
}
public boolean atRoot() {
// returns true if the current node is the root otherwise returns false
}
public boolean atLeaf() {
// returns true if current references a leaf other wise returns false
}
public char current() {
// returns the data value in the node referenced by current
}
public class PathIterator implements Iterator<String> {
// the iterator returns the path (a series of 0s and 1s) to each leaf
// DO NOT compute all paths in the constructor
// only compute them as needed (similar to what you did in homework 2)
// add private methods and variables as needed
public PathIterator() {
}
public boolean hasNext() {
}
public String next() {
// the format of the string should be leaf value, a space, a sequence of
// 0s and 1s
// the 0s and 1s indicate the path from the root the node containing
// the leaf value
}
public void remove() {
// optional method not implemented
}
}
public Iterator<String> iterator() {
// return a new path iterator object
}
public String toString() {
// returns a string representation of the tree using the postorder format
// discussed in class
}
}
----------------------------------------------------------------------------------------------------------------------------------
public class BinaryHeap {
// implements a binary heap where the heap rule is the value in the parent
// node is less than
// or equal to the values in the child nodes
// the implementation uses parallel arrays to store the priorities and the
// trees
// you must use this implementation
int priority[];
HuffmanTree trees[];
int size;
public BinaryHeap(int s) {
priority = new int[s + 1];
trees = new HuffmanTree[s + 1];
size = 0;
}
public void removeMin() {
// PRE: size != 0
// removes the priority and tree at the root of the heap
}
public int getMinPriority() {
// PRE: size != 0
// return the priority in the root of the heap
}
public HuffmanTree getMinTree() {
// PRE: size != 0
// return the tree in the root of the heap
}
public boolean full() {
// return true if the heap is full otherwise return false
}
public void insert(int p, HuffmanTree t) {
// insert the priority p and the associated tree t into the heap
// PRE !full()
}
public int getSize() {
// return the number of values (priority , tree) pairs in the heap
}
}
----------------------------------------------------------------------------------------------------------------------------------
import java.io.*;
import java.util.*;
public class HuffmanDecode {
public HuffmanDecode(String in, String out) {
//implements the Huffman Decode Algorithm
//Add private methods and instance variables as needed
}
public static void main(String args[]) {
//args[0] is the name of a input file (a file created by Huffman Encode)
//args[1] is the name of the output file for the uncompressed file
new HuffmanDecode(args[0], args[1]);
// do not add anything here
}
}
----------------------------------------------------------------------------------------------------------------------------------
import java.io.*;
import java.util.*;
public class HuffmanEncode {
public HuffmanEncode(String in, String out) {
//Implements the Huffman encoding algorithm
//Add private methods and instance variables as needed
}
public static void main(String args[]) {
//args[0] is the name of the file whose contents should be compressed
//args[1] is the name of the output file that will hold the compressed
// content of the input file
new HuffmanEncode(args[0], args[1]);
// do not add anything here
}
}
Explanation / Answer
public class huffman_code {
private static final int R = 256;
private huffman_code() { }
private static class Node implements Comparable<Node> {
private final char chr;
private final int frqncy;
private final Node l, r;
Node(char chr, int frqncy, Node l, Node r) {
this.chr = chr;
this.frqncy = frqncy;
this.l = l;
this.r = r;
}
private boolean isLeaf() {
assert ((l == null) && (r == null)) || ((l != null) && (r != null));
return (l == null) && (r == null);
}
public int compareTo(Node that) {
return this.frqncy - that.frqncy;
}
}
public static void compress() {
String s = BinaryStdIn.readString();
char[] in = s.toCharArray();
int[] frqncy = new int[R];
for (int x = 0; x < in.length; x++)
frqncy[in[x]]++;
Node root = buildTrie(frqncy);
String[] st = new String[R];
buildCode(st, root, "")
writeTrie(root);
BinaryStdOut.write(in.length);
for (int x = 0; x < in.length; x++) {
String code = st[in[x]];
for (int y = 0; y < code.length(); y++) {
if (code.charAt(y) == '0') {
BinaryStdOut.write(false);
}
else if (code.charAt(y) == '1') {
BinaryStdOut.write(true);
}
else throw new IllegalStateException("Illegal state");
}
}
BinaryStdOut.close();
}
private static Node buildTrie(int[] frqncy) {
MinPQ<Node> pq1 = new MinPQ<Node>();
for (char x = 0; x < R; x++)
if (frqncy[x] > 0)
pq1.insert(new Node(x, frqncy[x], null, null));
if (pq1.size() == 1) {
if (frqncy[''] == 0) pq1.insert(new Node('', 0, null, null));
else pq1.insert(new Node('', 0, null, null));
}
while (pq1.size() > 1) {
Node l = pq1.delMin();
Node r = pq1.delMin();
Node parent = new Node('', l.frqncy + r.frqncy, l, r);
pq1.insert(parent);
}
return pq1.delMin();
}
private static void writeTrie(Node x) {
if (x.isLeaf()) {
BinaryStdOut.write(true);
BinaryStdOut.write(x.chr, 8);
return;
}
BinaryStdOut.write(false);
writeTrie(x.l);
writeTrie(x.r);
}
private static void buildCode(String[] st, Node x, String s) {
if (!x.isLeaf()) {
buildCode(st, x.l, s + '0');
buildCode(st, x.r, s + '1');
}
else {
st[x.chr] = s;
}
}
public static void expand() {
Node root = readTrie();
int len = BinaryStdIn.readInt();
for (int x = 0; x < len; x++) {
Node x = root;
while (!x.isLeaf()) {
boolean bit = BinaryStdIn.readBoolean();
if (bit) x = x.r;
else x = x.l;
}
BinaryStdOut.write(x.chr, 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");
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.