Skip to content

Commit 9ad263f

Browse files
author
Christian Bender
authored
Merge pull request TheAlgorithms#136 from shikhart98/master
Add Compression Algorithm
2 parents f480b5b + c0c72ca commit 9ad263f

9 files changed

+240
-0
lines changed

‎Compression/bin/HEncoder$Node$Nodecomparator.class

859 Bytes
Binary file not shown.

‎Compression/bin/HEncoder$Node.class

683 Bytes
Binary file not shown.

‎Compression/bin/HEncoder.class

3.59 KB
Binary file not shown.

‎Compression/bin/compressclient.class

756 Bytes
Binary file not shown.

‎Compression/bin/genericheap.class

2.79 KB
Binary file not shown.

‎Compression/src/HEncoder.java

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
import java.util.ArrayList;
2+
import java.util.Comparator;
3+
import java.util.HashMap;
4+
5+
public class HEncoder {
6+
7+
public HashMap<Character, String> encoder = new HashMap<>(); // in order to encode
8+
public HashMap<String, Character> decoder = new HashMap<>(); // in order to decode
9+
10+
private static class Node {
11+
12+
Character ch;
13+
Integer freq;
14+
Node left;
15+
Node right;
16+
17+
public static final Nodecomparator Ctor = new Nodecomparator();
18+
19+
public static class Nodecomparator implements Comparator<Node> {
20+
21+
@Override
22+
public int compare(Node o1, Node o2) {
23+
return o2.freq - o1.freq;
24+
}
25+
26+
}
27+
}
28+
29+
public HEncoder(String feeder) {
30+
// 1. freq map
31+
HashMap<Character, Integer> freqmap = new HashMap<>();
32+
for (int i = 0; i < feeder.length(); ++i) {
33+
char ch = feeder.charAt(i);
34+
if (freqmap.containsKey(ch)) {
35+
freqmap.put(ch, freqmap.get(ch) + 1);
36+
} else {
37+
freqmap.put(ch, 1);
38+
}
39+
}
40+
41+
// 2. prepare the heap from keyset
42+
genericheap<Node> heap = new genericheap<Node>(Node.Ctor);
43+
ArrayList<Character> k = new ArrayList<>(freqmap.keySet());
44+
for (Character c : k) {
45+
Node n = new Node();
46+
n.ch = c;
47+
n.left = null;
48+
n.right = null;
49+
n.freq = freqmap.get(c);
50+
heap.add(n);
51+
}
52+
53+
// 3.Prepare tree, remove two , merge, add it back
54+
Node fn = new Node();
55+
while (heap.size() != 1) {
56+
Node n1 = heap.removeHP();
57+
Node n2 = heap.removeHP();
58+
fn = new Node();
59+
60+
fn.freq = n1.freq + n2.freq;
61+
fn.left = n1;
62+
fn.right = n2;
63+
64+
heap.add(fn);
65+
}
66+
67+
// 4. traverse
68+
69+
traverse(heap.removeHP(), "");
70+
}
71+
72+
private void traverse(Node node, String osf) {
73+
74+
if (node.left == null && node.right == null) {
75+
encoder.put(node.ch, osf);
76+
decoder.put(osf, node.ch);
77+
return;
78+
}
79+
traverse(node.left, osf + "0");
80+
traverse(node.right, osf + "1");
81+
82+
}
83+
84+
// compression work done here
85+
public String compress(String str) {
86+
String rv = "";
87+
for (int i = 0; i < str.length(); ++i) {
88+
rv += encoder.get(str.charAt(i));
89+
}
90+
return rv;
91+
}
92+
93+
94+
//in order to decompress
95+
public String decompress(String str) {
96+
String s = "";
97+
String code = "";
98+
for (int i = 0; i < str.length(); ++i) {
99+
code += str.charAt(i);
100+
if (decoder.containsKey(code)) {
101+
s += decoder.get(code);
102+
code = "";
103+
}
104+
}
105+
106+
return s;
107+
}
108+
}

