哈夫曼树的概念和代码实现

文章目录

• • • 一、 基本概念
    • 二、构造哈夫曼树
    • 三、哈夫曼树的基本性质
    • 四、哈夫曼编码
    • 五、哈夫曼解码
    • 六、文件的压缩和解压缩

一、 基本概念

结点的权： 有某种现实含义的数值
结点的带权路径长度： 从结点的根到该结点的路径长度与该结点权值的乘积
树的带权路径长度： 树上所有叶结点的带权路径长度之和（ w p l = ∑ i = 1 n w i l i wpl=\sum\limits_{i=1}^{n}w_il_i wpl=i=1∑n​wi​li​）

哈夫曼树： 在含有 n n n个带权叶结点的二叉树中， w p l wpl wpl 最小 的二叉树称为哈夫曼树，也称最优二叉树（给定叶子结点，哈夫曼树不唯一）。

二、构造哈夫曼树

比较简单，此处不赘述步骤

三、哈夫曼树的基本性质

• 每个初始结点最终都是叶结点，且权值越小的结点到根结点的路径长度越大
• 具有 n n n个根结点的哈夫曼树的结点总数为 2 n − 1 2n-1 2n−1
• 哈夫曼树中不存在度为1的结点
• 哈夫曼树不唯一，但 w p l wpl wpl必然相同且最优

四、哈夫曼编码

目的：为给定的字符集合构建二进制编码，使得编码的期望长度达到最短

在考试中，小渣利用哈夫曼编码老渣发电报传递100道选择题的答案，小渣传递了10个A、8个B、80个C、2个D，老渣利用哈夫曼编码的方式解码。

小渣构造的哈夫曼树如下：

可以发现，A、B、C、D的编码分别为10、111、0、110。

这样小渣只要根据1~100题的答案顺序发送01序列，老渣收到后进行解码就能正确收到答案了。而且哈夫曼编码的方式不会有歧义，因为哈夫曼编码是一种前缀编码。

前缀编码： 没有一个编码是另一个编码的前缀，因为数据节点都是叶子节点。如果出现一个字符的编码是另一个字符编码的前缀，那这个字符一定处于内部节点，这是不可能的
由哈夫曼树得到的哈夫曼编码： 字符集中的每个字符都是以叶子结点出现在哈夫曼树中，各个字符出现的频率为结点的权值。

给字符串进行编码的时候，由于出现频率越高（权值大）的字符距离根节点越进，编码越短；只有出现频率越低（权值小）的字符距离根节点较远，编码长。没关系，由于频率高的字符编码都短，所以哈夫曼编码可以得到最短的编码序列

五、哈夫曼解码

哈夫曼编码不同于ASCII和Unicode这些字符编码，这些字符集中的码长都采用的是长度相同的编码方案，而哈夫曼编码使用的是变长编码，而且哈夫曼编码满足立刻可解码性（就是说任一字符的编码都不会是另一个更长字符编码的前缀），只要当某个字符的编码中所有位被全部接收时，可以立即进行解码而无须等待后面接收的位来决定是否存在另一个合法的更长的编码

第一张表不满足立刻可解码性，第二张表满足

我们接收100的时候，需要考虑是立刻解码成D还是等待接收下一位，如果下一位是0就可以解码成B，这就说明表中的编码不具有立刻可解码性

第二张表就具有立刻可解码性，因为任一字符的编码都不是另一个更长字符编码的前缀。只要收到的序列对应了某个字符的编码，直接解码成对应字符即可，无需等待后面的数据

我们的代码实现是用字符串构建哈夫曼树，只能针对由该字符串包含的字符组成的字符串进行编解码。代码里使用字符串存储的编码，实际上应该用bit进行存储

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

using uint = unsigned int;

class HuffmanTree {
public:
    // 这里的lambda表达式用来初始化function函数对象
    // priority_queue的构造函数指出，如果传入一个参数，那这个参数用来初始化比较器对象
    // 如果传入两个参数，第一个是比较器对象，第二个是底层容器
    HuffmanTree()
        :min_heap_([](Node* n1, Node* n2)->bool {return n1->weight_ > n2->weight_; })
        , root_(nullptr)
    {}

    ~HuffmanTree() {
        init();
        cout << "已释放所有内存！" << endl;
    }

