-
Notifications
You must be signed in to change notification settings - Fork 85
Expand file tree
/
Copy pathhuffman_coding.java
More file actions
75 lines (61 loc) · 2.26 KB
/
huffman_coding.java
File metadata and controls
75 lines (61 loc) · 2.26 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class HuffmanCoding {
protected static Map<Character, String> result;
static class Node implements Comparable<Node> {
Node left;
Node right;
char data;
int count;
public Node(char data, int count, Node left, Node right) {
this.data = data;
this.count = count;
this.left = left;
this.right = right;
}
@Override
public int compareTo(Node node) {
return this.count < node.count ? -1 : 1;
}
}
public static void main (String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
System.out.print("\nEnter the string to be encoded: ");
String message = reader.readLine().trim();
reader.close();
Map<Character, Integer> frequencies = new HashMap<>();
for (char character : message.toCharArray())
frequencies.put(character, frequencies.getOrDefault(character, 0) + 1);
PriorityQueue<Node> queue = new PriorityQueue<>(frequencies.size());
for (Map.Entry<Character, Integer> pair : frequencies.entrySet())
queue.add(new Node(pair.getKey(), pair.getValue(), null, null));
while (queue.size() > 1) {
Node left = queue.poll();
Node right = queue.poll();
queue.add(new Node('$', left.count + right.count, left, right));
}
result = new HashMap<>();
preOrder(queue.poll(), "");
System.out.println("\nEncodings for each character:");
for (Map.Entry<Character, String> pair : result.entrySet())
System.out.println(pair.getKey() + ": " + pair.getValue());
StringBuilder answer = new StringBuilder("");
for (char character : message.toCharArray())
answer.append(result.get(character));
System.out.println("\nThe encoded message is: " + answer);
}
private static void preOrder(Node root, String prefix) {
if (root != null) {
if (root.data != '$') {
result.put(root.data, prefix);
return;
}
preOrder(root.left, prefix + "0");
preOrder(root.right, prefix + "1");
}
}
}