==================================================================================================

import java.util.*; import java.io.*;

/** This is the class that generates a Huffman encoding table and encodes a String using that encoding strategy */ public class TestHuffman{ public static void main(String[] args){ String forGeneratingCounts = ""; Scanner readFromConsole = new Scanner(System.in); try{ System.out.println("What file to load for frequency counts: "); String fName = readFromConsole.nextLine(); FileInputStream fis = new FileInputStream(fName); Scanner fscn = new Scanner(fis); while(fscn.hasNext()) forGeneratingCounts+=fscn.nextLine().toUpperCase().trim(); //Absorbing newline characters...not used in frequency counts fscn.close(); } catch(Exception e){ System.out.println("You must type an appropriate file name :("); System.out.println("\t"+e.getMessage()); System.exit(1); } //This will construct the tree/lookup table HuffEncodable myHuffEncoding = new HuffCodes(); //TODO: HuffCodes is the name of your file myHuffEncoding.constructEncoding(forGeneratingCounts); //Testing the encoding, assume letters typed are letters seen in document boolean keepEncoding = true; while(keepEncoding){ System.out.println("(ASCII) Enter a string to encode to binary (just press enter to stop looping): "); String toEncode = readFromConsole.nextLine(); keepEncoding = !toEncode.isEmpty(); if(keepEncoding) System.out.println(" Encoding: \t"+myHuffEncoding.encode(toEncode)); }

//Testing the decoding, assume only 1's and 0's typed boolean keepDecoding = true; while(keepDecoding){ System.out.println("(BINARY) Enter a binary sequence to convert to ASCII (just press enter to stop looping): "); String toDecode = readFromConsole.nextLine(); keepDecoding = !toDecode.isEmpty(); if(keepDecoding) System.out.println(" Decoding: \t"+myHuffEncoding.decode(toDecode)); }

//Print visual System.out.println(myHuffEncoding); } }

=====================================================================================

/************************************************************************************************ * * AT SOME POINT MUST USE ARRAYHEAP IN IMPLEMENTATION * ************************************************************************************************/ //TODO: ONLY Code that is modified should be done in the class that implements this...can create additional class // that this one uses, as well as additional methods.

public interface HuffEncodable{ //TODO: How to generate the huff encoding... public void constructEncoding(String forCounts);

//TODO: Using the generated encoding/tree convert the ASCII text to a binary sequence public String encode(String text);

//TODO: Using the generated encoding/tree convert the binary sequence to ASCII public String decode(String binary);

//TODO: Must override toString, Generate a nice string to show all characters and their encoding (A:101001,B:1101,...) or so }

=============================================================================================

public class ArrayHeap>{ private T[] data; private int last; private boolean isMin; public ArrayHeap(){ this(10,false); } public ArrayHeap(boolean isMin){ this(10,isMin); } public ArrayHeap(int sz, boolean isMin){ data=(T[])new Comparable[sz]; last=0; this.isMin=isMin; } public void enqueue(T d){ if(last==data.length){ T[] ndata=(T[])new Comparable[last*2]; for(int i=0; i0){//swap T temp = data[current]; data[current]=data[parent]; data[parent]=temp; current=parent; parent = (current-1)/2; } } } public T dequeue(){ T toRet = data[0]; data[0]=data[--last]; int current=0; int child = 2*current+1; //left int right = 2*current+2; //right if(isMin){ if( right0){//swap T temp = data[current]; data[current]=data[child]; data[child]=temp; current=child; child = 2*current+1; //left right = 2*current+2; //right if( right0){ child=right; } while(child0){ child=right; } } } return toRet; } public int getSize(){return last;} public static void main(String[] args){ ArrayHeap heap=new ArrayHeap(); String[] lets = "G L J C E T R B a W A".split(" "); for(String let : lets) heap.enqueue(let); while(heap.getSize()!=0) System.out.println(heap.dequeue()); } }

===============================================================================

public class ArrayHeapClone>{ private T[] data; private int last; private int minMult; public ArrayHeapClone(){ this(10,false); } public ArrayHeapClone(boolean isMin){ this(10,isMin); } public ArrayHeapClone(int sz, boolean isMin){ data=(T[])new Comparable[sz]; last=0; if(isMin) minMult=-1; else minMult=1; } public void enqueue(T d){ if(last==data.length){ T[] ndata=(T[])new Comparable[last*2]; for(int i=0; i0){//swap T temp = data[current]; data[current]=data[parent]; data[parent]=temp; current=parent; parent = (current-1)/2; } } public T dequeue(){ T toRet = data[0]; data[0]=data[--last]; int current=0; int child = 2*current+1; //left int right = 2*current+2; //right if( right0){ child=right; } while(child0){ child=right; } } return toRet; } public int getSize(){return last;} public static void main(String[] args){ ArrayHeap heap=new ArrayHeap(true); String[] lets = "G L J C E T R B a W A".split(" "); for(String let : lets) heap.enqueue(let); while(heap.getSize()!=0) System.out.println(heap.dequeue()); } }

================================================================

public class ArrayHeapPriority{ private T[] data; private double[] priorities; private int last; private boolean isMin; public ArrayHeapPriority(){ this(10,false); } public ArrayHeapPriority(boolean isMin){ this(10,isMin); } public ArrayHeapPriority(int sz, boolean isMin){ data=(T[])new Object[sz]; priorities=new double[sz]; last=0; this.isMin=isMin; } private void debug(){ for(int i=0; ipriorities[parent] ^ isMin)){//swap T temp = data[current]; data[current]=data[parent]; data[parent]=temp; double ptemp = priorities[current]; priorities[current]=priorities[parent]; priorities[parent]=ptemp; current=parent; parent = (current-1)/2; } } public T dequeue(){ T toRet = data[0]; data[0]=data[--last]; priorities[0]=priorities[last]; // Update priority to top as well int current=0; int child = 2*current+1; //left int right = 2*current+2; //right if( rightpriorities[child] ^ isMin)){ child=right; } while(childpriorities[child] ^ isMin)){ child=right; } } return toRet; } public int getSize(){return last;} public static void main(String[] args){ ArrayHeapPriority heap=new ArrayHeapPriority(true); String[] lets = "G L J C E T R B a W A".split(" "); for(int i=0; i What is Huftman Encoding?d In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The output is a variable-length code table for encoding a source symbol (such as a character in a file). The table is derived from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. More common symbols are generally represented using fewer bits than less common symbols EXAMPLE: Encoding BACADAEAFABBAAAGAH Fixed-Length Table: Frequency-Based Table A 000 C 010 E 100 G 110 101() 1100 G 111() Encoded as the string of 54 bits: Encoded to 42 bits ( 20% savings) 0010 0001 0000 0110 0010 0000 1010 0000 1001 0000 0000 0110 0001 11 1000 1010 0101 1011 0001 1010 1001 0000 0111 0011 11 What is Huftman Encoding?d In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The output is a variable-length code table for encoding a source symbol (such as a character in a file). The table is derived from the estimated probability or frequency of occurrence (weight) for each possible value of the source symbol. More common symbols are generally represented using fewer bits than less common symbols EXAMPLE: Encoding BACADAEAFABBAAAGAH Fixed-Length Table: Frequency-Based Table A 000 C 010 E 100 G 110 101() 1100 G 111() Encoded as the string of 54 bits: Encoded to 42 bits ( 20% savings) 0010 0001 0000 0110 0010 0000 1010 0000 1001 0000 0000 0110 0001 11 1000 1010 0101 1011 0001 1010 1001 0000 0111 0011 11