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

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

问题

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


目录
相关文章
|
存储 算法 C语言
C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作
C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作
|
2月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
5月前
|
机器学习/深度学习 存储
数据结构学习记录——哈夫曼树(什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码)
数据结构学习记录——哈夫曼树(什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码)
120 1
|
6月前
|
编译器
【数据结构】哈夫曼树编译码器【课程设计】
【数据结构】哈夫曼树编译码器【课程设计】
|
存储 算法
数据结构实验十二 哈夫曼树及编码
数据结构实验十二 哈夫曼树及编码
87 0
|
6月前
|
算法 Java
数据结构-构造哈夫曼树【详解+代码+图示】一文解惑!
数据结构-构造哈夫曼树【详解+代码+图示】一文解惑!
2674 0
|
C语言
c语言数据结构-哈夫曼树
c语言数据结构-哈夫曼树
100 0
|
存储 算法
【开卷数据结构 】哈夫曼树
【开卷数据结构 】哈夫曼树
115 0
数据结构——哈夫曼树
哈夫曼树 · 前言 哈夫曼树又叫做最优二叉树,可以将其看作一种特殊的二叉树。 可以说是从堆引入的哈夫曼树;堆的作用是构造最大堆和最小堆实现挑选最值删除的东西,而哈夫曼树也是寻找max和min并对其进行操作。 哈夫曼树的原理:出现频率较高的数占空间小,出现频率较低的数占空间更大。从而实现不压缩数据且节省空间的一种存储方式。
数据结构——哈夫曼树
|
算法
大话数据结构--哈夫曼树及其应用
大话数据结构--哈夫曼树及其应用
124 0