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 |