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();

            // assign short code, only indicates it's left or right node
            leftNode.code = "0";

            TreeNode rightNode = nodes.pollFirst();

            // assign short code, only indicates it's left or right node
            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) {

        // children's full code = parent full code + children's short code

        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) {
        // key is the word, value is the binding code
        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) {
        // key is the code, value is the binding word
        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) {
            // Returning either 1 or -1 is fine if this.weight = o.weight.

            // But returning 0 if now allowed because there are nodes of same weight, and
            // TreeSet will not keep the given node o if return 0 which will bring big trouble.

            if (this.weight >= o.weight) {
                return 1;
            }

            return -1;
        }
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-05 07:40:02

results matching ""

    No results matching ""