import java.io.File;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.IOException;import java.io.InputStream;import java.io.OutputStream;import java.util.PriorityQueue;/** * Lab 7: Huffman tree * * A class to provides methods for huffman tree based un/compression of * text-files */public class Huffman { /** * The translation table used to compress/uncompress the last file. * * This table is represented by an array of BitStrings, where table[i] * holdes the BitString for the i-th character. * * You may use an array with 256 entries even if not every character occures * in the inputfile. */ private BitString[] table; /** * This method opens and compresses the file inFilename and saves the * results in the file outFilename. * * IMPORTANT: This method is for your testing only. It is ready to use (if * Huffman::compress(String, OutputStream) is implemented). * * You can modify it. * * @param inFilename * the file to compress * @param outFilename * the result file * @throws IOException */ public void compress(String inFilename, String outFilename) throws IOException { File outFile = new File(outFilename); if (!outFile.exists()) outFile.createNewFile(); compress(inFilename, new FileOutputStream(outFile)); } /** * This method performs the compression of the file inFilename. It writes * the results to the OutputStream out. * * IMPORTANT: We use this method for testing your solution. Don't modify the * signature of this method. * * Implement a Huffman Tree based compression. First write the used code * table into the file as described in the task, followed by the compressd * data. You may use the class HuffmanStreamWriter here. This class * proviedes methods to write down the table and for writing BitStrings into * the OutputStream. * * @param inFilename * the file to compress * @param out * outputStram to wirte the results * @throws IOException */ public void compress(String inFilename, OutputStream out) throws IOException { // initialize storage for HuffmanTree-creation PriorityQueue<HuffmanTree> queue = new PriorityQueue<HuffmanTree>(256, new HuffmanComparator()); // initialize InputStream HuffmanStreamReader reader = new HuffmanStreamReader(new FileInputStream(inFilename)); // get counter of chars int[] count = getOccurence(reader); // for each possible ascii-code for (int i = 0; i < 256; i++) { // check if char is contained in file if (count[i] != 0){ // create HuffmanTree only containing char and it's count HuffmanTree temp = new HuffmanTree((char) i, count[i]); // add it to storage queue.add(temp); } } // while there are more than 1 HuffmanTree in storage while (queue.size() > 1) { // get best HuffmanTree HuffmanTree first = queue.poll(); // get second-best HuffmannTree HuffmanTree second = queue.poll(); // create new HuffmanTree (both currently best HuffmanTree's as subtrees) HuffmanTree tempTree = new HuffmanTree(first, second); // add newly created HuffmanTree to storage queue.offer(tempTree); } // get last remaining HuffmanTree of storage HuffmanTree result = queue.poll(); // read codetable out of the resulting HuffmanTree table = result.encode(new BitString[256], new BitString()); // initialize HuffmanStreamWriter HuffmanStreamWriter writer = new HuffmanStreamWriter(out); // write codetable writer.writeCodeTable(table); // initialize buffer and iteration-variable BitString buffer = new BitString(); int bit; // while end of InputStream isn't reached while ((bit = reader.readBit()) != -1) { // if next bit equals "0" append false/0 to buffer if (bit == 0) buffer.append(false); // otherwise next bit equals "1" -> append true/1 to buffer else buffer.append(true); // for every BitString in codetable for (int i = 0 ; i < table.length ; i++){ // check if matching BitString is found and break for-loop if yes if (buffer.toString().compareTo(table[i].toString()) == 0){ // if matching BitString found write it to OutputStream writer.write(table[i]); // and reset buffer buffer = new BitString(); } } } // write EoF-Code to end of file writer.write(table[0]); // close all open streams writer.close(); reader.close(); out.close(); } /** * To count the occurence of every char in a stream. * * @param stream * stream to count chars in * @return * int-array containing counter for every char (index = ascii-code) * @throws IOException */ private int[] getOccurence(InputStream stream) throws IOException { // initialize result-array int[] result = new int[256]; // set every counter to 0 for (int i = 0 ; i < result.length ; i++){ result[i] = 0; } // while end of stream isn't reached while (stream.available() > 0) { // read next char int newChar = stream.read(); // check if char is valid if (newChar == (char) 0) throw new InvalidCharacterException(); // if got valid char increase counter in array else result[newChar]++; } // set counter of EoF-Code to 1 (according to task) result[0] = 1; // return counter-array return result; } /** * This method opens and uncompresses the file inFilename and saves the * results in the file outFilename. * * IMPORTANT: This method is for your testing only. It is ready to use (if * Huffman::uncompress(String, OutputStream) is implemented). * * You can modify it. * * @param inFilename * the file to uncompress * @param outFilename * the result file * @throws IOException */ public void uncompress(String inFilename, String outFilename) throws IOException { File outFile = new File(outFilename); if (!outFile.exists()) outFile.createNewFile(); uncompress(inFilename, new FileOutputStream(outFile)); } /** * This method performs the uncompression of the file inFilename. It writes * the results to the OutputStream out. * * IMPORTANT: We use this method for testing your solution. Don't modify the * signature of this method. * * Implement a Huffman Tree based uncompression. The used code table is * stored at the begin of the file. You can use the class * HuffmanStreamReader to get the table. This class also offers methods to * read a file bit by bit. * * @param inFilename * the file to uncompress * @param out * outputStram to wirte the results * @throws IOException */ public void uncompress(String inFilename, OutputStream out) throws IOException { // initialize HuffmanStreamReader HuffmanStreamReader stream = new HuffmanStreamReader(new FileInputStream(inFilename)); // read codetable table = stream.getCodeTable(); // initialize buffer and iteration-variable BitString buffer = new BitString(); int bit; // while contains bits while ((bit = stream.readBit()) != -1){ // if next bit equals "0" -> append false/0 to result-BitString if (bit == 0) buffer.append(false); // else next bit equals "1" -> append true/1 to result-BitString else buffer.append(true); // for every BitString in codetable for (int i = 0 ; i < table.length ; i++){ // check if matching BitString is found if (buffer.toString().compareTo(table[i].toString()) == 0){ // write found ascii-code to OutputStream out.write(i); // and reset buffer buffer = new BitString(); } } } // close all open streams stream.close(); out.close(); } /** * This method returns the code table used by the last compress/uncompress * operation. * * @return the code table */ public BitString[] getCodeTable() { return table; }}--------------------------------------------------------------------------------------------public class HuffmanTree{ // name of node (-> char represented by node) public int name; // weight of huffmann-tree public int weight = 0; // right subtree public HuffmanTree right = null; // left subtree public HuffmanTree left = null; /** * To construct a new empty HT (subtrees are null and weight is 0). */ public HuffmanTree() { } /** * To construct a leaf of the HT with given name (subtrees are empty HTs). * * @param name * name of leaf */ public HuffmanTree(int name, int weight) { this.name = name; this.weight = weight; right = new HuffmanTree(); left = new HuffmanTree(); } /** * To construct a new HT with 2 given subtrees. * * @param left * left subtree * @param right * right subtree */ public HuffmanTree(HuffmanTree left, HuffmanTree right) { // set left subtree this.left = left; // set right subtree this.right = right; // update weight (sum of weights of both subtrees) this.weight = left.weight + right.weight; } /** * To check if HT is empty or not. * * @return * true, if both subtrees are null */ public boolean isEmpty() { return left == null && right == null; } /** * To check if HT is a leaf. * * @return * true, if actual HT is non-empty, but both subtrees are */ public boolean isLeaf() { return !this.isEmpty() && left.isEmpty() && right.isEmpty(); } /** * To traverse the HT writing result into a codetable * * @param codeTable * to codetable to fill codes in * @param path * path in HT = code of char * @return * filled codetable */ public BitString[] encode(BitString[] codeTable, BitString path) { // check if leaf is reached if (isLeaf()) { // if yes fill in code of char represented by leaf codeTable[name] = path; return codeTable; } // recursively traverse right subtree right.encode(codeTable, path.clone().append(true)); // and left subtree left.encode(codeTable, path.clone().append(false)); return codeTable; }}--------------------------------------------------------------------------------------------public class BitString implements Cloneable { private byte[] string; private int length; /** * Creates a new BitString filled with the length bits from data. * * @param data * input data * @param length * the length of the new BitString */ public BitString(byte[] data, int length) { if (length < 1) throw new IllegalArgumentException("length must be bigger than 0"); if (data == null) throw new IllegalArgumentException("data may not be null"); if ((length - 1) / 8 + 1 > data.length) throw new IllegalArgumentException( "data contains not enough elements for length: " + length); string = new byte[(length - 1) / 8 + 1]; for (int i = 0; i < string.length - 1; i++) string[i] = data[i]; this.length = length; // set unused bits in last byte to zero! if (length % 8 == 0) { // no unused bits string[string.length - 1] = data[string.length - 1]; } else { // apply bitmask byte mask = (byte) (255 << (8 - length % 8)); string[string.length - 1] = (byte) (data[string.length - 1] & mask); } } /** * Creates an empty BitString */ public BitString() { this.length = 0; } /** * Append a bit to the BitString * * @param the * bit to append to string * @return returns the complete BitString (this) */ public BitString append(boolean bit) { if (this.length % 8 == 0) { this.grow(1); } if (bit) { // set bit string[length / 8] = (byte) (string[length / 8] | (1 << (7 - length % 8))); } length++; return this; } /** * Clones the BitString * * @see java.lang.Object#clone() */ public BitString clone() { return string == null ? new BitString() : new BitString(string.clone(), length); } /** * Returns the BitString as byte array * * @return byte array or null if no bits are in BitString */ public byte[] getByteArray() { return (this.string == null) ? null : this.string.clone(); } /** * Returns the BitString as an boolean array * * @return boolean array or null if no bits are in BitString */ public boolean[] getBitArray() { // return "empty array" if (this.length == 0) return null; // build array boolean[] result = new boolean[this.length]; int bitShift = 7; int arrayPos = 0; int resultPos = 0; for (int i = 0; i < this.length; i++) { result[resultPos++] = (string[arrayPos] & 1 << bitShift) != 0; if (--bitShift < 0) { bitShift = 7; arrayPos++; } } return result; } /** * Returns the cirrent length of the BitString (in bits) * * @return the length of the BitString in bits */ public int getLength() { return this.length; } /** * Allocates more space for bits * * @param size */ private void grow(int size) { if (this.string == null) { this.string = new byte[size]; } else { // create new array byte[] newString = new byte[this.string.length + size]; // copy old content for (int i = 0; i < this.string.length; i++) newString[i] = this.string[i]; // replace array this.string = newString; } } /** * Returns a '0', '1' string * * @see java.lang.Object#toString() */ public String toString() { StringBuffer buffer = new StringBuffer(); int bitShift = 7; int arrayPos = 0; for (int i = 0; i < this.length; i++) { buffer.append((string[arrayPos] & 1 << bitShift) != 0 ? "1" : "0"); if (--bitShift < 0) { bitShift = 7; arrayPos++; } } return buffer.toString(); }}--------------------------------------------------------------------------------------------import java.io.IOException;import java.io.InputStream;public class HuffmanStreamReader extends InputStream { private BitString[] codeTable; private InputStream stream; private int buffer; private int bitsInBuffer; /** * Construts a new HuffmanStreamReader upon a given InputStream * * This Reader tries to read a code table from the Stream. * * @param stream * the InputStream * @throws IOException */ public HuffmanStreamReader(InputStream stream) throws IOException { super(); this.stream = stream; this.readCodeTable(); } /** * Reads the code table * * @throws IOException */ private void readCodeTable() throws IOException { codeTable = new BitString[256]; int character, codeLength, byteLength; character = this.read(); codeLength = this.read(); // read table entry by entry do { byteLength = (codeLength - 1) / 8 + 1; byte[] bytes = new byte[byteLength]; for (int i = 0; i < byteLength; i++) bytes[i] = (byte) this.read(); codeTable[character] = new BitString(bytes, codeLength); character = this.read(); codeLength = this.read(); } while (character != -1 && codeLength != 0); } /** * Returns the code table * * @return the code table */ public BitString[] getCodeTable() { return this.codeTable; } /** * @see java.io.InputStream#read() */ public int read() throws IOException { return this.stream.read(); } /** * Reads and returns a bit (as integer) from the stream * * @return the int value of the current bit or -1 if end of stream is * reached. * @throws IOException */ public int readBit() throws IOException { if (this.bitsInBuffer == 0) { this.buffer = this.read(); if (this.buffer == -1) return -1; this.bitsInBuffer = 8; } return (this.buffer >> (this.bitsInBuffer-- - 1)) & 1; }}--------------------------------------------------------------------------------------------import java.io.IOException;import java.io.OutputStream;public class HuffmanStreamWriter extends OutputStream { private int buffer = 0; private int bufferOffset = 0; private OutputStream stream; /** * Construct a new HuffmanStreamWriter upon a given OutputStream. * * @param stream * the used OutputStream */ public HuffmanStreamWriter(OutputStream stream) { super(); this.stream = stream; } /** * Writes a bit to the file. * * Note: Bits ar bufferd until a byte is complete. * * @param bit * the bit to wirte * @throws IOException */ private void writeBit(int bit) throws IOException { // append bit to buffer buffer |= (bit & 1) << (7 - bufferOffset++); if (bufferOffset == 8) { flushBitBuffer(); } } /** * Forces the bitBuffer to be flushed even if byte is inclomplete: - There * must be atleast one bit to be flushed - Missing Bits ar filled with zeros * * @throws IOException */ public void flushBitBuffer() throws IOException { if (bufferOffset != 0) { this.write(buffer); // reset buffer & offset bufferOffset = 0; buffer = 0; } } /** * Writes a BitString Object to the OutputStream * * @param bitString * to wirte * @throws IOException */ public void write(BitString bitString) throws IOException { for (boolean bit : bitString.getBitArray()) { this.writeBit(bit ? 1 : 0); } } /** * Flushes BitBuffer and closes the stream. * * To ensure that no bits are "left in buffer" this method should be called * after all write operations are finished. * * @see java.io.OutputStream#close() */ public void close() throws IOException { // pad buffer with zeros and flush it this.flushBitBuffer(); // execute super method super.close(); } /** * Writes a BitString[] representing the code table to the stream. * * @param table * to write. * @throws IOException */ public void writeCodeTable(BitString[] table) throws IOException { for (int i = 0; i < table.length; i++) { if (table[i] != null) { this.write(i); this.write(table[i].getLength()); this.write(table[i]); this.flushBitBuffer(); } } // write end of table this.write((char) 0); this.write((char) 0); } /** * @see java.io.OutputStream#write(int) */ public void write(int character) throws IOException { stream.write(character); }}--------------------------------------------------------------------------------------------