8000 Huffman Coding · harshspandey1/DSA-Bootcamp-Java@d150c48 · GitHub
[go: up one dir, main page]
Skip to content

Commit d150c48

Browse files
kunal-kushwahakunal-kushwaha
authored
Huffman Coding
1 parent eca087e commit d150c48

File tree

4 files changed

+213
-0
lines changed

4 files changed

+213
-0
lines changed

‎lectures/27-huffman-coding/code/Heap.java

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
import java.util.ArrayList;
2+
3+
public class Heap<T extends Comparable<T>>{
4+
5+
private ArrayList<T> list;
6+
7+
public Heap(){
8+
list = new ArrayList<>();
9+
}
10+
11+
public void insert(T value){
12+
list.add(value);
13+
upheap(list.size() - 1);
14+
}
15+
public int size(){
16+
return list.size();
17+
}
18+
private void upheap(int index){
19+
20+
if(index == 0){
21+
return;
22+
}
23+
24+
int p = parent(index);
25+
26+
if(list.get(index).compareTo(list.get(p)) < 0){
27+
swap(index, p);
28+
upheap(p);
29+
}
30+
}
31+
32+
public T remove() throws Exception{
33+
if(list.isEmpty()){
34+
throw new Exception("Removing from empty Heap");
35+
}
36+
T temp = list.get(0);
37+
38+
T last = list.remove(list.size() - 1);
39+
40+
if(!list.isEmpty()){
41+
list.set(0, last);
42+
43+
downheap(0);
44+
}
45+
return temp;
46+
}
47+
48+
private void downheap(int index) {
49+
50+
int min = index;
51+
int left = left(index);
52+
int right = right(index);
53+
54+
// check is left < min
55+
if(left < list.size() && list.get(min).compareTo(list.get(left)) > 0){
56+
min = left;
57+
}
58+
// check if right < min
59+
if(right < list.size() && list.get(min).compareTo(list.get(right)) > 0){
60+
min = right;
61+
}
62+
63+
if(min != index){
64+
swap(min, index);
65+
66+
downheap(min);
67+
}
68+
}
69+
70+
private void swap(int first, int second) {
71+
T temp = list.get(first);
72+
list.set(first, list.get(second));
73+
list.set(second, temp);
74+
}
75+
76+
private int parent(int index){
77+
return (index - 1) / 2;
78+
}
79+
80+
private int left(int index){
81+
return index * 2 + 1;
82+
}
83+
84+
private int right(int index){
85+
return index * 2 + 2;
86+
}
87+
88+
public ArrayList<T> heapSort() throws Exception {
89+
90+
ArrayList<T> data = new ArrayList<>();
91+
92+
while(!list.isEmpty()){
93+
data.add(this.remove());
94+
}
95+
return data;
96+
}
97+
98+
}

‎lectures/27-huffman-coding/code/HuffmanCoder.java

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
import java.util.*;
2+
3+
class HuffmanCoder {
4+
HashMap<Character, String> encoder;
5+
HashMap<String, Character> decoder;
6+
7+
private class Node implements Comparable<Node> {
8+
Character data;
9+
int cost; // frequency
10+
Node left;
11+
Node right;
12+
13+
public Node(Character data, int cost) {
14+
this.data = data;
15+
this.cost = cost;
16+
this.left = null;
17+
this.right = null;
18+
}
19+
20+
@Override
21+
public int compareTo(Node other) {
22+
return this.cost - other.cost;
23+
}
24+
}
25+
26+
public HuffmanCoder(String feeder) throws Exception {
27+
HashMap<Character, Integer> fmap = new HashMap<>();
28+
29+
for(int i=0; i < feeder.length(); i++) {
30+
char cc = feeder.charAt(i);
31+
if(fmap.containsKey(cc)) {
32+
int ov = fmap.get(cc);
33+
ov += 1;
34+
fmap.put(cc, ov);
35+
} else {
36+
fmap.put(cc, 1);
37+
}
38+
}
39+
40+
Heap<Node> minHeap = new Heap<>();
41+
Set<Map.Entry<Character, Integer>> entrySet = fmap.entrySet();
42+
43+
for(Map.Entry<Character, Integer> entry : entrySet) {
44+
Node node = new Node(entry.getKey(), entry.getValue());
45+
minHeap.insert(node);
46+
}
47+
48+
while(minHeap.size() != 1) {
49+
Node first = minHeap.remove();
50+
Node second = minHeap.remove();
51+
52+
Node newNode = new Node('\0', first.cost + second.cost);
53+
newNode.left = first;
54+
newNode.right = second;
55+
56+
minHeap.insert(newNode);
57+
}
58+
59+
Node ft = minHeap.remove();
60+
61+
this.encoder = new HashMap<>();
62+
this.decoder = new HashMap<>();
63+
64+
this.initEncoderDecoder(ft, "");
65+
}
66+
67+
private void initEncoderDecoder(Node node, String osf) {
68+
if(node == null) {
69+
return;
70+
}
71+
if(node.left == null && node.right == null) {
72+
this.encoder.put(node.data, osf);
73+
this.decoder.put(osf, node.data);
74+
}
75+
initEncoderDecoder(node.left, osf+"0");
76+
initEncoderDecoder(node.right, osf+"1");
77+
}
78+
79+
public String encode(String source) {
80+
String ans = "";
81+
82+
// Bitset can be used: like an array but with a bit at each index
83+
84+
for(int i=0; i<source.length(); i++) {
85+
ans = ans + encoder.get(source.charAt(i));
86+
}
87+
88+
return ans;
89+
}
90+
91+
public String decode(String codedString) {
92+
String key = "";
93+
String ans = "";
94+
for(int i=0; i<codedString.length(); i++) {
95+
key = key + codedString.charAt(i);
96+
if(decoder.containsKey(key)) {
97+
ans = ans + decoder.get(key);
98+
key = "";
99+
}
100+
}
101+
return ans;
102+
}
103+
}

‎lectures/27-huffman-coding/code/Main.java

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
class Main {
2+
public static void main(String[] args) throws Exception{
3+
String str = "abbccda";
4+
HuffmanCoder hf = new HuffmanCoder(str);
5+
String cs = hf.encode(str);
6+
System.out.println(cs);
7+
String dc = hf.decode(cs);
8+
System.out.println(dc);
9+
10+
11+
}
12+
}

‎lectures/27-huffman-coding/notes/HuffmanEncoding.pdf

999 KB
Binary file not shown.

0 commit comments

Comments
 (0)
0