Code:
import java.util.*;
class Element {
public
String info;
public
int frequency;
Element(){}
Element(String
str){
info
= str;
frequency
= 1;
}
Element(char
ch){
info
= Character.toString(ch);
frequency
= 1;
}
public
String toString(){
return
info;
}
}
class Node {
public
Element data;
public
Node left;
public
Node right;
Node(Element
d){
data
= d;
left
= right = null;
}
}
class HoffmannEncoding {
/*static
Element[] randomize(Element e[],int n){
Random
rgen = new Random();
Element
el[] = new Element[n];
for(int
i =0;i<n;i++)
el[i]
= e[i];
for(int
i=0;i<el.length;i++){
int
randomPosition = rgen.nextInt(el.length);
Element temp =
el[i];
el[i] =
el[randomPosition];
el[randomPosition] = temp;
}
return
el;
}*/
static
Element[] sort(Element e[],int n){
Element
el[] = new Element[n];
/*This
stuff is creating problems...I just need to shuffle the elements with minimum
frequency and same
//Randomizing
Algorithm
Random
rgen = new Random();
Boolean
flags[] = new Boolean[n];
for(int
i =0;i<n;i++)
flags[i]
= false;
for(int
i =0;i<n;i++){
int
no = rgen.nextInt(n);
if(!flags[no]){
System.out.println("Transferred
"+el[i]+" <- "+e[no]);
el[i]
= e[no];
System.out.println("Transferring
el["+i+"] <- e["+no+"]");
flags[no]
= true;
}
else
i--;
}
System.out.println();
*/
for(int
i=0;i<n;i++){ //Simple array copy
el[i]
= e[i];
}
//Sorting
Algorithm
for(int
i=0;i<n;i++){
for(int
j=0;j<n-i-1;j++){
if(el[j].frequency
< el[j+1].frequency){
Element
temp = el[j];
el[j]
= el[j+1];
el[j+1]
= temp;
}
}
}
return
el;
}
static
void display(Node root){
Node
temp = root;
if(temp==null)
return;
display(temp.left);
System.out.println(temp.data.info);
display(temp.right);
}
public
static String code(String str,Node root){
Node
temp = root;
String
hfcode = "";
try{
while(temp!=null){
while(temp.left.data.info.indexOf(str)!=-1
&& temp.left!=null){
temp
= temp.left;
hfcode
= hfcode + "0";
}
while(temp.right.data.info.indexOf(str)!=-1
&& temp.right!=null){
temp
= temp.right;
hfcode
= hfcode + "1";
}
if(temp.data.info.equals(str))
break;
}
}catch(Exception
e){}
return
hfcode;
}
public
static void main(String args[]){
Boolean
same = false;
int
i,j;
Scanner
s = new Scanner(System.in);
System.out.print("Enter
the string : ");
String
str = s.nextLine();
System.out.println(str);
//Calculating
Frequencies
Element
el[] = new Element[str.length()];
el[0]
= new Element(str.charAt(0));
for(j
= 1,i = 1;i<str.length();i++){
char
ch = str.charAt(i);
for(int
k = 0;k<str.length() && el[k]!=null;k++){
same
=false;
if(el[k].info.equals(Character.toString(ch))){
el[k].frequency++;
same
= true;
break;
}
}
if(!same){
el[j++]
= new Element(ch);
}
}
System.out.println("Character\tFrequency");
Element
comparisons[][] = new Element[j][j];
for(i=0;i<j;i++)
System.out.println(el[i].info+"\t\t"+el[i].frequency);
//Calculated
Frequencies
//Creating
Nodes --- start
comparisons[0]
= sort(el,j);
//try{
for(i
= 1;i<j+1;i++){
comparisons[i]
= sort(comparisons[i-1],j-i);
//I
guess I can shuffle up something over here...
int
l=j-i;
while(comparisons[i-1][l-1].frequency
== comparisons[i-1][l].frequency && l>=0)
l--;
System.out.println("l="+l);
for(int
f=l,b=j-i;f<b;f++,b--){
Element temp =
comparisons[i-1][f];
comparisons[i-1][f]
= comparisons[i-1][b];
comparisons[i-1][b]
= temp;
}
int
totalFreq = comparisons[i-1][j-i-1].frequency +
comparisons[i-1][j-i].frequency;
comparisons[i][j-i-1]
= new Element(comparisons[i-1][j-i-1].info + comparisons[i-1][j-i].info);
comparisons[i][j-i-1].frequency
= totalFreq;
}//}catch(Exception
e){System.out.println(e);}
System.out.println("Creating
Nodes...");
//Displaying
the Comparison Array
for(i=0;i<j;i++){
for(int
k=0;k<j-i;k++)
System.out.println(comparisons[i][k].info+"\t\t"+comparisons[i][k].frequency);
System.out.println("\n***\n");
}
//Created
Nodes --- end
//Building
Tree
Node
root = new Node(comparisons[j-1][0]);
Node
temp = root;
for(i=j-2;i>=0;i--){
for(int
k = 0;k<j-i-1;k++){
temp.left
= new Node(comparisons[i][k]);
temp.right
= new Node(comparisons[i][k+1]);
}
temp
= temp.right;
}
System.out.println("Inorder
Traversal of the Binary Tree");
display(root);
//Builded
the Tree
//Calculating
Codes
System.out.println("Character\tCode");
for(i=0;i<j;i++)
System.out.println(comparisons[0][i]+"\t\t\t"+code(comparisons[0][i].info,root));
//Completed...
}
}
OUTPUT:
Enter the
string : structure
structure
Character Frequency
s 1
t 2
r 2
u 2
c 1
e 1
Creating
Nodes...
t 2
r 2
u 2
s 1
c 1
e 1
***
t 2
r 2
u 2
s 1
ce 2
***
t 2
r 2
u 2
sce 3
***
t 2
r 2
usce 5
***
t 2
rusce 7
***
trusce 9
***
Inorder
Traversal of the Binary Tree
t
trusce
r
rusce
u
usce
s
sce
c
ce
e
Character Code
t 0
r 10
u 110
s 1110
c 11110
e 11111
Need
the code??
No comments:
Post a Comment