程序员经验分享-hwhale

哈夫曼树，哈夫曼编码及应用——（代码实现）

2023-05-16

哈夫曼树，哈夫曼编码及应用

  • 1.哈夫曼树
    • 1.1 什么是哈夫曼树
  • 2.如何构造哈夫曼树（哈夫曼算法）
    • 2.1 举例实现哈夫曼树
      • 2.1.1手动实现具体步骤
      • 2.1.2代码实现具体步骤
  • 3.哈夫曼编码
    • 3.1 什么是哈夫曼编码
    • 3.2哈夫曼编码的具体实现
  • END!!!

1.哈夫曼树 

路径长度：从树中一个节点到另一个节点之间的分支构成两个节点之间的路径，路径上的分支数目就成为路径长度。
树的路径长度：从树根到每一节点的路径长度之和。
带权路径长度：考虑到带权的节点，节点的带权路径长度是从该节点到根之间的路径长度与节点权的乘积。
带权路径长度（WPL）：树中所有叶子节点的带权路径长度之和。

在这里插入图片描述
在上图中，根节点到节点D的路径长度是4，二叉树的路径长度=1+1+2+2+3+3+4+4=20。WPL(a)=51+152+403+304+10*4=315。

1.1 什么是哈夫曼树

假设有n各权值{w1,w2,…,wn}，构造一棵有n各叶子节点的二叉树，每个叶子节点带权wk，每个叶子的路径长度为lk，WPL=w1l1+w2l2+…+wn*ln，记带权路径长度WPL最小的二叉树为哈夫曼树，也称其为最优二叉树。

2.如何构造哈夫曼树（哈夫曼算法）

  1. 根据给定的n个权值{w1,w2,…,wn}构成n个二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根节点，其左右子树均为空。
  2. 在F中选取两棵根节点的权值最小的树作为左右子树构造一个新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
  3. 在F中删除这两棵树，同时将新得到的二叉树加入F中。
  4. 重复步骤2和步骤3，直到F只含一棵树为止。这棵树便是哈夫曼树。

2.1 举例实现哈夫曼树

2.1.1手动实现具体步骤

在这里插入图片描述
在这里插入图片描述

2.1.2代码实现具体步骤

注意：二叉树的存储以数组形式保存，而且0下标不存储元素，i下标的左孩子2*i，右孩子2*i+2.（之前有关二叉树的文章介绍过，大家可以自行查看）。

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef unsigned int WeigthType;

typedef unsigned int NodeType;

typedef struct
{
    WeigthType weight;
    NodeType parent, leftchild, rightchild;
}HNode;

typedef struct IndexWeight
{
    int index;
    WeigthType weight;
    operator WeigthType() const { return weight; }//按照权值比较
};



class HuffManTree
{
private:
    vector<WeigthType> w;
    vector<HNode> hft;
    int n = 0;
public:
    //构造函数（初始化Huffman树）  (叶子节点树，权重，hufman树)
    HuffManTree(vector<WeigthType> w1)
    {
        w = w1;
        n = w1.size();
        hft.resize(n * 2);
        
        for (int i = 1; i <= n; i++)
        {
            hft.at(i).weight = w[i-1];
        }        
    }

    void CreatHuffman()
    {
        //优先级队列
        priority_queue<IndexWeight, vector<IndexWeight>, std::greater<IndexWeight>> qu;
        for (int i = 1; i <= n; i++)
        {
            qu.push(IndexWeight{ i,hft.at(i).weight });
        }

        int k = n +1;

        while (!qu.empty())
        {
            //左节点
            if (qu.empty()) break;
            IndexWeight left = qu.top();      qu.pop();
            //右节点
            if (qu.empty()) break;
            IndexWeight right = qu.top();     qu.pop();

            hft.at(k).weight = left.weight + right.weight;
            hft.at(k).leftchild = left.index;
            hft.at(k).rightchild = right.index;
            hft.at(left.index).parent = k;
            hft.at(right.index).parent = k;
            qu.push(IndexWeight{ k,hft.at(k).weight });
            k++;            
        }
    }

