当前位置: 首页 > news >正文

哈夫曼树

哈夫曼树(Huffman Tree)是一种最优的二叉树,常用于数据压缩,如在 Huffman 编码中使用。它是根据字符出现的频率来构造的,频率越高的字符越靠近树的根,频率低的字符则在较深的节点上。其核心思想是通过构建一颗最小堆(或者优先队列)来逐步合并最小的两个节点,直到所有节点都合并成一颗哈夫曼树。 

哈夫曼树的构建过程:

  1. 统计频率:首先统计每个字符出现的频率。
  2. 构建最小堆:将每个字符作为一个树的节点插入一个最小堆(优先队列)中。
  3. 合并最小频率的节点:每次从最小堆中取出两个频率最小的节点,创建一个新节点,其频率为这两个节点频率之和。然后将这个新节点插入回最小堆。
  4. 重复步骤3,直到堆中只剩下一个节点,这个节点就是哈夫曼树的根节点
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_map>
#include <string>using namespace std;// 哈夫曼树的节点
struct HuffmanNode {char ch;              // 存储字符int freq;             // 字符的频率HuffmanNode* left;    // 左子树HuffmanNode* right;   // 右子树// 构造函数HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}// 定义优先级队列的比较规则:按频率最小的优先struct Compare {bool operator()(HuffmanNode* l, HuffmanNode* r) {return l->freq > r->freq; // 返回 true 时 l 排在 r 后面}};
};// 用递归生成哈夫曼编码
void generateHuffmanCodes(HuffmanNode* root, const string& str, unordered_map<char, string>& huffmanCode) {if (root == nullptr)return;// 如果是叶子节点,保存它的编码if (!root->left && !root->right) {huffmanCode[root->ch] = str;}// 遍历左子树和右子树generateHuffmanCodes(root->left, str + "0", huffmanCode);generateHuffmanCodes(root->right, str + "1", huffmanCode);
}// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freq) {// 优先队列(最小堆)用于按频率排序priority_queue<HuffmanNode*, vector<HuffmanNode*>, HuffmanNode::Compare> minHeap;// 创建叶子节点并插入最小堆for (const auto& pair : freq) {minHeap.push(new HuffmanNode(pair.first, pair.second));}// 合并节点直到只剩一个节点while (minHeap.size() > 1) {// 取出两个最小的节点HuffmanNode* left = minHeap.top(); minHeap.pop();HuffmanNode* right = minHeap.top(); minHeap.pop();// 创建一个新的内部节点,频率为左右节点频率之和HuffmanNode* node = new HuffmanNode('\0', left->freq + right->freq);node->left = left;node->right = right;// 将新节点插入最小堆minHeap.push(node);}// 最后堆中剩下的节点就是哈夫曼树的根节点return minHeap.top();
}// 打印哈夫曼编码
void printHuffmanCodes(const unordered_map<char, string>& huffmanCode) {for (const auto& pair : huffmanCode) {cout << pair.first << ": " << pair.second << endl;}
}int main() {// 输入字符串string text = "this is an example for huffman encoding";// 统计每个字符的频率unordered_map<char, int> freq;for (char c : text) {freq[c]++;}// 构建哈夫曼树HuffmanNode* root = buildHuffmanTree(freq);// 保存每个字符的哈夫曼编码unordered_map<char, string> huffmanCode;// 生成哈夫曼编码generateHuffmanCodes(root, "", huffmanCode);// 打印哈夫曼编码printHuffmanCodes(huffmanCode);return 0;
}

相关文章:

哈夫曼树

哈夫曼树&#xff08;Huffman Tree&#xff09;是一种最优的二叉树&#xff0c;常用于数据压缩&#xff0c;如在 Huffman 编码中使用。它是根据字符出现的频率来构造的&#xff0c;频率越高的字符越靠近树的根&#xff0c;频率低的字符则在较深的节点上。其核心思想是通过构建一…...

wax到底是什么意思

在很久很久以前&#xff0c;人类还没有诞生文字之前&#xff0c;人类就产生了语言&#xff1b;在诞生文字之前&#xff0c;人类就已经使用了语言很久很久。 没有文字之前&#xff0c;人们的语言其实是相对比较简单的&#xff0c;因为人类的生产和生活水平非常低下&#xff0c;…...

笔记:使用ST-LINK烧录STM32程序怎么样最方便?

一般板子在插件上&#xff0c; 8脚 3.3V;9脚 CLK;10脚 DIO;4脚GND ST_Link 19脚 3.3V;9脚 CLK;7脚 DIO;20脚 GND 烧录软件&#xff1a;ST-LINK Utility&#xff0c;Keil_5; ST_Link 接口针脚定义&#xff1a; 按定义连接ST_Link与电路板&#xff1b; 打开STM32 ST-LINK Uti…...

数据分析系列--[11] RapidMiner,K-Means聚类分析(含数据集)

一、数据集 二、导入数据 三、K-Means聚类 数据说明:提供一组数据,含体重、胆固醇、性别。 分析目标:找到这组数据中需要治疗的群体供后续使用。 一、数据集 点击下载数据集 二、导入数据 三、K-Means聚类 Ending, congratulations, youre done....

Python在数据科学领域的深度应用:从数据处理到机器学习模型构建

Python在数据科学领域的深度应用:从数据处理到机器学习模型构建 在当今大数据与人工智能蓬勃发展的时代,Python凭借其简洁的语法、强大的库支持和活跃的社区,已成为数据科学家和工程师的首选编程语言。本文将深入探讨Python在数据科学领域的应用,从数据预处理、探索性分析…...

