赫夫曼编码—数据压缩算法

赫夫曼算法类 Huffman.java

/**

 * @Author: ltx

 * @Description: 赫夫曼编码

 */

public class Huffman {

    Map codeMap = new HashMap<>();

    /**

     * 中序遍历(前序或后序也行)

     * 得到huffman编码

     *

     * @param node 节点

     * @param sb   StringBuilder

     */

    public void getCodeByMidOrder(Node node, StringBuilder sb) {

        if (node.left != null) {

            //往左走+'0'

            sb.append("0");

            getCodeByMidOrder(node.left, sb);

        }

        //叶子节点

        if (node.left == null && node.right == null) {

//            System.out.print(node + ":" + sb + ", ");

            codeMap.put(node.value, sb.toString());

        }

        if (node.right != null) {

            //往右走+'1'

            sb.append("1");

            getCodeByMidOrder(node.right, sb);

        }

        //回溯向上走减少一个字符

        if (sb.length() > 0) {

            sb.deleteCharAt(sb.length() - 1);

        }

    }

    public Node getHuffmanTree(List nodes) {

        Collections.sort(nodes);

//        System.out.println(nodes);

        while (nodes.size() > 1) {

            //左叶子-数组最小值

            Node leafLeft = nodes.remove(0);

            //右叶子-数组次小值

            Node leafRight = nodes.remove(0);

            //父节点=数组最小值+数组次小值

            Node parentNode = new Node(null, leafLeft.weight + leafRight.weight);

            parentNode.left = leafLeft;

            parentNode.right = leafRight;

            //新的节点添加到list里面

            nodes.add(parentNode);

            Collections.sort(nodes);

        }

        return nodes.get(0);

    }

    /**

     * 获取各个字符权重(字符个数)

     *

     * @param str

     * @return

     */

    public List getCharWight(String str) {

        Map charNumMap = new HashMap<>();

        char[] chs = str.toCharArray();

        for (char c : chs) {

            //数量

            Integer count = charNumMap.get(c);

            if (count == null) {

                charNumMap.put(c, 1);

            } else {

                charNumMap.put(c, count + 1);

            }

        }

//        System.out.println(charNumMap);

        List nodes = new ArrayList<>();

        //创建节点List

        for (char c : charNumMap.keySet()) {

            nodes.add(new Node(c, charNumMap.get(c)));

        }

        return nodes;

    }

    /**

     * 编码

     * 根据赫夫曼编码表，对原始数据做转换

     *

     * @param str 原始字符串

     * @return

     */

    public String encoding(String str) {

        StringBuilder sb = new StringBuilder();

        char[] chs = str.toCharArray();

        for (char c : chs) {

            sb.append(codeMap.get(c));

        }

        return sb.toString();

    }

    /**

     * 解码

     *

     * @return

     */

    public String decode(String encodStr) {

        //翻转codeMap

        Map encodeMap = new HashMap<>();

        for (char c : codeMap.keySet()) {

            encodeMap.put(codeMap.get(c), c);

        }

        char[] chs = encodStr.toCharArray();

        int j = 0;

        StringBuilder res = new StringBuilder();

        while (j < encodStr.length() - 1) {

            StringBuilder sb = new StringBuilder();

            Character cr;

            //匹配出字符串

            while ((cr = encodeMap.get(sb.toString())) == null) {

                sb.append(chs[j]);

                j++;

            }

            res.append(cr);

        }

        return res.toString();

    }

    public static void main(String[] args) {

        Huffman huffman = new Huffman();

        System.out.println("原始数据:");

        //需要压缩的串

        String str = "i like like like java do you like a java";

        System.out.println(str);

        //1.获得字符权重List

        List 货币代码nodes = huffman.getCharWight(str);

        //[ :9, a:5, d:1, e:4, u:1, v:2, i:5, y:1, j:2, k:4, l:4, o:2]

        System.out.println("节点权重列表:");

        System.out.println(nodes);

        //2.构造赫夫曼树

        Node root = huffman.getHuffmanTree(nodes);

        //3.获得赫夫曼编码表

        huffman.getCodeByMidOrder(root, new StringBuilder(""));

        System.out.println("赫夫曼编码表:");

        //得到赫夫曼编码表

        //{ =01, a=100, d=11000, u=11001, e=1110, v=11011, i=101, y=11010, j=0010, k=1111, l=000, o=0011}

        System.out.println(huffman.codeMap);

        //4.压缩编码

        String encodStr = huffman.encoding(str);

        System.out.println("压缩后数据:");

//1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

        System.out.println(encodStr);

        //5.解压

        String res = huffman.decode(encodStr);

        System.out.println("解压后数据:");

        //打印最终结果

        //i like like like java do you like a java

        System.out.println(res);

    }

}