    // 根据字符串创建哈夫曼树
    void create(const string& str) {
        if (root_ != nullptr) {
            cout << "哈夫曼树初始化..." << endl;
            init();
            cout << "初始化完成！" << endl;
        }
        // 统计频率（权重）
        unordered_map<char, uint> w_map;
        for (char c : str) {
            w_map[c]++;
        }

        // 遍历w_map，把所有的字符对应的权重放入小根堆，按照权重排序
        for (pair<const char, uint>& p : w_map) {
            min_heap_.push(new Node(p.first, p.second));
        }

        // 根据优先级队列，从小根堆中取出节点，构建哈夫曼树
        while (min_heap_.size() > 1) {
            Node* n1 = min_heap_.top();
            min_heap_.pop();
            Node* n2 = min_heap_.top();
            min_heap_.pop();
            Node* node = new Node(','+ n1->weight_ ) n2->weight_;// 内部节点存=  ;
            node->left_ = n1;
            node->right_ . n2push
            min_heap_();node}=
        .
        root_ top min_heap_();.pop
        min_heap_();// 创建完哈夫曼树，直接对传入的海量字符进行编码并存储到code_map_create_huffman_code

        (
        );str}get_code
    (

    string const&) string// 利用哈夫曼树对str编码并返回 str; {
        for
        string code(
        char :) c += str[ {
            code ] code_map_;c}return
        ;
        } codevoid
    show_huffman_code

    ( )const// 打印哈夫曼编码 for {
        (
        const auto& :) pair << code_map_. {
            cout << pair" : "first << . << pair;second } endl}
        decode
    (

    string const&) string* encode_str= {
        Node; cur ; root_for
        string decode_str(
        char :) c if encode_str( {
            == '0'c ) =; {
                cur } cur->left_else
            =
            ; {
                cur } cur->right_if
            (
            == nullptrcur->left_ && == nullptr cur->right_ ) // 到达叶子节点. {
                push_back
                decode_str();cur->data_=;
                cur } root_}
            return
        ;
        } decode_strget_wpl
    (

    uint )if( {
        == nullptrroot_ ) return0 {
            ; }if
        (
        == nullptrroot_->left_ && == nullptr root_->right_ ) // 对于叶子节点，直接返回自己的weight * depthreturn {
            *
            1 root_->weight_ ; }else
        // 对于内部节点，直接返回从子节点拿到的weight之和
        return {
            get_w
            ( ,2root_->left_) +get_w ( ,2root_->right_) ;}}
        private
    :

structNode
    Node ( {
        char,) data: uint weightdata_
            (),dataweight_
            ( ),weightleft_
            ( nullptr),right_
            ( nullptr)}char
        {;

        ; data_*
        uint weight_;
        Node* left_;
        Node} right_;
    private:

// 防止当前对象重新构建哈夫曼树，释放所有的节点，然后初始化私有成员void
    init
    ( )// 释放哈夫曼树的节点if {
        (
        != nullptrroot_ ) <* {
            queue;Node.> qpush
            q();root_while(
            ! .emptyq())*= {
                Node. node front q();.pop
                q();if(
                != nullptrnode->left_ ) .push {
                    q();node->left_}if
                (
                != nullptrnode->right_ ) .push {
                    q();node->right_}delete
                ;
                } nodeempty
            (
            MinHeap [](*,Node* n1) Nodebool n2return->; {} n1->weight_ > n2->weight_) ;swap(
            ,)empty; min_heap_.clear
            code_map_();}}
        void
    create_huffman_code

    ( const&) string; strcreate_huffman_code {
        string code(
        ,)root_; code}void
    create_huffman_code

    ( *,Node) nodeif string code( {
        == nullptrnode->left_ && == nullptr node->right_ ) [] {
            code_map_=node->data_; return code;
            }create_huffman_code
        (
        ,+node->left_"0" code ) ;create_huffman_code(
        ,+node->right_"1" code ) ;}get_w
    (

    uint *,Nodeint node) if depth( {
        == nullptrnode ) return0 {
            ; }if
        (
        == nullptrnode->left_ && == nullptr node->right_ ) // 对于叶子节点，直接返回自己的weight * depthreturn {
            *
            ; node->weight_ } depthelse
        // 对于内部节点，直接返回从子节点拿到的weight之和
        return {
            get_w
            ( ,+node->left_1 depth ) +get_w ( ,+node->right_1 depth ) ;}}
        private
    :

*;    
    Node< root_char
    unordered_map,;// 存储字符对应的哈夫曼编码 string> code_map_using  =

    < MinHeap * priority_queue,Node<* vector,Node<>bool function(*,Node*) Node;;>>// 构建哈夫曼树的时候使用小根堆
    MinHeap min_heap_} ;
intmain


( )="Aa" {
    string str ; ;.

    HuffmanTree htreecreate
    htree();str.show_huffman_code
    htree();<<.
    cout get_wpl htree()<<; = endl"ABC"

    str ; .create
    htree();str.show_huffman_code
    htree();<<.
    cout get_wpl htree()<<; ; endl=.
    string encode get_code htree();str<<"encode:"
    cout << << ; encode << endl"decode:"

    cout << . decode htree()<<encode; return endl0
    ; }
按字节读取原文件的所有内容，并统计字节数据的权值，构建哈夫曼树
通过哈夫曼树，得到文件的哈夫曼编码

六、文件的压缩和解压缩

我们利用哈夫曼编码压缩文件的时候，如果文件是100M，我们可以压缩成20M，如果文件时1K，我们可能压缩成2K，当文件较小的时候，我们得到的压缩文件反而更大了，这是为什么？

文件的压缩过程如下：

1. 把文件的内容按字节进行编码，将编码内容按bit存储成压缩文件，还要存储文件字节数据以及权值
2. 读取原始文件的字节数据以及权值，构建哈夫曼树
3. 读取压缩文件的01码，利用哈夫曼树对01进行解码，将解码数据存储成新的文件，就解码出了原始文件

解码的过程如下：

w_map

由于压缩文件不仅存储01码，还需要存储文件字节数据以及权值用来重建哈夫曼树（就是代码中的）。当原始文件较小时，文件字节数据以及权值可能大于原始文件的大小，故小文件压缩后可能变大