哈夫曼树原理及其C语言实现

目录

原理

应用场景

实现步骤

C语言实现

总结


原理

哈夫曼树(Huffman Tree),又称最优二叉树,是一种带权路径长度最短的二叉树,广泛应用于数据压缩领域。所谓树的带权路径长度,是指树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为第0层,叶结点到根结点的路径长度为叶结点的层数)之和。它的核心思想是:权值越大的节点离根越近,权值越小的节点离根越远,从而最小化整体的带权路径长度(WPL)。

关键概念:

  1. 权值(Weight):节点的权重(如字符出现的频率)。

  2. 路径长度:从根节点到某节点的边数。

  3. 带权路径长度(WPL):所有叶子节点的权值 × 路径长度之和。

哈夫曼树的构造基于贪心算法,具体步骤如下:

  1. 初始状态:给定N个权值,将它们视为N棵仅含一个结点的树(森林)。
  2. 选择合并:在森林中选出两个根结点权值最小的树,将它们合并为一棵新树,新树的根结点权值为这两个子树根结点权值之和。
  3. 更新森林:从森林中删除这两个最小的树,并将新树加入森林。
  4. 重复操作:重复步骤2和3,直到森林中只剩下一棵树,这棵树即为所求得的哈夫曼树。

以下是一个简单的哈夫曼树构造过程的图形化展示(假设初始权值为2, 3, 6, 8, 9):

  • 初始状态:五棵独立的树,每棵树的权值分别为2, 3, 6, 8, 9。
  • 第一次合并:选择权值最小的两棵树(权值为2和3),合并成新树,新树的权值为5。
  • 第二次合并:再次选择权值最小的两棵树(此时为权值为5和6的树),合并成新树,新树的权值为11。
  • 后续合并:继续上述过程,直到所有树合并为一棵哈夫曼树。

示例:假设字符集 {A, B, C, D} 的权值分别为 {5, 2, 1, 3},哈夫曼树构建过程如下:

Step 1: 最小权值 C(1) 和 B(2) → 合并为权值3的父节点
Step 2: 新节点3 和 D(3) → 合并为权值6的父节点
Step 3: 合并 A(5) 和 6 → 最终根节点权值11最终哈夫曼树:11/  \5    6/ \3   3/ \ 1   2 (B)(C)

应用场景

  1. 数据压缩:哈夫曼编码(Huffman Coding)将高频字符用短编码,低频字符用长编码。

  2. 文件压缩工具:如 ZIP、GZIP 使用哈夫曼算法。

  3. 图像压缩:JPEG 格式中的熵编码阶段。

  4. 通信协议:优化数据传输效率。

实现步骤

哈夫曼树的实现步骤:

  1. 统计字符频率:遍历数据,统计每个字符的出现次数作为权值。

  2. 构建最小堆:将所有字符节点按权值排序,形成优先队列(最小堆)。

  3. 合并节点:循环取出权值最小的两个节点,合并为新节点,放回堆中。

  4. 生成编码表:从根节点出发,向左为0,向右为1,记录叶子节点的路径编码。

  5. 压缩与解压:根据编码表将原始数据转换为二进制流,或反向解码。

C语言实现

1. 定义哈夫曼树节点结构

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_TREE_NODES 256typedef struct HuffmanNode {char ch;                // 字符(叶子节点有效)int weight;             // 权值(字符频率)struct HuffmanNode *left, *right; // 左右子节点
} HuffmanNode;typedef struct PriorityQueue {HuffmanNode **nodes;    // 节点指针数组int size;               // 当前堆大小int capacity;           // 堆容量
} PriorityQueue;

2. 构建最小堆(优先队列)