海外问卷调查渠道查,具体运营的秘密

相信只要持之以恒并逐渐掌握技巧&#xff0c;每一位调查人在踏上征徐之时都会非常顺利的。并在日后的职业生涯中拥有捉刀厮杀的基本技能&#xff01;本文会告诉你如何做好一个优秀的海外问卷调查人。 在市场经济高速发展的今天&#xff0c;众多的企业为了自身的生存和发展而在…...

穷举vs暴搜vs深搜vs回溯vs剪枝系列一>单词搜索

题解如下 题目&#xff1a;解析决策树&#xff1a;代码设计&#xff1a; 代码&#xff1a; 题目&#xff1a; 解析 决策树&#xff1a; 代码设计&#xff1a; 代码&#xff1a; class Solution {private boolean[][] visit;//标记使用过的数据int m,n;//行&#xff0c;列char…...

万字长文深入浅出负载均衡器

前言 本篇博客主要分享Load Balancing&#xff08;负载均衡&#xff09;&#xff0c;将从以下方面循序渐进地全面展开阐述&#xff1a; 介绍什么是负载均衡介绍常见的负载均衡算法 负载均衡简介 初识负载均衡 负载均衡是系统设计中的一个关键组成部分&#xff0c;它有助于…...

基于SpringBoot的青年公寓服务平台的设计与实现(源码+SQL脚本+LW+部署讲解等)

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…...

经典游戏红色警戒2之英语

1. New construction options 部署新的建筑物&#xff08;一般是部署基地车时说的&#xff09;。 2. Loading 等待。&#xff08;正在进行&#xff09; 3. Construction complete 建筑完成。 4. On hold 等待。&#xff08;暂停进行&#xff09; 5. Canceled 取消。 6. Ca…...

IM 即时通讯系统-50-[特殊字符]cim(cross IM) 适用于开发者的分布式即时通讯系统

IM 开源系列 IM 即时通讯系统-41-开源 野火IM 专注于即时通讯实时音视频技术&#xff0c;提供优质可控的IMRTC能力 IM 即时通讯系统-42-基于netty实现的IM服务端,提供客户端jar包,可集成自己的登录系统 IM 即时通讯系统-43-简单的仿QQ聊天安卓APP IM 即时通讯系统-44-仿QQ即…...

QtCreator在配置Compilers时,有一个叫ABI的选项,那么什么是ABI?

问题提出 QtCreator在配置Compilers时,有一个叫ABI的选项,那么什么是ABI&#xff1f; ABI&#xff08;Application Binary Interface&#xff09;介绍 ABI&#xff08;Application Binary Interface&#xff0c;应用二进制接口&#xff09;是指应用程序与操作系统或其他程序…...

处理 **5万字(约7.5万-10万token,中文1字≈1.5-2token)** 的上下文

处理 5万字&#xff08;约7.5万-10万token&#xff0c;中文1字≈1.5-2token&#xff09; 的上下文&#xff0c;对模型的长文本处理能力和显存要求较高。以下是不同规模模型的适用性分析及推荐&#xff1a; 一、模型规模与上下文能力的关系 模型类型参数量最大上下文长度&#…...

【狂热算法篇】探秘图论之Dijkstra 算法:穿越图的迷宫的最短路径力量(通俗易懂版)

羑悻的小杀马特.-CSDN博客羑悻的小杀马特.擅长C/C题海汇总,AI学习,c的不归之路,等方面的知识,羑悻的小杀马特.关注算法,c,c语言,青少年编程领域.https://blog.csdn.net/2401_82648291?typebbshttps://blog.csdn.net/2401_82648291?typebbshttps://blog.csdn.net/2401_8264829…...

springboot 启动原理

目标&#xff1a; SpringBootApplication注解认识了解SpringBoot的启动流程 了解SpringFactoriesLoader对META-INF/spring.factories的反射加载认识AutoConfigurationImportSelector这个ImportSelector starter的认识和使用 目录 SpringBoot 启动原理SpringBootApplication 注…...

浅析DDOS攻击及防御策略

DDoS&#xff08;分布式拒绝服务&#xff09;攻击是一种通过大量计算机或网络僵尸主机对目标服务器发起大量无效或高流量请求&#xff0c;耗尽其资源&#xff0c;从而导致服务中断的网络攻击方式。这种攻击方式利用了分布式系统的特性&#xff0c;使攻击规模更大、影响范围更广…...

Linux网络 HTTPS 协议原理

概念 HTTPS 也是一个应用层协议&#xff0c;不过 是在 HTTP 协议的基础上引入了一个加密层。因为 HTTP的内容是明文传输的&#xff0c;明文数据会经过路由器、wifi 热点、通信服务运营商、代理服务器等多个物理节点&#xff0c;如果信息在传输过程中被劫持&#xff0c;传输的…...

Idea插件开发

相关操作 执行插件 导出插件 然后到 /build/distributions 目录下面去找...

Java 有很多常用的库

1. 常用工具类库 Apache Commons&#xff1a;提供了大量常用的工具类&#xff0c;如&#xff1a; commons-lang3&#xff1a;字符串、数字、日期等常用工具类。commons-io&#xff1a;IO 操作&#xff0c;文件读写、流处理等。commons-collections4&#xff1a;集合类扩展。 G…...

pytorch实现文本摘要

人工智能例子汇总&#xff1a;AI常见的算法和例子-CSDN博客 import numpy as npfrom modelscope.hub.snapshot_download import snapshot_download from transformers import BertTokenizer, BertModel import torch# 下载模型到本地目录 model_dir snapshot_download(tians…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...