    void PrintTree()
    {
        int lenght = hft.size();
       
        for (int i = 1; i < lenght; i++)
        {
            cout << "index：" << i
                << "\tweight：" << hft.at(i).weight
                << "\tparent：" << hft.at(i).parent
                << "\tleftchile：" << hft.at(i).leftchild
                << "\trightchild：" << hft.at(i).rightchild << endl;                    
        }
        cout << endl;
    }
    vector<HNode> GetHft()
    {
        return hft;
    }
};
int main()
{
    vector<WeigthType> w{ 5,29,7,8,14,23,3,11 };
    
    HuffManTree tree(w);
    tree.CreatHuffman();
    cout << "打印哈夫曼树：" << endl;
    tree.PrintTree();    

    return 0;
}

在这里插入图片描述

3.哈夫曼编码

哈夫曼树是为了解决远距离通信的数据传输的最优化问题。
比如，有一段文字内容为ABCDEFGH，现需要将其传输给别人，通常就会用二进制来表示每个字符，如下（A的ASCII码为65）：

字母ABCDEFGH
二进制字符100 0001100 0010100 0011100 0100100 0101100 0110100 0111100 1000

按照上述所说，传输的内容变为：“100 0001100 0010100 0011100 0100100 010100 0110100 0111100 1000”接受时可以三位来解码。但是当文档很大时，所需要的二进制串是非常可怕的，而且有些字符出现的频率是非常高的。

为提高数据传输的效率，一般采用哈夫曼编码对数据进行压缩，随着字符的增多和多字符权重的不同，这种压缩会更加显出优势。

3.1 什么是哈夫曼编码

 前缀编码：编码中非0即1，长度不等的话其实很容易混淆，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。
一般地，设需要编码的字符集为{d1,d2,...,dn}，
	各个字符在电文中出现的次数或频率集合为{w1,w2,...,wn}，以d1,d2,...,dn作为叶子节点，
	以w1,w2,...,wn作为相应叶子节点的权值来构造一棵哈夫曼树。
	规定哈夫曼树的左分支表示0，右分支表示1，则从根节点到叶子节点所经过的路径分支组成的0和1的序列便为该节点对于字符的编码，这就是哈夫曼编码。

3.2哈夫曼编码的具体实现

字母ABCDEFGH
出现的频率*100529781423311
二进制字符111111011100001100111110001

在这里插入图片描述

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

typedef unsigned int WeigthType;

typedef unsigned int NodeType;

typedef struct
{
    WeigthType weight;
    NodeType parent, leftchild, rightchild;
}HNode;

typedef struct IndexWeight
{
    int index;
    WeigthType weight;
    operator WeigthType() const { return weight; }//按照权值比较
};



class HuffManTree
{
private:
    vector<WeigthType> w;
    vector<HNode> hft;
    int n = 0;
public:
    //构造函数（初始化Huffman树）  (叶子节点树，权重，hufman树)
    HuffManTree(vector<WeigthType> w1)
    {
        w = w1;
        n = w1.size();
        hft.resize(n * 2);

        for (int i = 1; i <= n; i++)
        {
            hft.at(i).weight = w[i-1];
        }        
    }

    void CreatHuffman()
    {
        //优先级队列
        priority_queue<IndexWeight, vector<IndexWeight>, std::greater<IndexWeight>> qu;//按照下标比较

        for (int i = 1; i <= n; i++)
        {
            qu.push(IndexWeight{ i,hft.at(i).weight });
        }

        int k = n +1;

        while (!qu.empty())
        {
            //左节点
            if (qu.empty()) break;
            IndexWeight left = qu.top();      qu.pop();
            //右节点
            if (qu.empty()) break;
            IndexWeight right = qu.top();     qu.pop();

            hft.at(k).weight = left.weight + right.weight;
            hft.at(k).leftchild = left.index;
            hft.at(k).rightchild = right.index;
            hft.at(left.index).parent = k;
            hft.at(right.index).parent = k;
            qu.push(IndexWeight{ k,hft.at(k).weight });
            k++;            
        }
    }

