huffman coding in java

[ayanbizz]

I am trying to implement huffman coding scheme in java.But I am facing problems in building the huffman tree.How to proceed ?Is there any datastructure in java that will help me to do it?Please help!!

[thekashyap]

Can you post your code and point to where the problem is?
Or is it that you don't understand Huffman coding?

[ayanbizz]

@thekashyap till now I have been able to read the frequency of characters in a text file and stored them in a hash-map.But now , I have to arrange them according to their frequency and build a binary tree from it.Here's where I am stuck.Please give me some ideas..Also ,what to do when 2 characters have same frequency?

[jwenting]

There are standard tree structures in the Collections API.
If those aren't sufficient, you can always build your own.

[thekashyap]

@thekashyap till now I have been able to read the frequency of characters in a text file and stored them in a hash-map.But now , I have to arrange them according to their frequency and build a binary tree from it.Here's where I am stuck.Please give me some ideas..Also ,what to do when 2 characters have same frequency?

Again, can you please post your code and indicate where are you stuck?

[ayanbizz]

@thekashyap I think I was not precise with my question.Till now I don't have any problem with the coding .Rather,I was seeking some ideas on how to start building the tree from the hash-map.Like ,is there any datastructure in java which I could use?

[thekashyap]

As jwenting said there is no built-in tree in java (upto 1.5) I understand in 1.6 there were some talks of it, but donno; check the rel notes. There were also some threads saying there is some XXXNode class in awt or swing that can be mis-used if you want to create your own tree impl.
But you'll get decent enough generic tree impls on www. Here is one.
About the algorithm itself, it seems quite simple from teh description available here. PS It recommends using priority Q (instead of your HashMap). In one sentence, you build a binary tree, where the comparator should compare the probability / frequency. Only catch being the "internal nodes" that you need to create.
If you still have problems get back.

[ayanbizz]

thanx...

[thekashyap]

Do close the thread if you have no more questions..

[ayanbizz]

Here's what I did..created an abstract Node class and extended it in Leaf and NLeaf class(non-leaf).And the inserted the nodes in TreeSet.So,I was succesful in creating the nodes and sort them but now I'm again stuck with the encoding portion.I was trying to pop the top 2 nodes from treeset and encode them.but by doing so, the top 2 nodes will get 0 and 1 and so on...but it should be like ,the root getting 0 and so on..What shall i do.I'm posting some portions of the code here..
Node class

abstract class Node implements Comparable<Node>{  
String code="";  
int ascii;  
int seq;  
int fq,x,y;  

public Node(int fq,int ascii,int seq)  
{this.fq=fq;  
this.ascii=ascii;  
this.seq=seq;  
}  
public int compareTo(Node n)  
{  
    int x=this.fq-n.fq;  
    if (x!=0)  
    return x;  
    else{  
    y=this.seq-n.seq;  
    return y;  
    }  
}  
abstract void enCode(String s);  
}  

Leaf class ...

class Leaf extends Node{  
public Leaf(int fq,int ascii,int seq){    
super(fq, ascii,seq);     
}  
void enCode(String s)  
{  
    code.concat(s);}  
}  

Nleaf class ....

class NLeaf extends Node{  
Node left;  
Node right;  
public NLeaf(Node l,Node r,int seq)  
{super(l.fq+r.fq,l.ascii+r.ascii,seq);  
left=l;  
right=r;  
left.enCode("0");  
right.enCode("1");  
}  
void enCode(String s)  
{  
    code.concat(s);}  
}  

part of the main class ....

 TreeSet <Node> ts=new TreeSet<Node>();  
  int s=0;  
  for(int i:m.keySet())  
  {   s++;        
      Leaf l=new Leaf(m.get(i),i,s);  
      ts.add(l);  
  }  
    for(Node elt:ts)  
    System.out.println("frequency=="+elt.fq+"ascii val"+(char)elt.ascii);  
    do{  
        Node left=ts.first();  
        ts.remove(left);  
        Node right=ts.first();  
        ts.remove(right);  
        s++;  
        NLeaf nl=new NLeaf(left,right,s);  
        ts.add(nl);  

    }while(((int)ts.size())>1);

[ayanbizz]

Somebody please help me out..

[thekashyap]

Can you post full code?

[c.uetn]

How about managed to finish the implementation, if so you can post the code here ..! thanks ...!!

[stultuske]

why re-opening a dormant thread? if you have any questions about this, you could easily have started a new thread.

also, it's against forum rules to just hand out custom code. have you or are you currently working on a similar project? if so, and you're having trouble with it, just ask specific questions with relevant snippets of code, don't just ask for a custom-fit solution

[Ezzaral]

Agreed. Thread closed.