// 初始化优先队列
PriorityQueue* createQueue(int capacity) {PriorityQueue* queue = (PriorityQueue*)malloc(sizeof(PriorityQueue));queue->nodes = (HuffmanNode**)malloc(capacity * sizeof(HuffmanNode*));queue->size = 0;queue->capacity = capacity;return queue;
}// 上浮调整(插入节点时保持最小堆性质)
void heapifyUp(PriorityQueue* queue, int index) {int parent = (index - 1) / 2;while (index > 0 && queue->nodes[index]->weight < queue->nodes[parent]->weight) {HuffmanNode* temp = queue->nodes[index];queue->nodes[index] = queue->nodes[parent];queue->nodes[parent] = temp;index = parent;parent = (index - 1) / 2;}
}// 下沉调整(删除节点时保持最小堆性质)
void heapifyDown(PriorityQueue* queue, int index) {int left = 2 * index + 1;int right = 2 * index + 2;int smallest = index;if (left < queue->size && queue->nodes[left]->weight < queue->nodes[smallest]->weight) {smallest = left;}if (right < queue->size && queue->nodes[right]->weight < queue->nodes[smallest]->weight) {smallest = right;}if (smallest != index) {HuffmanNode* temp = queue->nodes[index];queue->nodes[index] = queue->nodes[smallest];queue->nodes[smallest] = temp;heapifyDown(queue, smallest);}
}// 插入节点
void enqueue(PriorityQueue* queue, HuffmanNode* node) {if (queue->size >= queue->capacity) return;queue->nodes[queue->size] = node;heapifyUp(queue, queue->size);queue->size++;
}// 取出权值最小的节点
HuffmanNode* dequeue(PriorityQueue* queue) {if (queue->size == 0) return NULL;HuffmanNode* minNode = queue->nodes[0];queue->nodes[0] = queue->nodes[queue->size - 1];queue->size--;heapifyDown(queue, 0);return minNode;
}

3. 构建哈夫曼树

// 创建叶子节点
HuffmanNode* createLeafNode(char ch, int weight) {HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));node->ch = ch;node->weight = weight;node->left = node->right = NULL;return node;
}// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char data[], int weights[], int n) {PriorityQueue* queue = createQueue(MAX_TREE_NODES);for (int i = 0; i < n; i++) {HuffmanNode* node = createLeafNode(data[i], weights[i]);enqueue(queue, node);}while (queue->size > 1) {HuffmanNode* left = dequeue(queue);HuffmanNode* right = dequeue(queue);HuffmanNode* parent = (HuffmanNode*)malloc(sizeof(HuffmanNode));parent->ch = '\0';  // 内部节点无字符parent->weight = left->weight + right->weight;parent->left = left;parent->right = right;enqueue(queue, parent);}HuffmanNode* root = dequeue(queue);free(queue->nodes);free(queue);return root;
}

4. 生成哈夫曼编码表