    void PrintTree()
    {
        int lenght = hft.size();
       
        for (int i = 1; i < lenght; i++)
        {
            cout << "index：" << i
                << "\tweight：" << hft.at(i).weight
                << "\tparent：" << hft.at(i).parent
                << "\tleftchile：" << hft.at(i).leftchild
                << "\trightchild：" << hft.at(i).rightchild << endl;             
        }
        cout << endl;
    }
    vector<HNode> GetHft()
    {
        return hft;
    }
};

typedef struct HuffmanCodeNode
{
    char ch;
    string code;
}HuffmanCodeNode;

class HuffManCode:public HuffManTree
{
private:
    vector<HuffmanCodeNode> huffcode;
    vector<HNode> hft;    
public:
    HuffManCode(const vector<char> *ch1, vector<WeigthType> w1):HuffManTree(w1)
    {
        int length = ch1->size();
        huffcode.resize(length+1);//0下标不用，从1下标开始
        for (int i = 1; i <= length; i++)
        {
            huffcode.at(i).ch = ch1->at(i-1);            
        }        
    }
    void CreateHuffmanCode()
    {
        hft = HuffManTree::GetHft();
        int length = huffcode.size();
        
        for (int i = 1; i < length; i++)//只需计算0-8下标的huffman编码
        {
            string code1;
            int k = length;
            int c = i;
            int parent = hft.at(c).parent;
            while (parent != 0)
            {
                string temp = hft.at(parent).leftchild == c ? "0" : "1";
                //code1.insert(0, temp);
                huffcode.at(i).code.insert(0, temp);
                c = parent;
                parent = hft.at(c).parent;
            }
        }
    }
    void PrintCode()
    {
        int length = huffcode.size();
        for (int i = 1; i < length; i++)
        {
            cout << "data：" << huffcode.at(i).ch << " --> " << hft.at(i).weight
                << " --> " << "huffmancode：" << huffcode.at(i).code << endl;
        }
    }
};

int main()
{
    vector<WeigthType> w{ 5,29,7,8,14,23,3,11 };
    vector<char> ch{ 'A','B','C','D','E','F','G','H' };
    
    HuffManCode hc(&ch,w);
    
    hc.CreatHuffman();
    hc.CreateHuffmanCode();
    cout << "打印哈夫曼树：" << endl;
    hc.PrintTree();
    cout << "打印哈夫曼编码：" << endl;
    hc.PrintCode();   

    return 0;
}

在这里插入图片描述

END!!!

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