‎Compression/src/compressclient.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
2+
public class compressclient {
3+
4+
public static void main(String[] args) {
5+
6+
HEncoder h= new HEncoder("aaaabbbcccccccccccdddd");
7+
System.out.println(h.compress("aabccd"));
8+
System.out.println(h.decompress("101011000111"));
9+
}
10+
11+
}

‎Compression/src/genericheap.java

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
2+
3+
import java.util.ArrayList;
4+
import java.util.Comparator;
5+
6+
public class genericheap<T> { // create a generic heap class <T> , where T can be of any type.
7+
8+
private ArrayList<T> data = new ArrayList<>();
9+
private Comparator<T> ctor;
10+
11+
public genericheap(Comparator<T> ctor) { // constructor to initialize the generic comparator
12+
this.ctor=ctor;
13+
}
14+
15+
public int size() { // returns the size of the arraylist data
16+
return data.size();
17+
}
18+
19+
public boolean isEmpty() { // checks whether the list is empty or not :: return true or false for the same
20+
return data.isEmpty();
21+
}
22+
23+
public void display() { //displays the list
24+
System.out.println(this.data);
25+
}
26+
27+
public void add(T integer) { // in this function we have added the <t> type object into the arraylist and called upheapify
28+
data.add(integer);
29+
upheapify(data.size() - 1);
30+
}
31+
32+
private void upheapify(int ci) {
33+
if (ci == 0) {
34+
return;
35+
}
36+
int pi = (ci - 1) / 2;
37+
if (isLarger(ci,pi) == true) {
38+
swap(ci, pi);
39+
upheapify(pi);
40+
}
41+
}
42+
43+
private boolean isLarger(int i, int j) {
44+
T ith = data.get(i);
45+
T jth = data.get(j);
46+
if(ctor.compare(ith,jth)>0)
47+
{
48+
return true;
49+
}
50+
else
51+
{
52+
return false;
53+
}
54+
}
55+
56+
private void swap(int ci, int pi) { // swap function written like this because of the generic property
57+
T ith = data.get(ci);
58+
T jth=data.get(pi);
59+
data.set(ci, jth);
60+
data.set(pi, ith);
61+
}
62+
63+
public T getHP() {
64+
return data.get(0);
65+
}
66+
67+
public T removeHP() {
68+
69+
swap(0, data.size() - 1);
70+
T rv=data.remove(data.size()-1);
71+
downheapify(0);
72+
return rv;
73+
}
74+
75+
private void downheapify(int pi) {
76+
int lci = 2 * pi + 1;
77+
int rci = 2 * pi + 2;
78+
79+
int max = pi;
80+
81+
if (lci < data.size() && isLarger(lci, max) == true) {
82+
max = lci;
83+
}
84+
if (rci < data.size() && isLarger(rci, max) == true) {
85+
max = rci;
86+
}
87+
if (max != pi) {
88+
swap(pi, max);
89+
downheapify(max);
90+
}
91+
}
92+
93+
}

‎Conversions/AnytoAny.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
import java.util.Scanner;
2+
//given a source number , source base, destination base, this code can give you the destination number.
3+
//sn ,sb,db ---> ()dn . this is what we have to do .
4+
public class anytoany {
5+
6+
public static void main(String[] args) {
7+
Scanner scn = new Scanner(System.in);
8+
int sn = scn.nextInt();
9+
int sb = scn.nextInt();
10+
int db = scn.nextInt();
11+
int m=1,dec=0,dn=0;
12+
while(sn!=0)
13+
{
14+
dec=dec+ (sn%10)*m;
15+
m*=sb;
16+
sn/=10;
17+
}
18+
m=1;
19+
while(dec!=0)
20+
{
21+
dn=dn+ (dec%db)*m;
22+
m*=10;
23+
dec/=db;
24+
}
25+
System.out.println(dn);
26+
}
27+
28+
}

0 commit comments

Comments
 (0)