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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
import java.util.*;
import java.io.*;
public class HuffmanCode {
public HuffmanNode root;
// Constructor that builds the Huffman tree from an array of frequencies
public HuffmanCode(int[] frequencies) {
Queue<HuffmanNode> nodes = new PriorityQueue<>();
for (int i = 0; i < frequencies.length; i++) {
if (frequencies[i] > 0) {
nodes.add(new HuffmanNode((char) i, frequencies[i]));
}
}
while (nodes.size() > 1) {
HuffmanNode left = nodes.remove();
HuffmanNode right = nodes.remove();
HuffmanNode branch = new HuffmanNode('\0', left.freq + right.freq, left, right);
nodes.add(branch);
}
this.root = nodes.isEmpty() ? null : nodes.remove();
}
// Constructor that reads the Huffman tree from a Scanner
public HuffmanCode(Scanner input) {
this.root = new HuffmanNode('\0', 0); // Initialize root with a dummy node
while (input.hasNextLine()) {
int character = Integer.parseInt(input.nextLine());
String path = input.nextLine();
addNode(character, path);
}
}
// Adds a node to the Huffman tree based on the given path
private void addNode(int character, String path) {
HuffmanNode current = root;
for (int i = 0; i < path.length(); i++) {
char direction = path.charAt(i);
if (direction == '0') {
if (current.left == null) {
if (i == path.length() - 1) {
current.left = new HuffmanNode((char) character, 1); // Final node
} else {
current.left = new HuffmanNode('\0', 0); // Create a dummy node if it doesn't exist
}
}
current = current.left;
} else if (direction == '1') {
if (current.right == null) {
if (i == path.length() - 1) {
current.right = new HuffmanNode((char) character, 1); // Final node
} else {
current.right = new HuffmanNode('\0', 0); // Create a dummy node if it doesn't exist
}
}
current = current.right;
}
}
}
// Saves the Huffman tree to the given output stream in standard format
public void save(PrintStream output) {
save(output, this.root, "");
}
private void save(PrintStream output, HuffmanNode head, String path) {
if (head != null) {
if (head.data != '\0') {
output.println((int) head.data);
output.println(path);
}
save(output, head.left, path + "0");
save(output, head.right, path + "1");
}
}
// Translates bits from the input stream to characters and writes them to the output stream
public void translate(BitInputStream input, PrintStream output) {
HuffmanNode current = root;
while (input.hasNextBit()) {
int bit = input.nextBit();
if (bit == 0) {
current = current.left;
} else {
current = current.right;
}
if (current.left == null && current.right == null) { // Leaf node
output.print(current.data);
current = root; // Restart for next character
}
}
}
// Inner class representing a node in the Huffman tree
private static class HuffmanNode implements Comparable<HuffmanNode> {
public char data;
public int freq;
public HuffmanNode left;
public HuffmanNode right;
public HuffmanNode(char data, int frequency) {
this(data, frequency, null, null);
}
public HuffmanNode(char data, int frequency, HuffmanNode left, HuffmanNode right) {
this.data = data;
this.freq = frequency;
this.left = left;
this.right = right;
}
public int compareTo(HuffmanNode other) {
return Integer.compare(this.freq, other.freq);
}
}
}
|