哈夫曼树，哈夫曼编码及应用——（代码实现） 的相关文章

  • STM32串口详解

    实验一 xff1a 简单的利用串口接收中断回调函数实现数据的返回 关于串口调试助手 xff0c 还应知道 xff1a 发送英文字符需要用一个字符即8位 xff0c 发送汉字需要两个字符即16位 xff0c 如上图 xff0c 发送汉字 姜

  • RLException: [xx.launch] is neither a launch file in package [x] nor is [x] a launch file name的解决方法

    ROS学习过程中 xff0c 遇到问题 xff1a RLException xx launch is neither a launch file in package x nor is x a launch file name 出现的问题

  • numpy 中 shape 与 size 属性

    因为需要生成一个和现有矩阵大小相等的矩阵 xff0c 故查找了相关资料 span class token operator gt gt span span class token operator gt span span class to

  • Ubtuntu+C语言实现网络通信附源代码

    下面这个案例是我用C在ubtuntu上面写的网络编程案例 2 网络编程 xff08 1 xff09 OSI七层模型理想化 应用层 xff1a app xff0c 应用程序 表示层 xff1a 对数据进行加工 会话层 xff1a 建立会话 x

  • Jetson Nano的GPIO口学习

    1 配置GPIO库 https github com NVIDIA jetson gpio 1 安装pip工具 sudo apt get update sudo apt get install python3 pip sudo apt ge

  • 22.11.22 TCP与UDP 客户端与服务器 协议搭建

    ubuntu 64 ubuntu yuyu yu 11 cat Tcp Cli c 客户端 include lt stdio h gt include lt sys types h gt include lt sys socket h gt

  • cmake交叉编译配置

    cmake交叉编译配置 很多时候 xff0c 我们在开发的时候是面对嵌入式平台 xff0c 因此由于资源的限制需要用到相关的交叉编译 即在你host宿主机上要生成target目标机的程序 里面牵扯到相关头文件的切换和编译器的选择以及环境变量

  • OS——gcc、g++、gdb、vim、vs code的基本使用

    文章目录 g 43 43 的使用gdb的使用vim的使用vscode的使用vs code的安装vs code中C 43 43 的编译运行配置 如果想要学习如何在CentOS 7中安装配置gcc g 43 43 gdb zhs和oh my z

  • make和cmake

    编程人员已经使用CMake和Make很长一段时间了 当你加入一家大公司或者开始在一个具有大量代码的工程上开展工作时 xff0c 你需要注意所有的构建 你需要看到处跳转的 CMakeLists txt 文件 你应该会在终端使用 cmake 和

  • ubuntu自带python与anaconda python环境的切换

    ubuntu的python可分为三大类 xff1a 1 ubuntu自带的python环境 一般安装在 usr bin 中python2和python3可以共存 2 anaconda自带的base环境 3 在anaconda中创建的虚拟py

  • 详细介绍如何在ubuntu20.04中安装ROS系统，以及安装过程中出现的常见错误的解决方法，填坑！！！

    本篇文章写于2020 10 xff0c 经过很多小伙伴的验证 xff0c 文章所介绍的步骤是可以正常完成安装的 xff0c 现在是2021 10 xff0c 经过近期的探索 xff0c 我将安装步骤进行了进一步的优化 xff0c 使安装变得

  • VScode进行python开发出现 No module named “XXX“的解决方法

    VScode进行python开发出现 No module named 34 XXX 34 的解决方法 最近从pycharm转向vscode的时候 xff0c 遇到了如下问题 span class token keyword import s

  • CM3寄存器简介

    Cortex M3基础 寄存器组 通用目的寄存器组R0 R7 也被称为低组寄存器 xff0c 所有指令都能访问字长32位 通用目的寄存器组R8 R12 高组寄存器 32位寄存器 复位后的初始值不可预料 堆栈指针R13 CM3中共有两个堆栈指

  • 基于亚博K210开发板的学习之旅（一）

    本文参考亚博智能官方K210开源课程 五月份购买了亚博的K210开发板 xff0c 但由于课程压力就搁置了 xff0c 最近暑假得空又恰逢电赛清单里有这个 芯片 xff0c 就抽空学习一下 xff0c 特写下这些 xff0c 以作记录 按照

  • STM32标准库通用软件模拟IIC

    STM32标准库通用软件模拟IIC 继上次通用可移植的矩阵键盘之后 xff0c 便继续寻找着下一个能够拿来只需改改引脚就可以使用的通用方案 恰好最近在研究PCA9685 xff0c 这是一片能够产生最多十六路PWM信号的芯片 xff0c 通

  • STM32F103控制PCA9685产生16路PWM波控制SG90舵机

    STM32控制PCA9685产生16路PWM波控制SG90舵机 如果你能点开这篇文章 xff0c 说明你已经知道PCA9685是多么强大 xff0c NXP公司原本做这片芯片是为了提供给LED使用 xff0c 在其官方文档里也能看到所有PW

  • 从源代码来看HAL库函数（一） HAL基础函数

    从源代码来看HAL库函数 xff08 一 xff09 HAL基础函数 全局变量 IO uint32 t uwtick 这个变量充当了一个运行时长计数的作用 xff0c 每发生一次SysTick中断就会加一 xff0c 直至溢出 xff0c

  • 使用TCP+串口与板子进行网络通信

    最近做了一个嵌入式的project xff0c 大概要求就是做一个client端 xff0c 一个sensor端 xff0c 两者通过TCP UDP进行通信 xff0c 然后在client端输入不同的命令sensor需做出不同的处理 xff

  • 毕业论文格式（图片题注引用，表格，公式格式）

    本科毕业论文差不多写完了 xff0c 记录一下一些格式 xff0c 以后写作可能会用到 xff0c 就可以翻起来看看 首先 xff0c 如果可以找到一篇格式符合要求的word文档的话 xff0c 最简单的方法就是在这个文档的基础上进行内容的

  • 图像处理——相位恢复（GS,TIE,改进型角谱迭代法）（已更新代码）

    利用GS xff0c TIE xff0c 改进型角谱迭代算法进行相位恢复 角谱传播理论 角谱传播理论可以翻阅傅里叶光学的书 xff0c 就能找到定量分析的计算公式 xff0c 可以分析某个平面的角谱垂直传播到另外一个平面的角谱 xff0c

