数据结构与算法(十四)哈夫曼树

问题

  1. 给定一串字符串:abcd,如何压缩?

我们知道每个字节在计算机中占8bit

假使我们定义二进制 00 表示 a01 表示b10 表示c11 表示d

那么abcd转为二进制后就变成了00011011,看,原本占4*8=32bit的一串字符串,现在只占8bit了,是不是压缩了4倍,nice!

  1. 给定一串字符串:aaaaaabcd,如何压缩?

如果我们再用上面的做法,就变成了00000000000000011011,我们发现前面有一大串0,那么我们有没有更好的办法进行优化呢?

比如定义a的二进制位0,咦,好像又缩短了一些,但是我们碰到001这样的应该怎么解码呢?首先来了个0解码为a,再来个0,解码为a,然后是1,我们发现没有对应的码值,解码失败了。这是为什么呢?

这里引出一个前缀的问题,这里明显a的二进制位是b的前缀,如果想保证解码成功,就必须保证没有前缀的情况发生,不然就会出现上面的问题。

说了那么多,现在我们正式看看什么是哈夫曼树吧~

定义

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

那么这个哈夫曼树和压缩又有什么关系呢?

二叉树:二叉,这时候你要想到二进制,二叉分左右嘛。左节点的边设置为0,右节点的边设置为1

哈夫曼编码

在上图的最优二叉树中我们给每一条边加上一个权值,指向左子节点的边我们标记为0,指向右子节点的边标记为1,那从根节点

到叶节点的路径就是我们说的哈夫曼编码;
哈夫曼编码.png

构建过程

核心思想:贪心算法:利用局部最优推出全局最优,把频率出现多的用短码表示,频率出现小的就用长一点。而且,任何一个字符的编码都不是另一个的前缀,在解压缩的时候,我们每次会读取尽可能长的可解压的二进制串,所以在解压缩的时候也不会产生歧义。

具体实现思路:
1.每次取数值最小的两个节点,将之组成为一颗子树。
2.移除原来的两个点
3.然后将组成的子树放入原来的序列中
4.重复执行1 2 3 直到只剩最后一个点

代码实现

package com.algorithm.tree;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class HFMTree {

    private final PriorityQueue<Node> priorityQueue;
    private final List<Node> nodeList;
    private final Map<Character, String> dictionary;
    private final Map<String, Character> deDictionary;

    private Node root;

    public HFMTree(Map<Character, Integer> dictionary) {
        priorityQueue = new PriorityQueue<>(dictionary.size());
        nodeList = new ArrayList<>(dictionary.size());
        this.dictionary = new HashMap<>(dictionary.size());
        this.deDictionary = new HashMap<>(dictionary.size());
        dictionary.forEach((chars, weight) -> {
            Node node = new Node(chars.toString(), weight);
            priorityQueue.add(node);
            nodeList.add(node);
        });
    }

    public String decode(String binary) {
        char[] chars = binary.toCharArray();
        StringBuilder message = new StringBuilder();
        StringBuilder sb = new StringBuilder();
        for (Character aChar : chars) {
            sb.append(aChar);
            Character character = deDictionary.get(sb.toString());
            if (character != null){
                message.append(character);
                sb = new StringBuilder();
            }
        }
        return message.toString();
    }

    public String encode(String message) {
        char[] chars = message.toCharArray();
        StringBuilder sb = new StringBuilder();
        for (char aChar : chars) {
            sb.append(dictionary.get(aChar));
        }
        return sb.toString();
    }

    public void code() {
        nodeList.forEach(node -> {
            String chars = node.chars;
            String code = "";
            do {
                if (node.parent.left == node) {
                    code = "0" + code;
                } else
                    code = "1" + code;
                node = node.parent;
            } while (node.parent != null);
            dictionary.put(chars.charAt(0), code);
            deDictionary.put(code, chars.charAt(0));
            System.out.println(chars + ":" + code);
        });
    }

    public void create() {
        int length = priorityQueue.size();
        for (int i = 0; i < length - 1; i++) {
            Node node1 = priorityQueue.poll();
            Node node2 = priorityQueue.poll();
            Node parent = new Node(node1.chars + node2.chars, node1.weight + node2.weight);
            parent.left = node1;
            parent.right = node2;
            node1.parent = parent;
            node2.parent = parent;
            priorityQueue.add(parent);
        }
        root = priorityQueue.poll();
    }


    private static class Node implements Comparable<Node> {
        Node left;
        Node right;
        Node parent;
        int weight;
        String chars;

        public Node(String chars, int weight) {
            this.chars = chars;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }

    public static void main(String[] args) {
        //a:7 b:10 c:3 d:20 e:6 f:15 g:22
        Map<Character, Integer> dictionary = new HashMap<>();
        dictionary.put('a', 7);
        dictionary.put('b', 10);
        dictionary.put('c', 3);
        dictionary.put('d', 20);
        dictionary.put('e', 6);
        dictionary.put('f', 15);
        dictionary.put('g', 22);
        HFMTree hfmTree = new HFMTree(dictionary);
        hfmTree.create();
        hfmTree.code();
        String binary = hfmTree.encode("abcdefg");
        System.out.println(binary);
        System.out.println(hfmTree.decode(binary));
    }
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×