////////////////Huffman class

import java.util.*;

public class Huffman{

protected PriorityQueue<Entry>pq;

protected Entry[]leafEntries;

public final static int size=256;//standard ASCII

public Huffman(){

Entry entry;

leafEntries=new Entry[size];

for(int i=0;i<size;i++)

{

entry=leafEntries[i]=new Entry();

entry.freq=0;

entry.right=entry.left=entry.parent=null;

}

pq=new PriorityQueue<Entry>();

}

public void updateFrequencies(String line){

Entry entry;

for(int j=0;j<line.length();j++)

{ leafEntries[(int)(line.charAt(j))].freq++;

}

leafEntries[(int)'\r'].freq++;

}

public void createPQ(){

Entry entry;

for(int i=0;i<size;i++)

{entry=leafEntries[i];

if(entry.freq>0)pq.add(entry);

}

}

public void createHuffmanTree(){

Entry left,right,sum;

while(pq.size()>1)

{

left=pq.remove();//minimum

left.code="0";

right=pq.remove();//min

right.code="1";

sum=new Entry();

sum.parent=null;

sum.freq=left.freq+right.freq;

sum.left=left;

sum.right=right;

left.parent=sum;

right.parent=sum;

pq.add(sum);

}//while

}

public void calculateHuffmanCodes(){

String code;

Entry entry;

for(int i=0;i<size;i++)

{code="";

entry=leafEntries[i];

if(entry.freq>0)

{

while(entry.parent!=null)

{

code=entry.code+code;

entry=entry.parent;//move up adding codes

}//while

leafEntries[i].code=code;

}//if

}//for

}//method

public String getCodes(){

Entry entry;

String codes= new String();

for(int i=0;i<size;i++)

{entry=leafEntries[i];

if(entry.freq>0)codes+=(char)i+" "+entry.code+"\n";

}//for

return codes;

}

public String getEncodedLine(String line){

Entry entry;

String encodedLine=new String();

for(int i=0;i<line.length();i++)

{entry=leafEntries[(int)(line.charAt(i))];

encodedLine+=entry.code;

}//for

entry=leafEntries[(int)'\r'];

encodedLine+=entry.code;

return encodedLine;

}//method

}//class

////////////////////HuffmanTester.java

import java.io.*;

public class HuffmanTester{

BufferedReader fileReader;

PrintWriter fileWriter;

Huffman huffman;

String inFilePath;

public HuffmanTester(){

huffman=new Huffman();

}

public PrintWriter openFiles(){

final String IN_FILE_PROMPT= "\nplease enter a path for the input file:";

final String OUT_FILE_PROMPT="\nplease enter a path for the output file:";

BufferedReader keyboardReader=new BufferedReader (new InputStreamReader(System.in));

String outFilePath ,line;

boolean pathsOK=false;

while(!pathsOK)

{

try{

System.out.println(IN_FILE_PROMPT);

inFilePath=keyboardReader.readLine();

fileReader=new BufferedReader(new FileReader(inFilePath));

System.out.println(OUT_FILE_PROMPT);

outFilePath=keyboardReader.readLine();

fileWriter=new PrintWriter(new FileWriter(outFilePath));

pathsOK=true;

}

catch(IOException e){System.out.println(e);}

}//while paths

return fileWriter;

}//open files

public void createEncoding(){

String line;

try{

while(true){

line=fileReader.readLine();

if(line==null)break;

huffman.updateFrequencies(line);

}

fileReader.close();

huffman.createPQ();

huffman.createHuffmanTree();

huffman.calculateHuffmanCodes();

}//try

catch(IOException e){System.out.println(e);}

}//method create

public void saveEncodedMessage(){

String line;

try{

fileWriter.print(huffman.getCodes());

fileWriter.println("*******************");

fileReader=new BufferedReader(new FileReader(inFilePath));

while(true){

line=fileReader.readLine();

if(line==null)break;

fileWriter.println(huffman.getEncodedLine(line));

}//while

}//try

catch(IOException e){System.out.println(e);}

}//method

public static void main(String args[]){

PrintWriter writer=null;

try{

HuffmanTester tester=new HuffmanTester();

writer=tester.openFiles();

tester.createEncoding();

tester.saveEncodedMessage();

}

finally

{writer.close();}

}//main

}

Testing Huffman

Running program on command line:

c:\Program Files\Java\jdk1.6.0_03\bin>java HuffmanTester

please enter a path for the input file:

data2.txt

please enter a path for the output file:

output2.txt

c:\Program Files\Java\jdk1.6.0_03\bin>

data2.txt

HHHHHHHHHHHHHHHHHHH

AAAAAAAAAAAA

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

cccccccccccccccccccc

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

ddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd

eeeeeeeeeeee

fffffffffffffffffffffffffffffffff

ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg

ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg

gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg

The file output2.txt (coding & encryption for data2.txt)

101100

A 100110

H 101101

a 1000

b 1010

c 10010

d 11

e 100111

f 10111

g 0

*******************

101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101101100

100110100110100110100110100110100110100110100110100110100110100110100110101100

100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000101100

101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101100

1001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010101100

11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101100

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101100

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101100

100111100111100111100111100111100111100111100111100111100111100111100111101100

101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101100

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101100

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101100

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000101100