随机推荐

  • 串口应用：遵循uart协议，发送多个字节的数据（状态机）

    上一节中 xff0c 我们遵循uart协议 xff0c 它发送一次只能发送6 7 8位数据 xff0c 我们不能随意更改位数 xff08 虽然在代码上可行 xff09 xff0c 不然就不遵循uart协议了 xff0c 会造成接收端无法接收

  • 数码管动态显示Verilog实现（参考小梅哥教程）(视觉暂留)

    一个数码管有八个引脚 xff0c 控制八段二极管的亮灭 xff0c 用以显示需要的数字 当有N个数码管时 xff0c 一个一个控制的话需要N x 8 个引脚 xff0c 消耗资源较多 因此可以利用动态显示的方案通过人眼的视觉暂留特性达到静态

  • 彻底理解DDS（信号发生器）的fpga实现（verilog设计代码）

    DDS xff08 Direct Digital Synthesis xff09 是一种把一系列数字信号通过D A转换器转换成模拟信号的数字合成技术 它有查表法和计算法两种基本合成方法 在这里主要记录DDS查表法的fpga实现 查表法 xf

  • HDMI/DVI

    一 基础知识 1 历史 早期在FPGA芯片上实现HDMI控制显示是使用HDMI发送芯片 xff0c eg xff1a ADV7513 sil9022 xff0c CH7301等 用之前VGA控制中输出的RGB信号 行场同步信号和使能信号输入

  • HDMI/DVI____TMDS编码

    一 编码步骤 xff1a 基本方法 xff1a 取第一位数据为初值 xff0c 接下来输入的每一位与前一导出的位 xff08 根据判断条件 xff09 进行异或XOR或者同或XNOR xff08 最小化传输 xff0c 减少0 1翻转 xf

  • HDMI/DVI____串行发送器

    一 功能 xff1a 把10bit数据转化为串行数据在一个时钟周期全部输出 xff08 先输出高位 xff0c 再输出低位 xff09 二 框图 二 思路 对于TMDS编码器 xff0c 在每一个输入时钟周期 xff0c 输入一次数据到TM

  • keil添加新文件.c.h

    文章目录 添加文件到组中1 双击组名称2 点击快捷键 添加头文件路径 h1 点击魔术棒快捷键2 头文件加 添加文件到组中 1 双击组名称 双击组名称 xff0c 打开弹窗 xff0c 然后选择相应的组中的新文件 xff0c 在点击ADD 2

  • QT常用控件（二）——自定义控件封装

    引言 Qt已经提供了很多的基础控件供开发使用 xff0c 而Qt原生的控件有时候并不能满足我们的需求 xff0c 特别是在工业的运用上 xff0c 比如我们需要一个日期时间的选择器 xff0c Qt虽然已经提供了原生的QDateTime控件

  • STM32之串口通信USART模块学习(1)

    一 通信接口 通信的目的 xff1a 将一个设备的数据传送到另一个设备 xff0c 扩展硬件系统通信协议 xff1a 制定通信的规则 xff0c 通信双方按照协议规则进行数据收发 单端信号通信的双方必须要共地 xff0c 因为都是对GND的

  • 2019电赛总结（一）

    2019电赛总结 xff08 一 xff09 文章目录 2019电赛总结 xff08 一 xff09 4 那之前5 电赛初期6 电赛中期7 电赛强化练习8 电赛预热阶段8月初9 那以后 4 那之前 2019电赛总结 序 xff09 5 电赛

  • 统计从键盘输入的一行字符中小写字母，大写字母，数字字符和其它字符的个数。

    统计从键盘输入的一行字符中小写字母 xff0c 大写字母 xff0c 数字字符和其它字符的个数 C语言实现 vs 2019 span class token macro property span class token directive

  • c语言求1~10的阶乘和

    求1 43 2 43 3 43 43 10 的和 span class token macro property span class token directive keyword include span span class toke

  • C和Cpp区别

    1 输入 xff0c 输出不同 xff08 out xff0c put xff09 c语言 xff1a include lt stdio h gt scanf 34 d 34 amp a printf 34 a 61 d n 34 a cp

  • C++实现基于顺序搜索的动态分区分配算法

    目录 1 需求分析 2 代码实现 3 测试用例 4 总结与收获 1 需求分析 动态分区分配又称为可变分区分配 xff0c 他是根据进程的实际需要 xff0c 动态地为之分配内存空间 在实现动态分区分配时 xff0c 将涉及到分区分配中所有的

  • C语言实现TCP编程

    C语言实现TCP编程 1 主机字节序和网络字节序2 套接字的地址结构IP地址转化的方法 3 TCP的网络接口4 TCP服务器端的编程流程5 TCP客户端的编程流程6 运行结果 1 主机字节序和网络字节序 主机字节序 xff1a 不同的芯片

  • QT---用户登录注册案例实现

    用户登录 注册 span class token macro property span class token directive hash span span class token directive keyword include

  • C++中list详解

    list详解 list的介绍list函数说明成员类型构造函数元素访问迭代器容量修改器操作 vector和list区别总结vector和list的使用场景 仿写END xff01 96 在这里插入代码片 96 list的介绍 list是序列容

  • sip response 摘要认证

    详解摘要认证 1 什么是摘要认证 摘要认证与基础认证的工作原理很相似 xff0c 用户先发出一个没有认证证书的请求 xff0c Web服务器回复一个带有WWW Authenticate头的响应 xff0c 指明访问所请求的资源需要证书 但是

  • Prim算法实现最小生成树

    Prim算法实现最小生成树 1 最小生成树是什么2 最小生成树的用途3 Prim算法描述4 Prim算法演示最小生成树过程5 Prim算法实现END 1 最小生成树是什么 对连通图进行遍历 过程中所经过的边和顶点的组合可看做是一棵普通树 通

  • 哈夫曼树，哈夫曼编码及应用——（代码实现）

    哈夫曼树 xff0c 哈夫曼编码及应用 1 哈夫曼树1 1 什么是哈夫曼树 2 如何构造哈夫曼树 xff08 哈夫曼算法 xff09 2 1 举例实现哈夫曼树2 1 1手动实现具体步骤2 1 2代码实现具体步骤 3 哈夫曼编码3 1 什么是

热门标签