void generateCodes(HuffmanNode* root, char* code, int depth, char** codes) {if (root == NULL) return;if (root->left == NULL && root->right == NULL) { // 叶子节点code[depth] = '\0';codes[(unsigned char)root->ch] = strdup(code);return;}code[depth] = '0';generateCodes(root->left, code, depth + 1, codes);code[depth] = '1';generateCodes(root->right, code, depth + 1, codes);
}

5. 压缩与解压示例

// 压缩函数(将字符串转换为哈夫曼编码)
char* compress(char* input, char** codes) {int len = strlen(input);char* compressed = (char*)malloc(MAX_TREE_NODES * len);compressed[0] = '\0';for (int i = 0; i < len; i++) {strcat(compressed, codes[(unsigned char)input[i]]);}return compressed;
}// 解压函数(根据哈夫曼树解码)
void decompress(HuffmanNode* root, char* compressed) {HuffmanNode* current = root;int len = strlen(compressed);for (int i = 0; i < len; i++) {if (compressed[i] == '0') {current = current->left;} else {current = current->right;}if (current->left == NULL && current->right == NULL) {printf("%c", current->ch);current = root; // 重置到根节点继续解码}}
}

6. 测试代码

int main() {char data[] = {'A', 'B', 'C', 'D'};int weights[] = {5, 2, 1, 3};int n = sizeof(data) / sizeof(data[0]);// 构建哈夫曼树HuffmanNode* root = buildHuffmanTree(data, weights, n);// 生成编码表char* codes[MAX_TREE_NODES] = {NULL};char code[MAX_TREE_NODES];generateCodes(root, code, 0, codes);// 打印编码printf("哈夫曼编码表:\n");for (int i = 0; i < MAX_TREE_NODES; i++) {if (codes[i] != NULL) {printf("%c: %s\n", (char)i, codes[i]);}}// 压缩示例char* input = "ABACAD";char* compressed = compress(input, codes);printf("\n原始数据: %s\n压缩后的二进制: %s\n", input, compressed);// 解压示例printf("解压结果: ");decompress(root, compressed);printf("\n");// 释放内存(略)return 0;
}

输出示例

哈夫曼编码表:
A: 0
B: 110
C: 111
D: 10原始数据: ABACAD
压缩后的二进制: 01100111010
解压结果: ABACAD

总结

  • 优点:哈夫曼编码是无损压缩,保证数据完整性。

  • 缺点:需存储编码表,压缩率依赖字符频率分布。

  • 优化方向:动态哈夫曼编码(适应数据变化)、结合其他算法(如LZ77)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/12747.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Vue Dom截图插件,截图转Base64 html2canvas

安装插件 npm install html2canvas --save插件使用 <template><div style"padding: 10px;"><div ref"imageTofile" class"box">发生什么事了</div><button click"toImage" style"margin: 10px;&quo…

C语言:深入了解指针3

1.回调函数是什么&#xff1f; 基本概念 回调函数就是⼀个通过函数指针调⽤的函数。 如果你把函数的指针&#xff08;地址&#xff09;作为参数传递给另⼀个函数&#xff0c;当这个指针被⽤来调⽤其所指向的函数 时&#xff0c;被调⽤的函数就是回调函数。回调函数不是由该函…

llama.cpp GGUF 模型格式

llama.cpp GGUF 模型格式 1. Specification1.1. GGUF Naming Convention (命名规则)1.1.1. Validating Above Naming Convention 1.2. File Structure 2. Standardized key-value pairs2.1. General2.1.1. Required2.1.2. General metadata2.1.3. Source metadata 2.2. LLM2.2.…

【C++】STL——vector底层实现

目录 &#x1f495; 1.vector三个核心 &#x1f495;2.begin函数&#xff0c;end函数的实现&#xff08;简单略讲&#xff09; &#x1f495;3.size函数&#xff0c;capacity函数的实现 &#xff08;简单略讲&#xff09; &#x1f495;4.reserve函数实现 &#xff08;细节…

Pinia状态管理

1、为什么要使用Pinia&#xff1f; Pinia 是 Vue 的存储库&#xff0c;它允许跨组件/页面共享状态 Pinia 最初是为了探索 Vuex 的下一次迭代会是什么样子&#xff0c;结合了 Vuex 5 核心团队讨论中的许多想法。最终&#xff0c;我们意识到 Pinia 已经实现了我们在 Vuex 5 中想…

TCP | RFC793

注&#xff1a;本文为 “ RFC793” 相关文章合辑。 RFC793-TCP 中文翻译 编码那些事儿已于 2022-07-14 16:02:16 修改 简介 翻译自&#xff1a; RFC 793 - Transmission Control Protocol https://datatracker.ietf.org/doc/html/rfc793 TCP 是一个高可靠的主机到主机之间…

VMware Workstation Pro安装了Ubuntu 24.04实现与Windows10之间的复制粘贴

windows10安装了VMware Workstation Pro&#xff0c;虚拟机上安装Ubuntu 24.04&#xff0c;想Ubuntu和windows之间实现复制粘贴&#xff0c;便于互相执行下面命令&#xff1a; sudo apt-get autoremove open-vm-tools //卸载已有的工具 sudo apt-get install open-vm-tools …

idea分析sql性能

idea对sql进行解析&#xff0c;可有效展示sql的性能问题&#xff0c;比直接看命令好。&#xff08;专业版才有数据库功能&#xff0c;可以在淘宝买&#xff0c;10块就好了&#xff09; 如下&#xff1a; 发现一个全表扫描&#xff0c;耗时6s&#xff0c;对应sql语句可以查看&…

智慧园区系统集成解决方案提升管理效率与智能化水平的新探索

内容概要 随着科技的不断进步&#xff0c;智慧园区管理系统已成为现代园区管理的重要组成部分。在众多系统中&#xff0c;快鲸智慧园区(楼宇)管理系统凭借其独特的优势&#xff0c;获得了广泛关注。该系统通过全面整合园区内各类智能设备&#xff0c;大幅提升了管理效率和智能…

Linux 的 sysfs 伪文件系统介绍【用户可以通过文件操作与内核交互(如调用内核函数),而无需编写内核代码】

1. 什么是 sysfs伪文件系统&#xff1f; sysfs 是 Linux 内核提供的 伪文件系统&#xff0c;用于向用户空间暴露内核对象的信息和控制接口。它是 procfs 的补充&#xff0c;主要用于管理 设备、驱动、内核子系统 等信息&#xff0c;使用户可以通过文件操作&#xff08;如用户空…

TCP编程

1.socket函数 int socket(int domain, int type, int protocol); 头文件&#xff1a;include<sys/types.h>&#xff0c;include<sys/socket.h> 参数 int domain AF_INET: IPv4 Internet protocols AF_INET6: IPv6 Internet protocols AF_UNIX, AF_LOCAL : Local…

springboot+vue+uniapp的校园二手交易小程序

开发语言&#xff1a;Java框架&#xff1a;springbootuniappJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#…

【PyQt】使用PyQt5和Matplotlib实现的CSV数据可视化工具

使用PyQt5和Matplotlib实现的CSV数据可视化工具 界面展示 代码 import sys from PyQt5.QtWidgets import (QApplication, QMainWindow, QWidget, QVBoxLayout,QHBoxLayout, QPushButton, QComboBox, QFileDialog,QLabel, QMessageBox) import pandas as pd from matplotlib.f…

软件工程导论三级项目报告--《软件工程》课程网站

《软件工程》课程网站 摘要 本文详细介绍了《软件工程》课程网站的设计与实现方案&#xff0c;包括可行性分析、需求分析、总体设计、详细设计、测试用例。首先&#xff0c;通过可行性分析从各方面确认了该工程的可实现性&#xff0c;接着需求分析明确了系统的目标用户群和功能…

数据结构-堆和PriorityQueue

1.堆&#xff08;Heap&#xff09; 1.1堆的概念 堆是一种非常重要的数据结构&#xff0c;通常被实现为一种特殊的完全二叉树 如果有一个关键码的集合K{k0,k1,k2,...,kn-1}&#xff0c;把它所有的元素按照完全二叉树的顺序存储在一个一维数组中&#xff0c;如果满足ki<k2i…

Spring @Lazy:延迟初始化,为应用减负

在Spring框架中&#xff0c;Lazy注解的作用非常直观&#xff0c;它就是用来告诉Spring容器&#xff1a;“嘿&#xff0c;这个Bean嘛&#xff0c;先别急着创建和初始化&#xff0c;等到真正需要用到的时候再弄吧&#xff01;” 默认情况下&#xff0c;Spring容器在启动时会立即创…

SynchronousQueue 与 LinkedBlockingQueue区别及应用场景

文章目录 前言认识SynchronousQueue基本对比及比较1. **基本特性**2. **内部实现**3. **性能特点**4. **使用场景**5. **总结对比** SynchronousQueue案例JDK应用案例案例1&#xff1a;SynchronousQueue的简单用例案例2&#xff1a;SynchronousQueue公平锁、非公平锁案例案例3&…

MySQL 缓存机制与架构解析

目录 一、MySQL缓存机制概述 二、MySQL整体架构 三、SQL查询执行全流程 四、MySQL 8.0为何移除查询缓存&#xff1f; 五、MySQL 8.0前的查询缓存配置 六、替代方案&#xff1a;应用层缓存与优化建议 总结 一、MySQL缓存机制概述 MySQL的缓存机制旨在提升数据访问效率&am…

【C++】STL——list的使用

目录 &#x1f495;1.带头双向链表List &#x1f495;2.list用法介绍 &#x1f495;3.list的初始化 &#x1f495;4.size函数与resize函数 &#x1f495;5.empty函数 &#x1f495;6.front函数与back函数 &#x1f495;7.push_front,push_back,pop_front,pop_back函数…

MySQL知识点总结(一)

1.SQL分类 数据定义&#xff08;DDL&#xff09;:创/改/删/名/清&#xff08;cadrt&#xff09; 数据库对象&#xff1a;表/视图/存储/函数/触发器/事件 数据操作&#xff08;DML&#xff09;&#xff1a;增/删/改/查&#xff08;idus&#xff09; 操作数据库对象 数据控制&…