房地产集团网站建设方案,网页设计与制作课程设计报告书,国内crm系统十大排名,wordpress远程发布XML哈夫曼编码#xff08;Huffman Coding#xff09; 是一种基于字符出现频率的无损数据压缩算法#xff0c;通过构建哈夫曼树#xff08;Huffman Tree#xff09; 来生成最优前缀编码#xff0c;使得高频字符用短编码#xff0c;低频字符用长编码#xff0c;从而实现高效…哈夫曼编码Huffman Coding 是一种基于字符出现频率的无损数据压缩算法通过构建哈夫曼树Huffman Tree 来生成最优前缀编码使得高频字符用短编码低频字符用长编码从而实现高效压缩。 1. 哈夫曼树Huffman Tree
定义哈夫曼树是一棵带权路径长度WPL最小的二叉树。 权值字符的出现频率或概率。带权路径长度每个叶子节点的权值 × 其到根节点的路径长度之和。 特点 没有度为1的节点严格的二叉树。频率越高的字符离根越近编码越短。
构建哈夫曼树的步骤
统计字符频率为每个字符赋予权值频率。创建节点集合每个字符作为一个叶子节点组成初始森林。合并最小权值节点 每次选择权值最小的两个节点合并成一个新父节点权值为两者之和。重复合并直到只剩一棵树。 生成编码从根到叶子的路径左分支为 0右分支为 1或相反。
示例 假设字符 A(5), B(9), C(12), D(13), E(16), F(45) 构建过程如下
初始节点集合5, 9, 12, 13, 16, 45合并最小的 5 和 9 → 新节点 14合并 12 和 13 → 新节点 25合并 14 和 16 → 新节点 30合并 25 和 30 → 新节点 55合并 45 和 55 → 根节点 100 最终哈夫曼树结构如下 (100)/ \F(45) (55)/ \(25) (30)/ \ / \C(12) D(13)(14) E(16)/ \A(5) B(9)2. 哈夫曼编码Huffman Coding
规则从根到叶子节点的路径生成二进制编码。 左分支为 0右分支为 1或相反。 示例基于上述哈夫曼树 F(45) → 0C(12) → 100D(13) → 101A(5) → 1100B(9) → 1101E(16) → 111
编码特点
前缀码Prefix Code任何字符的编码都不是其他编码的前缀避免解码歧义。最优性在所有前缀码中哈夫曼编码的压缩效率最高WPL最小。 3. 哈夫曼编码的压缩与解压
压缩过程
统计字符频率构建哈夫曼树。生成字符到二进制编码的映射表。将原始数据替换为哈夫曼编码的二进制流。
解压过程
根据哈夫曼树或编码表从二进制流中逐位解码。从根节点开始根据 0/1 向左/右子树移动直到到达叶子节点输出对应字符。 4. 代码实现C 示例
#include iostream
#include queue
#include unordered_map
using namespace std;// 哈夫曼树节点
struct Node {char ch;int freq;Node *left, *right;Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};// 优先队列的比较器按频率升序
struct Compare {bool operator()(Node* a, Node* b) {return a-freq b-freq;}
};// 构建哈夫曼树
Node* buildHuffmanTree(const unordered_mapchar, int freqMap) {priority_queueNode*, vectorNode*, Compare pq;for (auto pair : freqMap) {pq.push(new Node(pair.first, pair.second));}while (pq.size() 1) {Node* left pq.top(); pq.pop();Node* right pq.top(); pq.pop();Node* parent new Node(\0, left-freq right-freq);parent-left left;parent-right right;pq.push(parent);}return pq.top();
}// 生成编码表
void generateCodes(Node* root, string code, unordered_mapchar, string codes) {if (!root) return;if (root-ch ! \0) {codes[root-ch] code;return;}generateCodes(root-left, code 0, codes);generateCodes(root-right, code 1, codes);
}int main() {unordered_mapchar, int freqMap {{A,5}, {B,9}, {C,12}, {D,13}, {E,16}, {F,45}};Node* root buildHuffmanTree(freqMap);unordered_mapchar, string codes;generateCodes(root, , codes);for (auto pair : codes) {cout pair.first : pair.second endl;}return 0;
}5. 应用场景
文件压缩如 ZIP、GZIP、JPEG、MP3 等格式。数据传输减少带宽占用。数据库存储压缩文本字段。 6. 优缺点
优点 无损压缩解压后数据完全恢复。对高频字符优化压缩效率高。 缺点 需要存储哈夫曼树或编码表可能增加额外开销。不适合字符频率分布均匀的场景。 总结
哈夫曼编码通过构建最优二叉树实现高效压缩是经典的数据压缩算法之一。理解其核心思想贪心算法和实现步骤构建树、生成编码是掌握数据压缩技术的基础。 练一练 答案B 答案A
