尧图网页设计 
1. 从“压缩”说起为什么赫夫曼树是数据压缩的基石如果你处理过文件尤其是那些文本、日志或者配置文件一定对“压缩”这个概念不陌生。右键点击一个文件选择“添加到压缩文件”文件体积瞬间变小这个过程看似魔法背后却是一套严谨的数学和计算机科学理论在支撑。而在这套理论中赫夫曼树扮演着核心角色。它不像快速排序那样广为人知也不像哈希表那样频繁出现在面试题里但它是构建高效、无损压缩算法如DEFLATE即ZIP、GZIP等格式的核心的绝对基础。简单来说赫夫曼树解决的是一个“编码效率”问题。想象一下你要给一篇文章里的每个字母分配一个二进制编码。最朴素的想法是等长编码比如用5位二进制数可以表示32种字符给26个字母编码。但文章里‘e’和‘t’出现的频率远高于‘z’和‘q’。如果给高频字母如‘e’分配更短的编码给低频字母如‘z’分配更长的编码整篇文章的二进制总长度就能显著缩短。赫夫曼树就是用来生成这种“最优前缀码”的完美工具——它确保没有任何一个字符的编码是另一个字符编码的前缀从而保证了解码时的唯一性同时使得整体的编码长度最短。今天我们就抛开教科书上抽象的图示和证明用C手把手实现一棵赫夫曼树并完成一个简易的文本文件压缩/解压程序。你会看到从一堆字符频率到一棵树再到最终的压缩比特流每一个步骤如何用代码清晰地表达出来。更重要的是我会分享在实现过程中那些容易踩坑的细节比如内存管理、二进制位操作、文件I/O的边界处理这些才是将理论转化为可靠代码的关键。2. 赫夫曼树的核心原理贪心策略与最优前缀码要理解赫夫曼树必须先吃透两个核心概念贪心算法和前缀码。2.1 前缀码无歧义解码的保证前缀码是一种编码方式其中任何一个字符的编码都不是另一个字符编码的前缀。举个例子假设我们为 {A, B, C, D} 设计编码。非前缀码有问题的A0, B00, C1, D01。当你收到比特流“00”时你无法确定它是两个A0, 0还是一个B00。这就是歧义。前缀码正确的A0, B10, C110, D111。注意0不是10、110、111的前缀10不是110、111的前缀以此类推。对于比特流“010110”我们可以唯一地解码为 A(0), B(10), C(110)。赫夫曼树天然生成的就是前缀码。从树根到每个叶子节点的路径左走为0右走为1形成的编码必然满足前缀性质因为每个字符都位于叶子节点路径互不包含。2.2 贪心算法自底向上构建最优树赫夫曼树的构建过程是一个经典的贪心算法应用。它的目标是给定n个字符及其出现频率或权重构造一棵二叉树使得所有字符的带权路径长度最小。带权路径长度树中所有叶子节点的权重 × 该节点到根的路径长度之和。路径长度就是编码的位数。我们的目标就是最小化这个和即最小化总的编码长度。算法步骤这是你必须内化的逻辑初始化将每个字符看作一棵只有根节点的二叉树其权重即为频率。将这n棵树放入一个优先队列最小堆中。循环合并当堆中树的数量大于1时 a. 从堆中弹出权重最小的两棵树比如T1和T2。 b. 创建一棵新树TT的根节点权重 T1权重 T2权重。T的左子树为T1右子树为T2。 c. 将新树T放回堆中。结束堆中剩下的最后一棵树就是赫夫曼树。为什么这是“贪心”的因为在每一步我们都只做当前看起来最优的选择合并当前权重最小的两棵树。神奇的是这个局部最优的选择序列最终能导致全局最优解即带权路径长度最小。这是需要证明的但作为实现者我们首先需要相信并严格遵循这个过程。2.3 一个简单的例子假设有字符集 {A, B, C, D}频率分别为 {5, 1, 6, 3}。初始堆(B:1), (D:3), (A:5), (C:6)。弹出B和D合并为新树T1(权重4)。堆变为(T1:4), (A:5), (C:6)。弹出T1和A合并为新树T2(权重9)。堆变为(T2:9), (C:6)。弹出T2和C合并为新树T3(权重15)。这就是最终的赫夫曼树。从这棵树可以得到编码假设左0右1A: 可能是11取决于合并时左右顺序但长度固定B:100C:0D:101你可以计算一下使用这种编码的总比特数会比等长编码每个字符2位要少。3. C实现从节点定义到树构建理论清晰后我们开始用C实现。我们将整个过程模块化便于理解和调试。3.1 数据结构设计HuffmanNode树的节点是基础。我们需要区分叶子节点存字符和内部节点只存权重和左右孩子。#include cstdint // 用于uint8_t, uint32_t等明确大小的类型 #include memory // 用于智能指针简化内存管理 struct HuffmanNode { uint8_t ch; // 字符仅叶子节点有效。使用uint8_t表示0-255的字节。 uint32_t freq; // 权重频率 std::shared_ptrHuffmanNode left; // 左孩子 std::shared_ptrHuffmanNode right; // 右孩子 // 构造函数 HuffmanNode(uint8_t c, uint32_t f) : ch(c), freq(f), left(nullptr), right(nullptr) {} HuffmanNode(uint32_t f, std::shared_ptrHuffmanNode l, std::shared_ptrHuffmanNode r) : ch(0), freq(f), left(l), right(r) {} // 判断是否为叶子节点 bool isLeaf() const { return left nullptr right nullptr; } }; // 比较器用于优先队列最小堆 struct CompareNode { bool operator()(const std::shared_ptrHuffmanNode a, const std::shared_ptrHuffmanNode b) const { // 频率小的优先级高。如果频率相同可以定义额外规则如按字符保证确定性此处简化。 return a-freq b-freq; } };注意这里使用了std::shared_ptr智能指针。在赫夫曼树构建中节点会被多个父节点引用虽然最终树是唯一的但构建过程中临时节点可能被共享使用shared_ptr可以自动管理内存避免手动new/delete带来的内存泄漏风险尤其是在异常发生时。这是现代C推荐的做法。3.2 统计频率buildFrequencyTable压缩的第一步是扫描源文件统计每个字节0-255出现的次数。#include fstream #include vector #include array using FrequencyTable std::arrayuint32_t, 256; // 使用std::array大小固定为256 FrequencyTable buildFrequencyTable(const std::string inputFilename) { FrequencyTable freq {0}; // 初始化为全0 std::ifstream inFile(inputFilename, std::ios::binary); // 必须以二进制模式打开 if (!inFile.is_open()) { throw std::runtime_error(无法打开输入文件: inputFilename); } char byte; while (inFile.get(byte)) { // 将读取的char转换为无符号整数作为数组索引 freq[static_castunsigned char(byte)]; } // 处理一个特殊情况如果文件只有一个字符频率表只有一项非零。 // 赫夫曼树至少需要两个节点才能构建我们需要特殊处理。这里先忽略后面构建树时会处理。 return freq; }踩坑点1二进制模式打开文件。如果不使用std::ios::binary在Windows平台上读取文件时\r\n会被转换成\n导致统计的频率和实际字节不符压缩和解压必然失败。这是文件I/O操作中非常经典的坑。3.3 构建赫夫曼树buildHuffmanTree这是算法的核心。我们使用std::priority_queue作为最小堆。#include queue #include memory std::shared_ptrHuffmanNode buildHuffmanTree(const FrequencyTable freq) { // 定义最小堆 std::priority_queuestd::shared_ptrHuffmanNode, std::vectorstd::shared_ptrHuffmanNode, CompareNode minHeap; // 1. 初始化为每个频率0的字符创建叶子节点加入堆中 for (int i 0; i 256; i) { if (freq[i] 0) { minHeap.push(std::make_sharedHuffmanNode(static_castuint8_t(i), freq[i])); } } // 处理边界情况空文件或只有一个字符的文件 if (minHeap.empty()) { return nullptr; // 空树 } if (minHeap.size() 1) { // 只有一个字符需要构造一个虚拟的根节点让这个字符成为左孩子或右孩子。 // 否则编码长度为0无法解码。 auto singleNode minHeap.top(); minHeap.pop(); // 创建一个新的根节点左孩子是该字符节点右孩子为空或一个虚拟节点。 // 更常见的做法是让这个唯一字符的编码为“0”或“1”。 auto pseudoRoot std::make_sharedHuffmanNode(singleNode-freq, singleNode, nullptr); // 注意这里右孩子是nullptr解码时需要特殊处理。一个更健壮的做法是创建两个相同的节点合并。 // 我们采用另一种方法如果只有一个字符我们仍然创建一个内部节点其左右孩子都是这个字符节点但频率翻倍。 // 这样编码长度至少为1。 auto root std::make_sharedHuffmanNode(singleNode-freq * 2, singleNode, singleNode); return root; } // 2. 循环合并 while (minHeap.size() 1) { // 弹出两个权重最小的节点 auto left minHeap.top(); minHeap.pop(); auto right minHeap.top(); minHeap.pop(); // 创建新内部节点权重为子节点之和 uint32_t sumFreq left-freq right-freq; auto parent std::make_sharedHuffmanNode(sumFreq, left, right); // 将新节点加入堆中 minHeap.push(parent); } // 3. 堆中剩下的最后一个节点就是根节点 return minHeap.top(); }踩坑点2单一字符文件的处理。这是实现中极易忽略的边界情况。如果文件只有一个字符比如全是‘A’那么频率表中只有一项非零。按照标准算法堆中只有一个节点不会进入合并循环。这将导致生成的赫夫曼树只有一个叶子节点其编码长度为0。在压缩时你无法写入任何比特来代表这个字符解压时你看到空比特流也无法知道该解码成什么。因此必须特殊处理强制让这个唯一字符的编码长度至少为1。上面的代码展示了一种处理方法创建左右孩子相同的伪根你也可以选择在编码阶段如果发现编码表为空或只有一项时手动分配一个固定编码如“0”。4. 生成编码表与序列化树结构有了赫夫曼树我们需要遍历它来得到每个字符对应的二进制编码一个由‘0’和‘1’组成的字符串同时为了解压我们必须将树的结构也保存到压缩文件中。4.1 生成编码表generateCodes通过深度优先遍历DFS赫夫曼树我们可以生成编码表。#include string #include unordered_map using CodeTable std::unordered_mapuint8_t, std::string; void generateCodesHelper(const std::shared_ptrHuffmanNode node, const std::string code, CodeTable table) { if (!node) return; // 如果是叶子节点记录编码 if (node-isLeaf()) { // 注意对于只有一个字符的特殊树同一个字符可能出现在两个叶子 // 在我们之前的处理中对于单字符文件我们创建了一个左右孩子指向同一个节点的树。 // 这个节点会被访问两次左和右生成两个编码如0和1。 // 我们需要在调用此函数前或函数内处理这种情况确保一个字符只对应一个编码。 // 简单处理如果表中已存在该字符的编码则不覆盖或选择更短的。 // 更好的方法是在构建单字符树时就避免这种情况。我们调整buildHuffmanTree // 对于单字符创建一个新节点作为根其左孩子是字符节点右孩子是一个虚拟的、频率为0的空节点。 // 这样字符节点只会被访问一次。 if (table.find(node-ch) table.end()) { // 如果尚未记录 table[node-ch] code.empty() ? 0 : code; // 如果code为空即根就是叶子赋一个默认编码0 } } else { // 递归遍历左子树和右子树 if (node-left) { generateCodesHelper(node-left, code 0, table); } if (node-right) { generateCodesHelper(node-right, code 1, table); } } } CodeTable generateCodes(const std::shared_ptrHuffmanNode root) { CodeTable table; if (root) { // 处理单节点树的特殊情况 if (root-isLeaf()) { // 根节点本身就是叶子这意味着文件只有一个字符且我们之前没有创建伪根。 // 我们在这里赋予它一个固定编码0。 table[root-ch] 0; } else { generateCodesHelper(root, , table); } } return table; }4.2 序列化赫夫曼树serializeTree为了解压我们必须将树的结构保存到压缩文件中。我们不能只保存编码表因为解码时需要树来指导比特流的遍历。一个经典的方法是使用前序遍历并用特殊标记来区分内部节点和叶子节点。约定遇到叶子节点写入一个1比特紧接着写入该字符的8个比特一个字节。遇到内部节点写入一个0比特。这个过程需要按比特写入比较繁琐。我们这里先实现一个将树序列化为字符串‘0’/‘1’和字符的函数实际写入文件时再处理比特。#include sstream void serializeTreeHelper(const std::shared_ptrHuffmanNode node, std::ostringstream oss) { if (!node) return; if (node-isLeaf()) { oss.put(1); // 用字符1表示叶子节点 oss.put(node-ch); // 写入字符本身 } else { oss.put(0); // 用字符0表示内部节点 serializeTreeHelper(node-left, oss); serializeTreeHelper(node-right, oss); } } std::string serializeTree(const std::shared_ptrHuffmanNode root) { std::ostringstream oss; serializeTreeHelper(root, oss); return oss.str(); }这样序列化后的字符串就包含了完整的树结构信息。例如一个简单的树根为内部节点左右孩子分别是叶子节点‘A’和‘B’会被序列化为0 1 A 1 B空格仅为示意。注意这种序列化方法会占用额外空间但对于小文件或非极端情况开销是可接受的。更紧凑的序列化方式可以使用位操作但实现更复杂。我们优先保证清晰正确。5. 压缩过程从字符到比特流这是最激动人心也最易出错的一步。我们需要将序列化的树写入输出文件。再次读取源文件根据编码表将每个字符替换成对应的比特串。将这些比特串按顺序拼接每凑满8个比特一个字节就写入文件。处理最后一个可能不足8比特的字节。5.1 按比特写入的辅助类BitOutputStreamC标准库的ostream只支持按字节写入。我们需要一个包装类支持累积比特凑整后写入。class BitOutputStream { private: std::ofstream out; // 底层输出流 unsigned char buffer; // 8位缓冲区 int bitsInBuffer; // 当前缓冲区中已累积的比特数 public: explicit BitOutputStream(std::ofstream os) : out(os), buffer(0), bitsInBuffer(0) {} // 写入单个比特 (0 或 1) void writeBit(int bit) { if (bit ! 0 bit ! 1) { throw std::invalid_argument(Bit must be 0 or 1); } // 将比特放到缓冲区的最高位或最低位这里我们选择放到缓冲区的最高位从左到右填充。 // 假设buffer初始为0 bitsInBuffer0。 // 写入第一个比特1 buffer 1000 0000, bitsInBuffer1。 // 写入第二个比特0 buffer 1000 0000 | (0 (7-1)) 1000 0000, bitsInBuffer2。 // 更直观的做法是放到最低位然后左移。 // 我们采用buffer左移1位然后与新bit进行或操作。 buffer (buffer 1) | static_castunsigned char(bit); bitsInBuffer; if (bitsInBuffer 8) { flush(); // 缓冲区满写入文件 } } // 写入一个字符串形式的比特序列如 10110 void writeBits(const std::string bits) { for (char b : bits) { if (b 0) writeBit(0); else if (b 1) writeBit(1); else throw std::invalid_argument(Invalid bit character); } } // 强制将缓冲区内容写入文件可能不足8位并在末尾补0。 // 解压时需要知道补了多少位所以通常我们会先写入原始数据的比特总数或者在这里记录补位数。 // 我们采用另一种常见方法在最后一个字节将有效比特左移到该字节的高位解压时根据编码树自然停止。 // 但更可靠的方法是在文件开头写入一个“补位数”字节。 void flush() { if (bitsInBuffer 0) { // 将缓冲区中已有的比特左移使其位于字节的高位低位补0。 buffer (8 - bitsInBuffer); out.put(buffer); buffer 0; bitsInBuffer 0; } } // 析构时自动flush ~BitOutputStream() { flush(); } };5.2 完整的压缩函数compress现在我们将所有步骤串联起来。#include fstream #include iostream void compress(const std::string inputFilename, const std::string outputFilename) { // 1. 构建频率表 FrequencyTable freq buildFrequencyTable(inputFilename); // 2. 构建赫夫曼树 auto root buildHuffmanTree(freq); if (!root) { std::cerr 输入文件为空无需压缩。 std::endl; return; } // 3. 生成编码表 CodeTable codes generateCodes(root); // 4. 序列化树 std::string serializedTree serializeTree(root); // 5. 打开输出文件二进制模式 std::ofstream outFile(outputFilename, std::ios::binary); if (!outFile.is_open()) { throw std::runtime_error(无法打开输出文件: outputFilename); } // 6. 写入压缩文件头部信息可选但很重要 // 通常包括魔数标识文件类型、原始文件大小、树序列化数据的大小等。 // 这里我们简化先写入序列化树的大小4字节再写入树数据本身。 uint32_t treeSize static_castuint32_t(serializedTree.size()); outFile.write(reinterpret_castconst char*(treeSize), sizeof(treeSize)); outFile.write(serializedTree.data(), treeSize); // 7. 再次打开输入文件进行编码压缩 std::ifstream inFile(inputFilename, std::ios::binary); BitOutputStream bitOut(outFile); // 创建比特输出流 char byte; while (inFile.get(byte)) { uint8_t ch static_castunsigned char(byte); auto it codes.find(ch); if (it codes.end()) { // 理论上不会发生因为编码表来自频率表 throw std::runtime_error(发现未编码字符); } bitOut.writeBits(it-second); // 写入该字符对应的比特串 } // 8. BitOutputStream析构时会自动flush将最后不足8位的缓冲区写入。 // 但我们还需要告诉解压方“有效数据到此为止”否则会多读。 // 一个简单方法在flush后再额外写入一个字节标明最后一个有效字节中有多少位是真实的。 // 我们在flush后再写入bitsInBuffer实际在flush后它为0。 // 我们需要修改BitOutputStream在flush前记录这个数字。 // 为了简化我们采用另一种策略在文件开头也写入原始数据的比特总数。这里先不实现。 // 对于学习目的我们假设解码时能通过树正确终止当解码出的字符数等于原文件字符数时停止。 // 这要求我们在文件头也写入原始文件的字符总数或字节数。 std::cout 压缩完成。输出文件: outputFilename std::endl; }踩坑点3文件头信息与解码终止。这是实现压缩解压程序最关键的细节之一。解压器需要知道三件事1) 赫夫曼树的结构2) 压缩后的比特流从哪里开始3) 比特流在哪里结束即哪些比特是有效数据哪些是填充的0。我们的实现中树结构及其大小已经写入。但比特流的结束位置是模糊的。因为最后一个字节可能只有部分比特是有效的BitOutputStream::flush()会用0补足。如果解压器一直读它会把这些填充的0也当作编码来解析导致错误。解决方案在文件头额外存储原始数据的字节数或字符数。解压时每解码出一个字符计数器加一当解码字符数等于原始字符数时立即停止忽略后面可能存在的填充比特。这是最常用、最可靠的方法。我们需要修改压缩函数在写入树数据后再写入原始文件的大小uint32_t originalSize。这部分代码的补充将在解压部分体现。6. 解压过程从比特流重建数据解压是压缩的逆过程从压缩文件头部读取树结构信息反序列化重建赫夫曼树。读取后续的比特流。从树根开始根据比特流中的每一位0向左1向右遍历赫夫曼树到达叶子节点时输出对应的字符。重复步骤3直到解码出预定数量的字符由头部信息给出。6.1 按比特读取的辅助类BitInputStream与BitOutputStream对应我们需要一个能按比特读取文件的类。class BitInputStream { private: std::ifstream in; unsigned char buffer; // 当前字节 int bitsInBuffer; // 当前字节中剩余未读的比特数 bool isEof; // 是否已到达文件末尾底层流 // 从文件中读取下一个字节到缓冲区 void fillBuffer() { if (isEof) { buffer 0; bitsInBuffer 0; return; } char byte; if (in.get(byte)) { buffer static_castunsigned char(byte); bitsInBuffer 8; } else { isEof true; buffer 0; bitsInBuffer 0; } } public: explicit BitInputStream(std::ifstream is) : in(is), buffer(0), bitsInBuffer(0), isEof(false) { fillBuffer(); // 预读第一个字节 } // 读取一个比特如果文件结束返回-1 int readBit() { if (bitsInBuffer 0) { if (isEof) return -1; fillBuffer(); if (bitsInBuffer 0) return -1; // 填充后仍然为空说明文件已读完 } // 从buffer的最高位开始取比特 int bit (buffer (bitsInBuffer - 1)) 1; bitsInBuffer--; return bit; } // 判断是否还有比特可读包括缓冲区中的和文件中未读的 bool good() const { return !isEof || bitsInBuffer 0; } };6.2 反序列化赫夫曼树deserializeTree根据之前序列化的规则‘0’内部节点‘1’叶子节点后跟一个字节字符从比特流中重建树。注意我们现在是从一个std::string或直接按字节读取来重建而不是从BitInputStream读因为树结构数据是按字节对齐存储的。#include istream #include memory std::shared_ptrHuffmanNode deserializeTreeHelper(std::istream in) { char flag; if (!in.get(flag)) { return nullptr; // 读取失败 } if (flag 1) { // 叶子节点 char ch; if (!in.get(ch)) { throw std::runtime_error(反序列化树失败期望字符数据); } return std::make_sharedHuffmanNode(static_castuint8_t(ch), 0); // 频率在解压时无用设为0 } else if (flag 0) { // 内部节点 auto left deserializeTreeHelper(in); auto right deserializeTreeHelper(in); // 内部节点的频率在解压时也无用设为0 return std::make_sharedHuffmanNode(0, left, right); } else { throw std::runtime_error(反序列化树失败无效的标志位); } } std::shared_ptrHuffmanNode deserializeTree(const std::string treeStr) { std::istringstream iss(treeStr); return deserializeTreeHelper(iss); }6.3 完整的解压函数decompress现在实现解压主函数并加入之前提到的文件头信息树大小、原始数据大小。void decompress(const std::string inputFilename, const std::string outputFilename) { std::ifstream inFile(inputFilename, std::ios::binary); if (!inFile.is_open()) { throw std::runtime_error(无法打开压缩文件: inputFilename); } // 1. 读取树的大小 uint32_t treeSize 0; if (!inFile.read(reinterpret_castchar*(treeSize), sizeof(treeSize))) { throw std::runtime_error(读取树大小失败); } // 2. 读取序列化树的字符串数据 std::vectorchar treeData(treeSize); if (!inFile.read(treeData.data(), treeSize)) { throw std::runtime_error(读取树数据失败); } std::string treeStr(treeData.begin(), treeData.end()); // 3. 反序列化重建赫夫曼树 auto root deserializeTree(treeStr); if (!root) { throw std::runtime_error(重建赫夫曼树失败); } // 4. 读取原始数据大小我们在压缩时应该写入现在假设它存在 // 修改压缩函数在写入树数据后写入原始文件的字节数。 // 我们这里先读取它。 uint32_t originalDataSize 0; // 原始文件的字节数 if (!inFile.read(reinterpret_castchar*(originalDataSize), sizeof(originalDataSize))) { throw std::runtime_error(读取原始数据大小失败); } // 5. 打开输出文件 std::ofstream outFile(outputFilename, std::ios::binary); if (!outFile.is_open()) { throw std::runtime_error(无法打开输出文件: outputFilename); } // 6. 使用BitInputStream读取后续的压缩比特流 BitInputStream bitIn(inFile); auto currentNode root; uint32_t decodedCount 0; while (decodedCount originalDataSize) { int bit bitIn.readBit(); if (bit -1) { // 比特流提前结束可能文件损坏 throw std::runtime_error(压缩数据不完整或已损坏); } // 根据比特遍历树 if (bit 0) { if (currentNode-left) { currentNode currentNode-left; } else { throw std::runtime_error(无效的压缩数据比特流与树结构不匹配); } } else { // bit 1 if (currentNode-right) { currentNode currentNode-right; } else { throw std::runtime_error(无效的压缩数据比特流与树结构不匹配); } } // 如果到达叶子节点输出字符并重置到根节点 if (currentNode-isLeaf()) { outFile.put(static_castchar(currentNode-ch)); decodedCount; currentNode root; // 回到根节点准备解码下一个字符 } } // 7. 解码字符数已达到原始大小停止。忽略后面可能存在的填充比特。 std::cout 解压完成。输出文件: outputFilename std::endl; }相应地我们需要修改压缩函数compress在写入树数据后写入原始文件的大小。// 在compress函数中写入树数据之后写入原始文件大小 // ... 写入treeSize和serializedTree ... // 获取原始文件大小字节数 inFile.clear(); // 清除可能的eof状态 inFile.seekg(0, std::ios::end); uint32_t originalSize static_castuint32_t(inFile.tellg()); inFile.seekg(0, std::ios::beg); // 重置文件指针准备重新读取数据 // 写入原始文件大小 outFile.write(reinterpret_castconst char*(originalSize), sizeof(originalSize)); // 然后继续创建BitOutputStream并进行编码...踩坑点4文件指针与重复读取。在压缩函数中我们两次打开或读取输入文件一次统计频率一次进行编码。第二次读取前必须将文件指针重置到开头inFile.seekg(0, std::ios::beg)。同时在获取文件大小后也要重置指针。忘记重置是常见的错误会导致第二次读取不到任何数据。7. 测试、局限性与扩展思考7.1 如何测试编写一个简单的main函数来测试压缩和解压int main() { std::string inputFile test.txt; std::string compressedFile test.huff; std::string decompressedFile test_decompressed.txt; try { // 压缩 compress(inputFile, compressedFile); std::cout 压缩成功。 std::endl; // 解压 decompress(compressedFile, decompressedFile); std::cout 解压成功。 std::endl; // 验证比较原始文件和解压后的文件是否一致 // 可以使用系统命令如fc(Windows)或diff(Linux/Mac)或者写代码逐字节比较。 std::ifstream orig(inputFile, std::ios::binary); std::ifstream decomp(decompressedFile, std::ios::binary); bool identical true; char c1, c2; while (orig.get(c1) decomp.get(c2)) { if (c1 ! c2) { identical false; break; } } // 检查是否都同时到达文件末尾 if (orig.good() ! decomp.good()) { identical false; } if (identical) { std::cout 验证通过解压文件与原始文件完全一致。 std::endl; } else { std::cout 验证失败文件内容不一致 std::endl; } } catch (const std::exception e) { std::cerr 错误: e.what() std::endl; return 1; } return 0; }7.2 本实现的局限性内存与效率我们一次性将整个树序列化成字符串对于包含大量不同字符的文件树可能很大。实际工业级实现如zlib会使用更紧凑的规范赫夫曼树表示法。文件头开销我们存储了整棵树的序列化表示和原始文件大小。对于非常小的文件头信息可能比压缩后的数据还大导致“负压缩”。仅支持字节流我们的实现针对的是二进制字节流0-255。对于纯文本文件可以考虑使用ASCII或UTF-8但原理相同。无分块处理对于大文件一次性统计频率可能内存占用高。实际中可采用自适应赫夫曼编码或分块处理。无错误恢复文件损坏或格式不对时程序会直接崩溃。健壮的程序应加入更多的错误检查和恢复机制。7.3 扩展思考从赫夫曼到DEFLATE真正的ZIP、GZIP、PNG等格式使用的DEFLATE算法是赫夫曼编码的加强版。它主要做了两件事LZ77滑动窗口压缩先通过查找重复字符串并用距离长度对替换消除文件中的冗余。赫夫曼编码对LZ77处理后的输出包含字面量字节、距离、长度信息进行赫夫曼编码。并且它使用了两棵赫夫曼树一棵用于字面量/长度另一棵用于距离。此外DEFLATE使用了规范赫夫曼码它不存储整棵树而是只存储每个编码长度的符号数量从而极大地减少了树结构信息的开销。这是赫夫曼编码在工程实践上的一个重要优化方向。实现一个完整的DEFLATE压缩器是庞大的工程但理解了我们今天手写的赫夫曼压缩解压全过程你就已经握住了打开无损压缩世界大门的钥匙。下次当你再点击“压缩文件”时你看到的将不再是一个黑盒而是一棵棵优雅的二叉树在比特的海洋里高效地排列组合。 C++手把手实现赫夫曼树：从贪心算法到文件压缩实战
1. 从“压缩”说起为什么赫夫曼树是数据压缩的基石如果你处理过文件尤其是那些文本、日志或者配置文件一定对“压缩”这个概念不陌生。右键点击一个文件选择“添加到压缩文件”文件体积瞬间变小这个过程看似魔法背后却是一套严谨的数学和计算机科学理论在支撑。而在这套理论中赫夫曼树扮演着核心角色。它不像快速排序那样广为人知也不像哈希表那样频繁出现在面试题里但它是构建高效、无损压缩算法如DEFLATE即ZIP、GZIP等格式的核心的绝对基础。简单来说赫夫曼树解决的是一个“编码效率”问题。想象一下你要给一篇文章里的每个字母分配一个二进制编码。最朴素的想法是等长编码比如用5位二进制数可以表示32种字符给26个字母编码。但文章里‘e’和‘t’出现的频率远高于‘z’和‘q’。如果给高频字母如‘e’分配更短的编码给低频字母如‘z’分配更长的编码整篇文章的二进制总长度就能显著缩短。赫夫曼树就是用来生成这种“最优前缀码”的完美工具——它确保没有任何一个字符的编码是另一个字符编码的前缀从而保证了解码时的唯一性同时使得整体的编码长度最短。今天我们就抛开教科书上抽象的图示和证明用C手把手实现一棵赫夫曼树并完成一个简易的文本文件压缩/解压程序。你会看到从一堆字符频率到一棵树再到最终的压缩比特流每一个步骤如何用代码清晰地表达出来。更重要的是我会分享在实现过程中那些容易踩坑的细节比如内存管理、二进制位操作、文件I/O的边界处理这些才是将理论转化为可靠代码的关键。2. 赫夫曼树的核心原理贪心策略与最优前缀码要理解赫夫曼树必须先吃透两个核心概念贪心算法和前缀码。2.1 前缀码无歧义解码的保证前缀码是一种编码方式其中任何一个字符的编码都不是另一个字符编码的前缀。举个例子假设我们为 {A, B, C, D} 设计编码。非前缀码有问题的A0, B00, C1, D01。当你收到比特流“00”时你无法确定它是两个A0, 0还是一个B00。这就是歧义。前缀码正确的A0, B10, C110, D111。注意0不是10、110、111的前缀10不是110、111的前缀以此类推。对于比特流“010110”我们可以唯一地解码为 A(0), B(10), C(110)。赫夫曼树天然生成的就是前缀码。从树根到每个叶子节点的路径左走为0右走为1形成的编码必然满足前缀性质因为每个字符都位于叶子节点路径互不包含。2.2 贪心算法自底向上构建最优树赫夫曼树的构建过程是一个经典的贪心算法应用。它的目标是给定n个字符及其出现频率或权重构造一棵二叉树使得所有字符的带权路径长度最小。带权路径长度树中所有叶子节点的权重 × 该节点到根的路径长度之和。路径长度就是编码的位数。我们的目标就是最小化这个和即最小化总的编码长度。算法步骤这是你必须内化的逻辑初始化将每个字符看作一棵只有根节点的二叉树其权重即为频率。将这n棵树放入一个优先队列最小堆中。循环合并当堆中树的数量大于1时 a. 从堆中弹出权重最小的两棵树比如T1和T2。 b. 创建一棵新树TT的根节点权重 T1权重 T2权重。T的左子树为T1右子树为T2。 c. 将新树T放回堆中。结束堆中剩下的最后一棵树就是赫夫曼树。为什么这是“贪心”的因为在每一步我们都只做当前看起来最优的选择合并当前权重最小的两棵树。神奇的是这个局部最优的选择序列最终能导致全局最优解即带权路径长度最小。这是需要证明的但作为实现者我们首先需要相信并严格遵循这个过程。2.3 一个简单的例子假设有字符集 {A, B, C, D}频率分别为 {5, 1, 6, 3}。初始堆(B:1), (D:3), (A:5), (C:6)。弹出B和D合并为新树T1(权重4)。堆变为(T1:4), (A:5), (C:6)。弹出T1和A合并为新树T2(权重9)。堆变为(T2:9), (C:6)。弹出T2和C合并为新树T3(权重15)。这就是最终的赫夫曼树。从这棵树可以得到编码假设左0右1A: 可能是11取决于合并时左右顺序但长度固定B:100C:0D:101你可以计算一下使用这种编码的总比特数会比等长编码每个字符2位要少。3. C实现从节点定义到树构建理论清晰后我们开始用C实现。我们将整个过程模块化便于理解和调试。3.1 数据结构设计HuffmanNode树的节点是基础。我们需要区分叶子节点存字符和内部节点只存权重和左右孩子。#include cstdint // 用于uint8_t, uint32_t等明确大小的类型 #include memory // 用于智能指针简化内存管理 struct HuffmanNode { uint8_t ch; // 字符仅叶子节点有效。使用uint8_t表示0-255的字节。 uint32_t freq; // 权重频率 std::shared_ptrHuffmanNode left; // 左孩子 std::shared_ptrHuffmanNode right; // 右孩子 // 构造函数 HuffmanNode(uint8_t c, uint32_t f) : ch(c), freq(f), left(nullptr), right(nullptr) {} HuffmanNode(uint32_t f, std::shared_ptrHuffmanNode l, std::shared_ptrHuffmanNode r) : ch(0), freq(f), left(l), right(r) {} // 判断是否为叶子节点 bool isLeaf() const { return left nullptr right nullptr; } }; // 比较器用于优先队列最小堆 struct CompareNode { bool operator()(const std::shared_ptrHuffmanNode a, const std::shared_ptrHuffmanNode b) const { // 频率小的优先级高。如果频率相同可以定义额外规则如按字符保证确定性此处简化。 return a-freq b-freq; } };注意这里使用了std::shared_ptr智能指针。在赫夫曼树构建中节点会被多个父节点引用虽然最终树是唯一的但构建过程中临时节点可能被共享使用shared_ptr可以自动管理内存避免手动new/delete带来的内存泄漏风险尤其是在异常发生时。这是现代C推荐的做法。3.2 统计频率buildFrequencyTable压缩的第一步是扫描源文件统计每个字节0-255出现的次数。#include fstream #include vector #include array using FrequencyTable std::arrayuint32_t, 256; // 使用std::array大小固定为256 FrequencyTable buildFrequencyTable(const std::string inputFilename) { FrequencyTable freq {0}; // 初始化为全0 std::ifstream inFile(inputFilename, std::ios::binary); // 必须以二进制模式打开 if (!inFile.is_open()) { throw std::runtime_error(无法打开输入文件: inputFilename); } char byte; while (inFile.get(byte)) { // 将读取的char转换为无符号整数作为数组索引 freq[static_castunsigned char(byte)]; } // 处理一个特殊情况如果文件只有一个字符频率表只有一项非零。 // 赫夫曼树至少需要两个节点才能构建我们需要特殊处理。这里先忽略后面构建树时会处理。 return freq; }踩坑点1二进制模式打开文件。如果不使用std::ios::binary在Windows平台上读取文件时\r\n会被转换成\n导致统计的频率和实际字节不符压缩和解压必然失败。这是文件I/O操作中非常经典的坑。3.3 构建赫夫曼树buildHuffmanTree这是算法的核心。我们使用std::priority_queue作为最小堆。#include queue #include memory std::shared_ptrHuffmanNode buildHuffmanTree(const FrequencyTable freq) { // 定义最小堆 std::priority_queuestd::shared_ptrHuffmanNode, std::vectorstd::shared_ptrHuffmanNode, CompareNode minHeap; // 1. 初始化为每个频率0的字符创建叶子节点加入堆中 for (int i 0; i 256; i) { if (freq[i] 0) { minHeap.push(std::make_sharedHuffmanNode(static_castuint8_t(i), freq[i])); } } // 处理边界情况空文件或只有一个字符的文件 if (minHeap.empty()) { return nullptr; // 空树 } if (minHeap.size() 1) { // 只有一个字符需要构造一个虚拟的根节点让这个字符成为左孩子或右孩子。 // 否则编码长度为0无法解码。 auto singleNode minHeap.top(); minHeap.pop(); // 创建一个新的根节点左孩子是该字符节点右孩子为空或一个虚拟节点。 // 更常见的做法是让这个唯一字符的编码为“0”或“1”。 auto pseudoRoot std::make_sharedHuffmanNode(singleNode-freq, singleNode, nullptr); // 注意这里右孩子是nullptr解码时需要特殊处理。一个更健壮的做法是创建两个相同的节点合并。 // 我们采用另一种方法如果只有一个字符我们仍然创建一个内部节点其左右孩子都是这个字符节点但频率翻倍。 // 这样编码长度至少为1。 auto root std::make_sharedHuffmanNode(singleNode-freq * 2, singleNode, singleNode); return root; } // 2. 循环合并 while (minHeap.size() 1) { // 弹出两个权重最小的节点 auto left minHeap.top(); minHeap.pop(); auto right minHeap.top(); minHeap.pop(); // 创建新内部节点权重为子节点之和 uint32_t sumFreq left-freq right-freq; auto parent std::make_sharedHuffmanNode(sumFreq, left, right); // 将新节点加入堆中 minHeap.push(parent); } // 3. 堆中剩下的最后一个节点就是根节点 return minHeap.top(); }踩坑点2单一字符文件的处理。这是实现中极易忽略的边界情况。如果文件只有一个字符比如全是‘A’那么频率表中只有一项非零。按照标准算法堆中只有一个节点不会进入合并循环。这将导致生成的赫夫曼树只有一个叶子节点其编码长度为0。在压缩时你无法写入任何比特来代表这个字符解压时你看到空比特流也无法知道该解码成什么。因此必须特殊处理强制让这个唯一字符的编码长度至少为1。上面的代码展示了一种处理方法创建左右孩子相同的伪根你也可以选择在编码阶段如果发现编码表为空或只有一项时手动分配一个固定编码如“0”。4. 生成编码表与序列化树结构有了赫夫曼树我们需要遍历它来得到每个字符对应的二进制编码一个由‘0’和‘1’组成的字符串同时为了解压我们必须将树的结构也保存到压缩文件中。4.1 生成编码表generateCodes通过深度优先遍历DFS赫夫曼树我们可以生成编码表。#include string #include unordered_map using CodeTable std::unordered_mapuint8_t, std::string; void generateCodesHelper(const std::shared_ptrHuffmanNode node, const std::string code, CodeTable table) { if (!node) return; // 如果是叶子节点记录编码 if (node-isLeaf()) { // 注意对于只有一个字符的特殊树同一个字符可能出现在两个叶子 // 在我们之前的处理中对于单字符文件我们创建了一个左右孩子指向同一个节点的树。 // 这个节点会被访问两次左和右生成两个编码如0和1。 // 我们需要在调用此函数前或函数内处理这种情况确保一个字符只对应一个编码。 // 简单处理如果表中已存在该字符的编码则不覆盖或选择更短的。 // 更好的方法是在构建单字符树时就避免这种情况。我们调整buildHuffmanTree // 对于单字符创建一个新节点作为根其左孩子是字符节点右孩子是一个虚拟的、频率为0的空节点。 // 这样字符节点只会被访问一次。 if (table.find(node-ch) table.end()) { // 如果尚未记录 table[node-ch] code.empty() ? 0 : code; // 如果code为空即根就是叶子赋一个默认编码0 } } else { // 递归遍历左子树和右子树 if (node-left) { generateCodesHelper(node-left, code 0, table); } if (node-right) { generateCodesHelper(node-right, code 1, table); } } } CodeTable generateCodes(const std::shared_ptrHuffmanNode root) { CodeTable table; if (root) { // 处理单节点树的特殊情况 if (root-isLeaf()) { // 根节点本身就是叶子这意味着文件只有一个字符且我们之前没有创建伪根。 // 我们在这里赋予它一个固定编码0。 table[root-ch] 0; } else { generateCodesHelper(root, , table); } } return table; }4.2 序列化赫夫曼树serializeTree为了解压我们必须将树的结构保存到压缩文件中。我们不能只保存编码表因为解码时需要树来指导比特流的遍历。一个经典的方法是使用前序遍历并用特殊标记来区分内部节点和叶子节点。约定遇到叶子节点写入一个1比特紧接着写入该字符的8个比特一个字节。遇到内部节点写入一个0比特。这个过程需要按比特写入比较繁琐。我们这里先实现一个将树序列化为字符串‘0’/‘1’和字符的函数实际写入文件时再处理比特。#include sstream void serializeTreeHelper(const std::shared_ptrHuffmanNode node, std::ostringstream oss) { if (!node) return; if (node-isLeaf()) { oss.put(1); // 用字符1表示叶子节点 oss.put(node-ch); // 写入字符本身 } else { oss.put(0); // 用字符0表示内部节点 serializeTreeHelper(node-left, oss); serializeTreeHelper(node-right, oss); } } std::string serializeTree(const std::shared_ptrHuffmanNode root) { std::ostringstream oss; serializeTreeHelper(root, oss); return oss.str(); }这样序列化后的字符串就包含了完整的树结构信息。例如一个简单的树根为内部节点左右孩子分别是叶子节点‘A’和‘B’会被序列化为0 1 A 1 B空格仅为示意。注意这种序列化方法会占用额外空间但对于小文件或非极端情况开销是可接受的。更紧凑的序列化方式可以使用位操作但实现更复杂。我们优先保证清晰正确。5. 压缩过程从字符到比特流这是最激动人心也最易出错的一步。我们需要将序列化的树写入输出文件。再次读取源文件根据编码表将每个字符替换成对应的比特串。将这些比特串按顺序拼接每凑满8个比特一个字节就写入文件。处理最后一个可能不足8比特的字节。5.1 按比特写入的辅助类BitOutputStreamC标准库的ostream只支持按字节写入。我们需要一个包装类支持累积比特凑整后写入。class BitOutputStream { private: std::ofstream out; // 底层输出流 unsigned char buffer; // 8位缓冲区 int bitsInBuffer; // 当前缓冲区中已累积的比特数 public: explicit BitOutputStream(std::ofstream os) : out(os), buffer(0), bitsInBuffer(0) {} // 写入单个比特 (0 或 1) void writeBit(int bit) { if (bit ! 0 bit ! 1) { throw std::invalid_argument(Bit must be 0 or 1); } // 将比特放到缓冲区的最高位或最低位这里我们选择放到缓冲区的最高位从左到右填充。 // 假设buffer初始为0 bitsInBuffer0。 // 写入第一个比特1 buffer 1000 0000, bitsInBuffer1。 // 写入第二个比特0 buffer 1000 0000 | (0 (7-1)) 1000 0000, bitsInBuffer2。 // 更直观的做法是放到最低位然后左移。 // 我们采用buffer左移1位然后与新bit进行或操作。 buffer (buffer 1) | static_castunsigned char(bit); bitsInBuffer; if (bitsInBuffer 8) { flush(); // 缓冲区满写入文件 } } // 写入一个字符串形式的比特序列如 10110 void writeBits(const std::string bits) { for (char b : bits) { if (b 0) writeBit(0); else if (b 1) writeBit(1); else throw std::invalid_argument(Invalid bit character); } } // 强制将缓冲区内容写入文件可能不足8位并在末尾补0。 // 解压时需要知道补了多少位所以通常我们会先写入原始数据的比特总数或者在这里记录补位数。 // 我们采用另一种常见方法在最后一个字节将有效比特左移到该字节的高位解压时根据编码树自然停止。 // 但更可靠的方法是在文件开头写入一个“补位数”字节。 void flush() { if (bitsInBuffer 0) { // 将缓冲区中已有的比特左移使其位于字节的高位低位补0。 buffer (8 - bitsInBuffer); out.put(buffer); buffer 0; bitsInBuffer 0; } } // 析构时自动flush ~BitOutputStream() { flush(); } };5.2 完整的压缩函数compress现在我们将所有步骤串联起来。#include fstream #include iostream void compress(const std::string inputFilename, const std::string outputFilename) { // 1. 构建频率表 FrequencyTable freq buildFrequencyTable(inputFilename); // 2. 构建赫夫曼树 auto root buildHuffmanTree(freq); if (!root) { std::cerr 输入文件为空无需压缩。 std::endl; return; } // 3. 生成编码表 CodeTable codes generateCodes(root); // 4. 序列化树 std::string serializedTree serializeTree(root); // 5. 打开输出文件二进制模式 std::ofstream outFile(outputFilename, std::ios::binary); if (!outFile.is_open()) { throw std::runtime_error(无法打开输出文件: outputFilename); } // 6. 写入压缩文件头部信息可选但很重要 // 通常包括魔数标识文件类型、原始文件大小、树序列化数据的大小等。 // 这里我们简化先写入序列化树的大小4字节再写入树数据本身。 uint32_t treeSize static_castuint32_t(serializedTree.size()); outFile.write(reinterpret_castconst char*(treeSize), sizeof(treeSize)); outFile.write(serializedTree.data(), treeSize); // 7. 再次打开输入文件进行编码压缩 std::ifstream inFile(inputFilename, std::ios::binary); BitOutputStream bitOut(outFile); // 创建比特输出流 char byte; while (inFile.get(byte)) { uint8_t ch static_castunsigned char(byte); auto it codes.find(ch); if (it codes.end()) { // 理论上不会发生因为编码表来自频率表 throw std::runtime_error(发现未编码字符); } bitOut.writeBits(it-second); // 写入该字符对应的比特串 } // 8. BitOutputStream析构时会自动flush将最后不足8位的缓冲区写入。 // 但我们还需要告诉解压方“有效数据到此为止”否则会多读。 // 一个简单方法在flush后再额外写入一个字节标明最后一个有效字节中有多少位是真实的。 // 我们在flush后再写入bitsInBuffer实际在flush后它为0。 // 我们需要修改BitOutputStream在flush前记录这个数字。 // 为了简化我们采用另一种策略在文件开头也写入原始数据的比特总数。这里先不实现。 // 对于学习目的我们假设解码时能通过树正确终止当解码出的字符数等于原文件字符数时停止。 // 这要求我们在文件头也写入原始文件的字符总数或字节数。 std::cout 压缩完成。输出文件: outputFilename std::endl; }踩坑点3文件头信息与解码终止。这是实现压缩解压程序最关键的细节之一。解压器需要知道三件事1) 赫夫曼树的结构2) 压缩后的比特流从哪里开始3) 比特流在哪里结束即哪些比特是有效数据哪些是填充的0。我们的实现中树结构及其大小已经写入。但比特流的结束位置是模糊的。因为最后一个字节可能只有部分比特是有效的BitOutputStream::flush()会用0补足。如果解压器一直读它会把这些填充的0也当作编码来解析导致错误。解决方案在文件头额外存储原始数据的字节数或字符数。解压时每解码出一个字符计数器加一当解码字符数等于原始字符数时立即停止忽略后面可能存在的填充比特。这是最常用、最可靠的方法。我们需要修改压缩函数在写入树数据后再写入原始文件的大小uint32_t originalSize。这部分代码的补充将在解压部分体现。6. 解压过程从比特流重建数据解压是压缩的逆过程从压缩文件头部读取树结构信息反序列化重建赫夫曼树。读取后续的比特流。从树根开始根据比特流中的每一位0向左1向右遍历赫夫曼树到达叶子节点时输出对应的字符。重复步骤3直到解码出预定数量的字符由头部信息给出。6.1 按比特读取的辅助类BitInputStream与BitOutputStream对应我们需要一个能按比特读取文件的类。class BitInputStream { private: std::ifstream in; unsigned char buffer; // 当前字节 int bitsInBuffer; // 当前字节中剩余未读的比特数 bool isEof; // 是否已到达文件末尾底层流 // 从文件中读取下一个字节到缓冲区 void fillBuffer() { if (isEof) { buffer 0; bitsInBuffer 0; return; } char byte; if (in.get(byte)) { buffer static_castunsigned char(byte); bitsInBuffer 8; } else { isEof true; buffer 0; bitsInBuffer 0; } } public: explicit BitInputStream(std::ifstream is) : in(is), buffer(0), bitsInBuffer(0), isEof(false) { fillBuffer(); // 预读第一个字节 } // 读取一个比特如果文件结束返回-1 int readBit() { if (bitsInBuffer 0) { if (isEof) return -1; fillBuffer(); if (bitsInBuffer 0) return -1; // 填充后仍然为空说明文件已读完 } // 从buffer的最高位开始取比特 int bit (buffer (bitsInBuffer - 1)) 1; bitsInBuffer--; return bit; } // 判断是否还有比特可读包括缓冲区中的和文件中未读的 bool good() const { return !isEof || bitsInBuffer 0; } };6.2 反序列化赫夫曼树deserializeTree根据之前序列化的规则‘0’内部节点‘1’叶子节点后跟一个字节字符从比特流中重建树。注意我们现在是从一个std::string或直接按字节读取来重建而不是从BitInputStream读因为树结构数据是按字节对齐存储的。#include istream #include memory std::shared_ptrHuffmanNode deserializeTreeHelper(std::istream in) { char flag; if (!in.get(flag)) { return nullptr; // 读取失败 } if (flag 1) { // 叶子节点 char ch; if (!in.get(ch)) { throw std::runtime_error(反序列化树失败期望字符数据); } return std::make_sharedHuffmanNode(static_castuint8_t(ch), 0); // 频率在解压时无用设为0 } else if (flag 0) { // 内部节点 auto left deserializeTreeHelper(in); auto right deserializeTreeHelper(in); // 内部节点的频率在解压时也无用设为0 return std::make_sharedHuffmanNode(0, left, right); } else { throw std::runtime_error(反序列化树失败无效的标志位); } } std::shared_ptrHuffmanNode deserializeTree(const std::string treeStr) { std::istringstream iss(treeStr); return deserializeTreeHelper(iss); }6.3 完整的解压函数decompress现在实现解压主函数并加入之前提到的文件头信息树大小、原始数据大小。void decompress(const std::string inputFilename, const std::string outputFilename) { std::ifstream inFile(inputFilename, std::ios::binary); if (!inFile.is_open()) { throw std::runtime_error(无法打开压缩文件: inputFilename); } // 1. 读取树的大小 uint32_t treeSize 0; if (!inFile.read(reinterpret_castchar*(treeSize), sizeof(treeSize))) { throw std::runtime_error(读取树大小失败); } // 2. 读取序列化树的字符串数据 std::vectorchar treeData(treeSize); if (!inFile.read(treeData.data(), treeSize)) { throw std::runtime_error(读取树数据失败); } std::string treeStr(treeData.begin(), treeData.end()); // 3. 反序列化重建赫夫曼树 auto root deserializeTree(treeStr); if (!root) { throw std::runtime_error(重建赫夫曼树失败); } // 4. 读取原始数据大小我们在压缩时应该写入现在假设它存在 // 修改压缩函数在写入树数据后写入原始文件的字节数。 // 我们这里先读取它。 uint32_t originalDataSize 0; // 原始文件的字节数 if (!inFile.read(reinterpret_castchar*(originalDataSize), sizeof(originalDataSize))) { throw std::runtime_error(读取原始数据大小失败); } // 5. 打开输出文件 std::ofstream outFile(outputFilename, std::ios::binary); if (!outFile.is_open()) { throw std::runtime_error(无法打开输出文件: outputFilename); } // 6. 使用BitInputStream读取后续的压缩比特流 BitInputStream bitIn(inFile); auto currentNode root; uint32_t decodedCount 0; while (decodedCount originalDataSize) { int bit bitIn.readBit(); if (bit -1) { // 比特流提前结束可能文件损坏 throw std::runtime_error(压缩数据不完整或已损坏); } // 根据比特遍历树 if (bit 0) { if (currentNode-left) { currentNode currentNode-left; } else { throw std::runtime_error(无效的压缩数据比特流与树结构不匹配); } } else { // bit 1 if (currentNode-right) { currentNode currentNode-right; } else { throw std::runtime_error(无效的压缩数据比特流与树结构不匹配); } } // 如果到达叶子节点输出字符并重置到根节点 if (currentNode-isLeaf()) { outFile.put(static_castchar(currentNode-ch)); decodedCount; currentNode root; // 回到根节点准备解码下一个字符 } } // 7. 解码字符数已达到原始大小停止。忽略后面可能存在的填充比特。 std::cout 解压完成。输出文件: outputFilename std::endl; }相应地我们需要修改压缩函数compress在写入树数据后写入原始文件的大小。// 在compress函数中写入树数据之后写入原始文件大小 // ... 写入treeSize和serializedTree ... // 获取原始文件大小字节数 inFile.clear(); // 清除可能的eof状态 inFile.seekg(0, std::ios::end); uint32_t originalSize static_castuint32_t(inFile.tellg()); inFile.seekg(0, std::ios::beg); // 重置文件指针准备重新读取数据 // 写入原始文件大小 outFile.write(reinterpret_castconst char*(originalSize), sizeof(originalSize)); // 然后继续创建BitOutputStream并进行编码...踩坑点4文件指针与重复读取。在压缩函数中我们两次打开或读取输入文件一次统计频率一次进行编码。第二次读取前必须将文件指针重置到开头inFile.seekg(0, std::ios::beg)。同时在获取文件大小后也要重置指针。忘记重置是常见的错误会导致第二次读取不到任何数据。7. 测试、局限性与扩展思考7.1 如何测试编写一个简单的main函数来测试压缩和解压int main() { std::string inputFile test.txt; std::string compressedFile test.huff; std::string decompressedFile test_decompressed.txt; try { // 压缩 compress(inputFile, compressedFile); std::cout 压缩成功。 std::endl; // 解压 decompress(compressedFile, decompressedFile); std::cout 解压成功。 std::endl; // 验证比较原始文件和解压后的文件是否一致 // 可以使用系统命令如fc(Windows)或diff(Linux/Mac)或者写代码逐字节比较。 std::ifstream orig(inputFile, std::ios::binary); std::ifstream decomp(decompressedFile, std::ios::binary); bool identical true; char c1, c2; while (orig.get(c1) decomp.get(c2)) { if (c1 ! c2) { identical false; break; } } // 检查是否都同时到达文件末尾 if (orig.good() ! decomp.good()) { identical false; } if (identical) { std::cout 验证通过解压文件与原始文件完全一致。 std::endl; } else { std::cout 验证失败文件内容不一致 std::endl; } } catch (const std::exception e) { std::cerr 错误: e.what() std::endl; return 1; } return 0; }7.2 本实现的局限性内存与效率我们一次性将整个树序列化成字符串对于包含大量不同字符的文件树可能很大。实际工业级实现如zlib会使用更紧凑的规范赫夫曼树表示法。文件头开销我们存储了整棵树的序列化表示和原始文件大小。对于非常小的文件头信息可能比压缩后的数据还大导致“负压缩”。仅支持字节流我们的实现针对的是二进制字节流0-255。对于纯文本文件可以考虑使用ASCII或UTF-8但原理相同。无分块处理对于大文件一次性统计频率可能内存占用高。实际中可采用自适应赫夫曼编码或分块处理。无错误恢复文件损坏或格式不对时程序会直接崩溃。健壮的程序应加入更多的错误检查和恢复机制。7.3 扩展思考从赫夫曼到DEFLATE真正的ZIP、GZIP、PNG等格式使用的DEFLATE算法是赫夫曼编码的加强版。它主要做了两件事LZ77滑动窗口压缩先通过查找重复字符串并用距离长度对替换消除文件中的冗余。赫夫曼编码对LZ77处理后的输出包含字面量字节、距离、长度信息进行赫夫曼编码。并且它使用了两棵赫夫曼树一棵用于字面量/长度另一棵用于距离。此外DEFLATE使用了规范赫夫曼码它不存储整棵树而是只存储每个编码长度的符号数量从而极大地减少了树结构信息的开销。这是赫夫曼编码在工程实践上的一个重要优化方向。实现一个完整的DEFLATE压缩器是庞大的工程但理解了我们今天手写的赫夫曼压缩解压全过程你就已经握住了打开无损压缩世界大门的钥匙。下次当你再点击“压缩文件”时你看到的将不再是一个黑盒而是一棵棵优雅的二叉树在比特的海洋里高效地排列组合。