import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;
public class Huffman {
public static void main(String[] args) {
Map<String, Integer> words = new TreeMap<>();
String text = "In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression.";
for (int i = 0; i < text.length(); i++) {
String key = text.charAt(i) + "";
if (!words.containsKey(key)) {
words.put(key, 0);
}
words.put(key, words.get(key) + 1);
}
TreeNode root = buildTree(words);
String encoded = encode(root, text);
System.out.println(encoded);
String decoded = decode(root, encoded);
System.out.println(decoded);
}
public static TreeNode buildTree(Map<String, Integer> words) {
TreeSet<TreeNode> nodes = new TreeSet<>();
for (String word : words.keySet()) {
int frequence = words.get(word);
TreeNode tmp = new TreeNode(frequence, null, null);
tmp.word = word;
nodes.add(tmp);
}
while (nodes.size() > 1) {
TreeNode leftNode = nodes.pollFirst();
leftNode.code = "0";
TreeNode rightNode = nodes.pollFirst();
rightNode.code = "1";
TreeNode newNode = new TreeNode(leftNode.weight + rightNode.weight, leftNode, rightNode);
nodes.add(newNode);
}
assignCode(nodes.first());
return nodes.first();
}
private static void assignCode(TreeNode tNodes) {
if (tNodes.left != null) {
tNodes.left.code = tNodes.code + tNodes.left.code;
assignCode(tNodes.left);
}
if (tNodes.right != null) {
tNodes.right.code = tNodes.code + tNodes.right.code;
assignCode(tNodes.right);
}
}
public static String encode(TreeNode tree, String text) {
Map<String, String> map = new HashMap<>();
flatten1(tree, map);
String ans = "";
for (int i = 0; i < text.length(); i++) {
ans += map.get(text.charAt(i) + "");
}
return ans;
}
public static String decode(TreeNode tree, String text) {
Map<String, String> map = new HashMap<>();
flatten2(tree, map);
String ans = "";
while (!text.isEmpty()) {
for (String key : map.keySet()) {
if (!text.startsWith(key)) {
continue;
}
ans += map.get(key);
text = text.substring(key.length());
}
}
return ans;
}
public static void flatten1(TreeNode root, Map<String, String> map) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
map.put(root.word, root.code);
return;
}
flatten1(root.left, map);
flatten1(root.right, map);
}
public static void flatten2(TreeNode root, Map<String, String> map) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
map.put(root.code, root.word);
return;
}
flatten2(root.left, map);
flatten2(root.right, map);
}
private static class TreeNode implements Comparable<TreeNode> {
int weight;
String word;
String code;
TreeNode left;
TreeNode right;
public TreeNode(int weight, TreeNode left, TreeNode right) {
this.weight = weight;
this.left = left;
this.right = right;
this.code = "";
}
@Override
public int compareTo(TreeNode o) {
if (this.weight >= o.weight) {
return 1;
}
return -1;
}
}
}