SHOW:
|
|
- or go back to the newest paste.
| 1 | import java.util.*; | |
| 2 | import java.io.*; | |
| 3 | ||
| 4 | class HuffmanNode implements Comparable<HuffmanNode>{
| |
| 5 | HuffmanNode right; | |
| 6 | HuffmanNode left; | |
| 7 | HuffmanNode parent; | |
| 8 | int count; | |
| 9 | String letter; | |
| 10 | ||
| 11 | public HuffmanNode(){}
| |
| 12 | ||
| 13 | public HuffmanNode (String letter, int count){
| |
| 14 | this.letter = letter; | |
| 15 | this.count = count; | |
| 16 | } | |
| 17 | public HuffmanNode (String letter, int count, HuffmanNode parent, HuffmanNode left, HuffmanNode right){
| |
| 18 | this.letter = letter; | |
| 19 | this.count = count; | |
| 20 | this.left = left; | |
| 21 | this.right = right; | |
| 22 | this.parent = parent; | |
| 23 | } | |
| 24 | ||
| 25 | public void setCount(int count){
| |
| 26 | this.count = count; | |
| 27 | } | |
| 28 | ||
| 29 | public int getCount(){
| |
| 30 | return count; | |
| 31 | } | |
| 32 | ||
| 33 | public void setRight(HuffmanNode right){
| |
| 34 | this.right = right; | |
| 35 | } | |
| 36 | ||
| 37 | public HuffmanNode getRight(HuffmanNode right){
| |
| 38 | return right; | |
| 39 | } | |
| 40 | ||
| 41 | public void setLeft(HuffmanNode left){
| |
| 42 | this.left = left; | |
| 43 | } | |
| 44 | ||
| 45 | public HuffmanNode getLeft(HuffmanNode left){
| |
| 46 | return left; | |
| 47 | } | |
| 48 | public void setParent(HuffmanNode right){
| |
| 49 | this.left = left; | |
| 50 | } | |
| 51 | public HuffmanNode getParent(HuffmanNode parent){
| |
| 52 | return parent; | |
| 53 | } | |
| 54 | ||
| 55 | public void buildTree(HuffmanNode node){
| |
| 56 | if (node.compareTo(this) <= 0 && left != null){
| |
| 57 | System.out.println(node.getCount() + ":" + this.count); | |
| 58 | left.buildTree(node); | |
| 59 | } | |
| 60 | else if (node.compareTo(this) <= 0 && left == null){
| |
| 61 | this.left = node; | |
| 62 | node.parent = this; | |
| 63 | } | |
| 64 | else if (node.compareTo(this) > 0 && right != null){
| |
| 65 | System.out.println(node.getCount() + ":" +this.count); | |
| 66 | right.buildTree(node); | |
| 67 | } | |
| 68 | else if (node.compareTo(this) > 0 && right == null){
| |
| 69 | this.right = node; | |
| 70 | node.parent = this; | |
| 71 | } | |
| 72 | } | |
| 73 | ||
| 74 | ||
| 75 | public int compareTo(HuffmanNode x){
| |
| 76 | return this.count - x.count; | |
| 77 | } | |
| 78 | public void genCode(String s){
| |
| 79 | if(left != null){
| |
| 80 | left.genCode(s + "0"); | |
| 81 | } | |
| 82 | if(right != null){
| |
| 83 | right.genCode(s + "1"); | |
| 84 | } | |
| 85 | if (left == null && right == null){
| |
| 86 | System.out.println(s); | |
| 87 | } | |
| 88 | } | |
| 89 | } | |
| 90 | ||
| 91 | public class hw4{
| |
| 92 | public static void main (String []args)throws IOException{
| |
| 93 | ||
| 94 | //ask user to enter file name | |
| 95 | System.out.printf("Enter a file location and name to encode [press Enter]: ");
| |
| 96 | Scanner input = new Scanner(System.in); | |
| 97 | - | z |
| 97 | + | |
| 98 | ||
| 99 | //Gets file name from Scanner and checks to see if valid | |
| 100 | - | Code: |
| 100 | + | |
| 101 | //if (!file.isFile()){
| |
| 102 | //System.out.printf("Enter a file location and name to encode [press Enter]: ");
| |
| 103 | //} | |
| 104 | Scanner text = new Scanner(file); | |
| 105 | ||
| 106 | String[] letters = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"};
| |
| 107 | int[] freq = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
| |
| 108 | ||
| 109 | String letter; | |
| 110 | String tempStr; | |
| 111 | int tempInt; | |
| 112 | ||
| 113 | while(text.hasNext()){
| |
| 114 | letter = text.next(); | |
| 115 | //System.out.printf("%s\n", letter);
| |
| 116 | ||
| 117 | char c = letter.charAt(0); | |
| 118 | int index = c - 97; | |
| 119 | freq[index]++; | |
| 120 | } | |
| 121 | ||
| 122 | for(int i=0; i <25; i++){
| |
| 123 | System.out.printf("%s:%d\n", letters[i], freq[i]);
| |
| 124 | } | |
| 125 | System.out.printf("\n");
| |
| 126 | ||
| 127 | for (int n=0; n <25; n++) {
| |
| 128 | for (int i=0; i <25; i++) {
| |
| 129 | if (freq[i] > freq[i+1]) {
| |
| 130 | // exchange elements | |
| 131 | tempInt = freq[i]; | |
| 132 | tempStr = letters[i]; | |
| 133 | freq[i] = freq[i+1]; | |
| 134 | letters[i] = letters[i+1]; | |
| 135 | freq[i+1] = tempInt; | |
| 136 | letters[i+1] = tempStr; | |
| 137 | } | |
| 138 | } | |
| 139 | } | |
| 140 | ||
| 141 | PriorityQueue<HuffmanNode> huffmanList = new PriorityQueue<HuffmanNode>(); | |
| 142 | ||
| 143 | for(int i=0; i <26; i++){
| |
| 144 | System.out.printf("%s:%d\n", letters[i], freq[i]);
| |
| 145 | if(freq[i] > 0){
| |
| 146 | huffmanList.add(new HuffmanNode(letters[i],freq[i])); | |
| 147 | } | |
| 148 | } | |
| 149 | ||
| 150 | HuffmanNode root = new HuffmanNode(); | |
| 151 | ||
| 152 | while(huffmanList.size() > 1){
| |
| 153 | HuffmanNode x = huffmanList.poll(); | |
| 154 | HuffmanNode y = huffmanList.poll(); | |
| 155 | HuffmanNode result = new HuffmanNode("-", x.getCount() + y.getCount(), null, x, y);
| |
| 156 | if(root == null){
| |
| 157 | root = result; | |
| 158 | } | |
| 159 | else{
| |
| 160 | root.buildTree(result); | |
| 161 | } | |
| 162 | huffmanList.add(result); | |
| 163 | } | |
| 164 | root.genCode(" ");
| |
| 165 | } | |
| 166 | } | |
| 167 | ||
| 168 | input file data: | |
| 169 | a | |
| 170 | a | |
| 171 | a | |
| 172 | a | |
| 173 | d | |
| 174 | d | |
| 175 | d | |
| 176 | d | |
| 177 | d | |
| 178 | d | |
| 179 | d | |
| 180 | d | |
| 181 | k | |
| 182 | k | |
| 183 | k | |
| 184 | k | |
| 185 | k | |
| 186 | k | |
| 187 | f | |
| 188 | f | |
| 189 | f | |
| 190 | f | |
| 191 | f | |
| 192 | f | |
| 193 | h | |
| 194 | h | |
| 195 | h | |
| 196 | h | |
| 197 | h | |
| 198 | h | |
| 199 | b | |
| 200 | b | |
| 201 | b | |
| 202 | b | |
| 203 | b | |
| 204 | b | |
| 205 | b | |
| 206 | b | |
| 207 | n | |
| 208 | n | |
| 209 | n | |
| 210 | n | |
| 211 | n | |
| 212 | n | |
| 213 | n | |
| 214 | e | |
| 215 | e | |
| 216 | e | |
| 217 | e | |
| 218 | e | |
| 219 | i | |
| 220 | i | |
| 221 | i | |
| 222 | i | |
| 223 | i | |
| 224 | i | |
| 225 | i | |
| 226 | i | |
| 227 | l | |
| 228 | k | |
| 229 | j | |
| 230 | a | |
| 231 | n | |
| 232 | s | |
| 233 | g | |
| 234 | l | |
| 235 | k | |
| 236 | j | |
| 237 | a | |
| 238 | s | |
| 239 | v | |
| 240 | o | |
| 241 | i | |
| 242 | j | |
| 243 | a | |
| 244 | s | |
| 245 | d | |
| 246 | l | |
| 247 | k | |
| 248 | g | |
| 249 | k | |
| 250 | n | |
| 251 | m | |
| 252 | a | |
| 253 | s | |
| 254 | d | |
| 255 | k | |
| 256 | l | |
| 257 | o | |
| 258 | v | |
| 259 | h | |
| 260 | a | |
| 261 | s | |
| 262 | d | |
| 263 | g | |
| 264 | z |