当前位置: 首页 > 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…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...