|
| 1 | + |
| 2 | +importjava.util.Comparator; |
| 3 | +importjava.util.Iterator; |
| 4 | +importjava.util.LinkedList; |
| 5 | +importjava.util.List; |
| 6 | +importjava.util.Scanner; |
| 7 | +importjava.util.Stack; |
| 8 | +/** |
| 9 | + * |
| 10 | + * @author Mayank Kumar (mk9440) |
| 11 | + */ |
| 12 | +/* |
| 13 | +Output : |
| 14 | +
|
| 15 | +Enter number of distinct letters |
| 16 | +6 |
| 17 | +Enter letters with its frequncy to encode |
| 18 | +Enter letter : a |
| 19 | +Enter frequncy : 45 |
| 20 | +
|
| 21 | +Enter letter : b |
| 22 | +Enter frequncy : 13 |
| 23 | +
|
| 24 | +Enter letter : c |
| 25 | +Enter frequncy : 12 |
| 26 | +
|
| 27 | +Enter letter : d |
| 28 | +Enter frequncy : 16 |
| 29 | +
|
| 30 | +Enter letter : e |
| 31 | +Enter frequncy : 9 |
| 32 | +
|
| 33 | +Enter letter : f |
| 34 | +Enter frequncy : 5 |
| 35 | +
|
| 36 | +LetterEncoded Form |
| 37 | +a0 |
| 38 | +b1 0 1 |
| 39 | +c1 0 0 |
| 40 | +d1 1 1 |
| 41 | +e1 1 0 1 |
| 42 | +f1 1 0 0 |
| 43 | +
|
| 44 | +*/ |
| 45 | + |
| 46 | +classNode{ |
| 47 | +Stringletr=""; |
| 48 | +intfreq=0,data=0; |
| 49 | +Nodeleft=null,right=null; |
| 50 | +} |
| 51 | + |
| 52 | +//A comparator class to sort list on the basis of their frequency |
| 53 | +classcompimplementsComparator<Node>{ |
| 54 | +@Override |
| 55 | +publicintcompare(Nodeo1,Nodeo2) { |
| 56 | +if(o1.freq>o2.freq){return1;} |
| 57 | +elseif(o1.freq<o2.freq){return -1;} |
| 58 | +else{return0;} |
| 59 | + } |
| 60 | +} |
| 61 | + |
| 62 | + |
| 63 | +publicclassHuffman { |
| 64 | + |
| 65 | +// A simple function to print a given list |
| 66 | +//I just made it for debugging |
| 67 | +publicstaticvoidprint_list(Listli){ |
| 68 | +Iterator<Node>it=li.iterator(); |
| 69 | +while(it.hasNext()){Noden=it.next();System.out.print(n.freq+" ");}System.out.println(); |
| 70 | + } |
| 71 | + |
| 72 | +//Function for making tree (Huffman Tree) |
| 73 | +publicstaticNodemake_huffmann_tree(Listli){ |
| 74 | +//Sorting list in increasing order of its letter frequency |
| 75 | +li.sort(newcomp()); |
| 76 | +Nodetemp=null; |
| 77 | +Iteratorit=li.iterator(); |
| 78 | +//System.out.println(li.size()); |
| 79 | +//Loop for making huffman tree till only single node remains in list |
| 80 | +while(true){ |
| 81 | +temp=newNode(); |
| 82 | +//a and b are Node which are to be combine to make its parent |
| 83 | +Nodea=newNode(),b=newNode(); |
| 84 | +a=null;b=null; |
| 85 | +//checking if list is eligible for combining or not |
| 86 | +//here first assignment of it.next in a will always be true as list till end will |
| 87 | +//must have atleast one node |
| 88 | +a=(Node)it.next(); |
| 89 | +//Below condition is to check either list has 2nd node or not to combine |
| 90 | +//If this condition will be false, then it means construction of huffman tree is completed |
| 91 | +if(it.hasNext()){b=(Node)it.next();} |
| 92 | +//Combining first two smallest nodes in list to make its parent whose frequncy |
| 93 | +//will be equals to sum of frequency of these two nodes |
| 94 | +if(b!=null){ |
| 95 | +temp.freq=a.freq+b.freq;a.data=0;b.data=1;//assigining 0 and 1 to left and right nodes |
| 96 | +temp.left=a;temp.right=b; |
| 97 | +//after combing, removing first two nodes in list which are already combined |
| 98 | +li.remove(0);//removes first element which is now combined -step1 |
| 99 | +li.remove(0);//removes 2nd element which comes on 1st position after deleting first in step1 |
| 100 | +li.add(temp);//adding new combined node to list |
| 101 | +//print_list(li); //For visualizing each combination step |
| 102 | + } |
| 103 | +//Sorting after combining to again repeat above on sorted frequency list |
| 104 | +li.sort(newcomp()); |
| 105 | +it=li.iterator();//resetting list pointer to first node (head/root of tree) |
| 106 | +if(li.size()==1){return (Node)it.next();}//base condition ,returning root of huffman tree |
| 107 | + } |
| 108 | +} |
| 109 | + |
| 110 | +//Function for finding path between root and given letter ch |
| 111 | +publicstaticvoiddfs(Noden,Stringch){ |
| 112 | +Stack<Node>st=newStack();// stack for storing path |
| 113 | +intfreq=n.freq;// recording root freq to avoid it adding in path encoding |
| 114 | +find_path_and_encode(st,n,ch,freq); |
| 115 | + } |
| 116 | + |
| 117 | +//A simple utility function to print stack (Used for printing path) |
| 118 | +publicstaticvoidprint_path(Stack<Node>st){ |
| 119 | +for(inti=0;i<st.size();i++){ |
| 120 | +System.out.print(st.elementAt(i).data+" "); |
| 121 | + } |
| 122 | + } |
| 123 | + |
| 124 | +publicstaticvoidfind_path_and_encode(Stack<Node>st,Noderoot,Strings,intf){ |
| 125 | +//Base condition |
| 126 | +if(root!=null){ |
| 127 | +if(root.freq!=f){st.push(root);}// avoiding root to add in path/encoding bits |
| 128 | +if(root.letr.equals(s)){print_path(st);return;}// Recursion stopping condition when path gets founded |
| 129 | +find_path_and_encode(st,root.left,s,f); |
| 130 | +find_path_and_encode(st,root.right,s,f); |
| 131 | +//Popping if path not found in right or left of this node,because we previously |
| 132 | +//pushed this node in taking a mindset that it might be in path |
| 133 | +st.pop(); |
| 134 | + } |
| 135 | + } |
| 136 | + |
| 137 | +publicstaticvoidmain(Stringargs[]){ |
| 138 | +List <Node>li=newLinkedList<>(); |
| 139 | +Scannerin=newScanner(System.in); |
| 140 | +System.out.println("Enter number of distinct letters "); |
| 141 | +intn=in.nextInt(); |
| 142 | +Strings[]=newString[n]; |
| 143 | +System.out.print("Enter letters with its frequncy to encode\n"); |
| 144 | +for(inti=0;i<n;i++){ |
| 145 | +Nodea=newNode(); |
| 146 | +System.out.print("Enter letter : "); |
| 147 | +a.letr=in.next();s[i]=a.letr; |
| 148 | +System.out.print("Enter frequncy : "); |
| 149 | +a.freq=in.nextInt();System.out.println(); |
| 150 | +li.add(a); |
| 151 | + } |
| 152 | +Noderoot=newNode(); |
| 153 | +root=make_huffmann_tree(li); |
| 154 | +System.out.println("Letter\t\tEncoded Form"); |
| 155 | +for(inti=0;i<n;i++){ |
| 156 | +System.out.print(s[i]+"\t\t");dfs(root,s[i]);System.out.println();} |
| 157 | + } |
| 158 | +} |
