Add Compression Algorithm

TheAlgorithms · tosirap · Oct 3, 2017 · Oct 3, 2017 · Oct 23, 2017 · Oct 23, 2017
commit ffa8d834c3272a4c72b3bcbbb6ed552ed6c98b84
@@ -0,0 +1,105 @@
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.HashMap;
+
+public class HEncoder {
+
+	public HashMap<Character, String> encoder = new HashMap<>();
+	public HashMap<String, Character> decoder = new HashMap<>();
+
+	private static class Node {
+
+		Character ch;
+		Integer freq;
+		Node left;
+		Node right;
+
+		public static final Nodecomparator Ctor = new Nodecomparator();
+
+		public static class Nodecomparator implements Comparator<Node> {
+
+			@Override
+			public int compare(Node o1, Node o2) {
+				return o2.freq - o1.freq;
+			}
+
+		}
+	}
+
+	public HEncoder(String feeder) {
+		// 1. freq map
+		HashMap<Character, Integer> freqmap = new HashMap<>();
+		for (int i = 0; i < feeder.length(); ++i) {
+			char ch = feeder.charAt(i);
+			if (freqmap.containsKey(ch)) {
+				freqmap.put(ch, freqmap.get(ch) + 1);
+			} else {
+				freqmap.put(ch, 1);
+			}
+		}
+
+		// 2. prepare the heap from keyset
+		genericheap<Node> heap = new genericheap<Node>(Node.Ctor);
+		ArrayList<Character> k = new ArrayList<>(freqmap.keySet());
+		for (Character c : k) {
+			Node n = new Node();
+			n.ch = c;
+			n.left = null;
+			n.right = null;
+			n.freq = freqmap.get(c);
+			heap.add(n);
+		}
+
+		// 3.Prepare tree, remove two , merge, add it back
+		Node fn = new Node();
+		while (heap.size() != 1) {
+			Node n1 = heap.removeHP();
+			Node n2 = heap.removeHP();
+			fn = new Node();
+
+			fn.freq = n1.freq + n2.freq;
+			fn.left = n1;
+			fn.right = n2;
+
+			heap.add(fn);
+		}
+
+		// 4. traverse
+
+		traverse(heap.removeHP(), "");
+	}
+
+	private void traverse(Node node, String osf) {
+
+		if (node.left == null && node.right == null) {
+			encoder.put(node.ch, osf);
+			decoder.put(osf, node.ch);
+			return;
+		}
+		traverse(node.left, osf + "0");
+		traverse(node.right, osf + "1");
+
+	}
+
+	public String compress(String str) {
+		String rv = "";
+		for (int i = 0; i < str.length(); ++i) {
+			rv += encoder.get(str.charAt(i));
+		}
+		return rv;
+	}
+
+	public String decompress(String str) {
+		String s = "";
+		String code = "";
+		for (int i = 0; i < str.length(); ++i) {
+			code += str.charAt(i);
+			if (decoder.containsKey(code)) {
+				s += decoder.get(code);
+				code = "";
+			}
+		}
+
+		return s;
+	}
+}
@@ -0,0 +1,11 @@
+
+public class compressclient {
+
+	public static void main(String[] args) {
+
+		HEncoder h= new HEncoder("aaaabbbcccccccccccdddd");
+		System.out.println(h.compress("aabccd"));
+		System.out.println(h.decompress("101011000111"));
+	}
+
+}
@@ -0,0 +1,93 @@
+
+
+import java.util.ArrayList;
+import java.util.Comparator;
+
+public class genericheap<T> {
+
+	private ArrayList<T> data = new ArrayList<>();
+	private Comparator<T> ctor;
+
+	public genericheap(Comparator<T> ctor) {
+		this.ctor=ctor;
+	}	
+
+	public int size() {
+		return data.size();
+	}
+
+	public boolean isEmpty() {
+		return data.isEmpty();
+	}
+
+	public void display() {
+		System.out.println(this.data);
+	}
+
+	public void add(T integer) {
+		data.add(integer);
+		upheapify(data.size() - 1);
+	}
+
+	private void upheapify(int ci) {
+		if (ci == 0) {
+			return;
+		}
+		int pi = (ci - 1) / 2;
+		if (isLarger(ci,pi) == true) {
+			swap(ci, pi);
+			upheapify(pi);
+		}
+	}
+
+	private boolean isLarger(int i, int j) {
+		T ith = data.get(i);
+		T jth = data.get(j);
+		if(ctor.compare(ith,jth)>0)
+		{
+			return true;
+		}
+		else
+		{
+			return false;
+		}
+	}
+
+	private void swap(int ci, int pi) {
+		T ith = data.get(ci);
+		T jth=data.get(pi);
+		data.set(ci, jth);
+		data.set(pi, ith);
+	}
+
+	public T getHP() {
+		return data.get(0);
+	}
+
+	public T removeHP() {
+
+		swap(0, data.size() - 1);
+		T rv=data.remove(data.size()-1);
+		downheapify(0);
+		return rv;
+	}
+
+	private void downheapify(int pi) {
+		int lci = 2 * pi + 1;
+		int rci = 2 * pi + 2;
+
+		int max = pi;
+
+		if (lci < data.size() && isLarger(lci, max) == true) {
+			max = lci;
+		}
+		if (rci < data.size() && isLarger(rci, max) == true) {
+			max = rci;
+		}
+		if (max != pi) {
+			swap(pi, max);
+			downheapify(max);
+		}
+	}
+
+}