My Huffman compression program is supposed to be able to compress any type of file. Thats why I'm using a FileInputStream to read bytes from file instead of characters.
Step 1. The frequency table that is created is an array with integers.
/**
* Initialises field frequencyTable.
* Opens file, reads one byte at a time and counts each bytes frequency.
* @param file the file to be read.
*
*/
private void buildFrequencyTable(String file){
//since we are reading one byte at a time there are 256 possible values.
this.frequencyTable = new int[256];
try{
FileInputStream in = new FileInputStream(file);
int currentByte;
while((currentByte = in.read())!=-1){
//add that byte to frequencyTable and increment it.
this.frequencyTable[currentByte] ++;
}
}catch (IOException e){
e.printStackTrace();
}
}
Step 2: I create the huffman tree.
this.pq is a priorityqueue. All the objects in pq are Nodes that is created for each unique byte. Each node has an integer value that represents the byte. And another integer value that represents the frequency for that byte. The Nodes are comparable to their frequency so that when building the huffman tree, the byte with the highest frequency gets encoded using fewer bits etc.
Node class:
class Node implements Comparable<Node>{
private int value;
private int frequency;
private Node left_child;
private Node right_child;
Node(int value, int frequency, Node left_child, Node right_child){
this.value = value;
this.frequency = frequency;
this.left_child = left_child;
this.right_child = right_child;
}
//Checks if two nodes have equal frequency.
private boolean equals(Node n){
return this.frequency == n.frequency;
}
@Override
public int compareTo(Node other) {
if(this.equals(other)){
return 0;
}else if(this.frequency > other.frequency){
return 1;
}else return -1;
}
Huffman tree builder method:
private void createHuffmanTree(){
while(this.pq.size() > 1){
Node left = this.pq.poll();
Node right = this.pq.poll();
//null character means its not a leaf node.
Node parent = new Node('\0',left.getFrequency()+right.getFrequency(), left, right);
this.pq.add(parent);
}
//The last item in priority queue will be the final huffman tree node.
this.huffmanTree = this.pq.poll();
}
MY PROBLEM:
Step 3. do the compression.
So now I have a Huffman tree ready to be used for creating an encoded version of the original file. But I don't understand this step.
If i create a hashMap that maps each byte to its huffman bit-encoding. Do I put the encoding as a string in the map?
And if so, If I create a method called Compress(). And I read once again the original file one byte at a time. How would I be able to use this hashMap to : 1. find the key value that is the currentbyte from file, 2. find its corresponding bit-encoding (that is a string) and write those individual bits to another file that is the compressed version?.
eg. I have the byte 65 (A) and it has the encoding "11". then the compress method would output: 11 11 11 (with extra padding)
NOTE! I've been given some code that implements a class called: BitFileReader. This class reads a file and can read one bit at a time. Though I don't know how to use this class in my program.
equals
smells. Are you sure, you do not want to havethis.value
compared ? Similar forcompareTo
, I can understand, that it is not important highlevel, but my preference is to have deterministic result, in your case it might be different every run, kind of... - Betlistabyte[]
,BitSet
(my favourite) or maybelong
(max 64 bits). The BitFileWriter should be similar to the existing BitFileReader:int readBit()
would hint at awriteBit(int)
. - Joop Eggen