Saturday, 29 December 2012

Huffman-Encoding In Action

Curiosity regarding huffman-decoding process, force me to make one working huffman-encoding/decoding app.

What is Huffman-Encoding In Action ?

Huffman-Encoding In Action is a small GUI program which allows you to visualize how huffman encoding decoding works.

The actual work is done in a class that encapsulates all the functionality, so it should be easy to set up another GUI for it.


For those who don't know what is Huffman Coding read this 

How It Works 

Let q be the priority doubly linked list
l be the list

class Node
{
    Node left, right;
    char data;
    int freq;
    char lEW = ' ';
    char rEW = ' ';
    boolean isRoot = false;
}

Above code is a structure of a node


/**
     * start of the algorithm
     * characters are read'ed 1 by 1 and count is determined using variable count 
     * and a newrec of type node is created which has a data as = char and freq = count for eg:
     * x is the char which appears 3 times then newrec.data = x and newrec.freq = 3 and finally it is inserted 
     * into Sorted DLL and l contains the char x so that when x appear next we could identify that its freq is already
     * determined
     * the same process is repeated for all the char in the string or txt.
     * @param txt 
     */
    public void start( String txt ){
        ogtxt = txt;
        char[] toCharArray = txt.toCharArray();
        for (char x : toCharArray) {
            int count = 0;
            
            
            if( !(l.contains( String.valueOf( x ) ) ) ){
                for (char k : toCharArray) {
                    if( k == x )
                        count++;
                }
                Node newrec = new Node();
                newrec.freq = count;
                newrec.data = x;
                newrec.left = newrec.right = null;
                q.insert(newrec);
                l.add(String.valueOf( x ));
            }
           
        }

        makeSingleTree( );//a recursive function which makes single huffman tree. base case = when there will be only one record in our sorted doubly linked list.
        root = q.delete();// that single tree is now assigned to root
        root.isRoot = true;
         if(root.left != null & root.right != null){
            assignWeights( root );// assigns 0 to every left edge and 1 to every right edge
            traverse(root);//this will traverse and determine the huffman code for each letter or char.
        }else{
            onlyOneNode = true;
        }
        displayHuffmanCode();// this function will display the unique huffman code for each char.
       
    }
So, there you go, now you have basic idea about how the entire process works, the code is well formed in several different methods and is pretty easy to understand as well.

Speed

On my Desktop with with 2.8GHZ. Huffman-Encoder requires just a couple of ms to generate huffman code.

Download

you can download Huffman-Encoding In Action's latest version from here

Miscellaneous 

When given input such as OOOOOOO the encoder will show output Only1Node O 7.