1
votes

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.

1
The output of Huffman encoding is generally a bit stream. It sounds like your BitWriter class handles this, but without seeing details, it's difficult to say. - Oliver Charlesworth
Very likely not related, but your equals smells. Are you sure, you do not want to have this.value compared ? Similar for compareTo, 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... - Betlista
I meant I've been given a class called BitFileReader. Im supposed to implement the writer myself. I can include the code if that would help?@OliverCharlesworth - Fanny
For an encoding one would need (1) the number of bits, and (2) something to contain the bits, byte[], BitSet (my favourite) or maybe long (max 64 bits). The BitFileWriter should be similar to the existing BitFileReader: int readBit() would hint at a writeBit(int). - Joop Eggen
maby you could give me lika a pseudo-code example? @JoopEggen - Fanny

1 Answers

1
votes

Pseudo-code (very)

void convert(InputStream in, BitFileWriter out) {
    HuffmanTree huffman = new HuffmanTree()
    int b;
    while ((b = in.read()) != -1) {
        huffman.add(b);
        Bits bits = huffman.get(b);
        for (int bit : bits.values()) {
             out.writeBit(bit);
        }
    }
    out.close();
}

Bits could be simply int[]. Or using BitSet:

class Bits {
    final BitSet bitset;
    final int nbits;

    Bits(BitSet bitset, int nbits) {
        this.bitset = bitset;
        this.nbits = nbits;
    }

    int[] values() {
        int[] v = new int[nbits];
        for (int i = bitset.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) {
            v[i] = 1;
        }
        return v;
    }
}