-
Notifications
You must be signed in to change notification settings - Fork 77
/
Huffman_Decoding.java
153 lines (112 loc) · 3.75 KB
/
Huffman_Decoding.java
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
import java.util.*;
abstract class Node implements Comparable<Node> {
public int frequency; // the frequency of this tree
public char data;
public Node left, right;
public Node(int freq) {
frequency = freq;
}
// compares on the frequency
public int compareTo(Node tree) {
return frequency - tree.frequency;
}
}
class HuffmanLeaf extends Node {
public HuffmanLeaf(int freq, char val) {
super(freq);
data = val;
}
}
class HuffmanNode extends Node {
public HuffmanNode(Node l, Node r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}
}
class Decoding {
/*
class Node
public int frequency; // the frequency of this tree
public char data;
public Node left, right;
*/
void decode(String S ,Node root)
{
String myString = "";
Node tmp = root;
for (int i = 0; i <= S.length(); i++){
if(tmp.right == null && tmp.left == null){
myString += tmp.data;
tmp = root;
i--;
}
else if (i < S.length())
tmp = S.charAt(i) == '1' ? tmp.right : tmp.left;
}
System.out.println(myString);
}
}
public class Solution {
// input is an array of frequencies, indexed by character code
public static Node buildTree(int[] charFreqs) {
PriorityQueue<Node> trees = new PriorityQueue<Node>();
// initially, we have a forest of leaves
// one for each non-empty character
for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));
assert trees.size() > 0;
// loop until there is only one tree left
while (trees.size() > 1) {
// two trees with least frequency
Node a = trees.poll();
Node b = trees.poll();
// put into new node and re-insert into queue
trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}
public static Map<Character,String> mapA=new HashMap<Character ,String>();
public static void printCodes(Node tree, StringBuffer prefix) {
assert tree != null;
if (tree instanceof HuffmanLeaf) {
HuffmanLeaf leaf = (HuffmanLeaf)tree;
// print out character, frequency, and code for this leaf (which is just the prefix)
//System.out.println(leaf.data + "\t" + leaf.frequency + "\t" + prefix);
mapA.put(leaf.data,prefix.toString());
} else if (tree instanceof HuffmanNode) {
HuffmanNode node = (HuffmanNode)tree;
// traverse left
prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);
// traverse right
prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String test= input.next();
// we will assume that all our characters will have
// code less than 256, for simplicity
int[] charFreqs = new int[256];
// read each character and record the frequencies
for (char c : test.toCharArray())
charFreqs[c]++;
// build tree
Node tree = buildTree(charFreqs);
// print out results
printCodes(tree, new StringBuffer());
StringBuffer s = new StringBuffer();
for(int i = 0; i < test.length(); i++) {
char c = test.charAt(i);
s.append(mapA.get(c));
}
//System.out.println(s);
Decoding d = new Decoding();
d.decode(s.toString(), tree);
}
}