简介一份演示C结合MFC实现Huffman编码压缩与解压的完整工程源码面向Windows桌面应用开发者尤其适合需要掌握无损压缩算法原理及MFC文件操作的中级C学习者。资源共46个文件以C头文件与实现文件h/cpp为主同时包含MFC工程配置sln/vcxproj、可执行程序exe及调试信息pdb等整体压缩包约40.81MB。已有206人学习下载。代码覆盖字符频率统计、Huffman树构建、编码表生成、二进制压缩与解压还原全流程并在MFC界面中演示文件选择、读取、写入等操作通过运行exe可快速验证效果结合源码便于理解压缩编解码的每个环节也可在此基础上扩展其他压缩算法。1. 需求分析与技术选型为什么是HuffmanMFC1.1 压缩算法的选型逻辑凡是做文件压缩最先碰到的就是选型问题。常见的无损压缩方案无外乎RLE游程编码、LZ77/LZ78系也就是Deflate、zip、gzip的底子、Huffman编码这几条路。我之所以在这个项目里选Huffman核心就一句话在算法复杂度和压缩效果的平衡点上Huffman是最适合教学落地和中小文件处理的方案。RLE实现简单但对文本类、数据类文件几乎无效顶多对付BMP位图、某些配置文件里连续重复的字节LZ系比如zip用的Deflate压缩率确实高但牵扯到滑动窗口、哈希链匹配、动态规划式的最优匹配这些概念程序量级和调试成本都不是一个小项目该承受的。Huffman的思路则异常朴素统计每个字节出现的频率给高频字节分配短编码、低频字节分配长编码整体算下来文件就能变小。它的原理足够经典JPEG、PNG、MP3这些格式内部都在用它做熵编码那一环——换言之你把这个小项目吃透等于把现代压缩体系的最后一块拼图装进了脑子里。1.2 为什么用MFC做界面层再聊界面。现在很多入门项目喜欢用Qt、WinForm甚至纯控制台而我坚持用MFC原因很实在MFC是Windows平台下最容易让学生理解“窗口消息机制”的框架而且网上资料存量极大。做Huffman压缩解压工具核心功能在算法层界面层只需要文件选择、压缩/解压按钮、进度显示、日志输出这几样东西MFC的对话框程序Dialog Based恰好能以最小成本把这些都组织起来。多说一句MFC虽然被一些人吐槽老旧但它在Windows原生开发、特别是工控和传统行业软件里的存量市场依旧可观。你学会了MFC的对话框、按钮、进度条、ListBox这些控件的用法后面再接触什么MFCOpenGL绘图、MFC操作MySQL、MFC项目打包发布都是一条线串下来的事。这个项目正好是把C语法、数据结构和Windows界面编程捏在一起的最佳练习场景。2. 核心算法拆解从字符频率到Huffman树2.1 数据结构设计整个压缩器的基础是一棵二叉树。每个叶子节点对应一个字节值0~255内部节点不存数据只存权重。权重就是该子树下所有叶子节点出现次数的总和。C里我用一个结构体来承载节点信息typedef struct HuffNode { unsigned char ch; // 字节值仅叶子节点有效 unsigned long freq; // 出现频率 struct HuffNode* left; struct HuffNode* right; HuffNode() : ch(0), freq(0), left(nullptr), right(nullptr) {} } HuffNode;这里有几个细节需要讲明白第一freq用unsigned long而不是int。如果一个几GB的大文件要做压缩单个字节的出现次数可能超过21亿32位signed int直接溢出。unsigned long在Windows 64位下是4字节虽然上限也就42亿左右但配合后面的分批处理策略足够覆盖日常场景。真要处理超大规模文件可以进一步扩到unsigned long long代价是内存占用上升没必要一上来就拉满。第二构建Huffman树的标准做法是“贪心 优先队列”。每次从所有节点中取出频率最小的两个节点合并成一个新节点新节点的频率等于两者之和再丢回队列。循环到只剩一个根节点为止。这里有同学喜欢自己写数组扫描找最小值我个人不建议——时间复杂度是O(n²)字符种类只有256个时问题不大但如果将来你想扩展到双字节编码65536种O(n²)就会拖慢构建速度。直接上std::priority_queue代码又短又不容易出逻辑错误struct NodeCmp { bool operator()(HuffNode* a, HuffNode* b) { return a-freq b-freq; // 小顶堆频率小的优先 } }; std::priority_queueHuffNode*, std::vectorHuffNode*, NodeCmp minHeap;2.2 构建Huffman树的关键代码第一步读文件统计频率。我用一个256格的数组存计数每次读入4KB缓冲循环叠加unsigned long freqTable[256] { 0 }; char buffer[4096]; DWORD bytesRead 0; HANDLE hFile CreateFileA(srcPath, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL); if (hFile INVALID_HANDLE_VALUE) { // 文件打开失败弹错误信息 return FALSE; } while (ReadFile(hFile, buffer, sizeof(buffer), bytesRead, NULL) bytesRead 0) { for (DWORD i 0; i bytesRead; i) { freqTable[(unsigned char)buffer[i]]; } } CloseHandle(hFile);搞完频率统计将所有freq 0的字节值包装成叶子节点扔进优先队列for (int i 0; i 256; i) { if (freqTable[i] 0) { HuffNode* node new HuffNode(); node-ch (unsigned char)i; node-freq freqTable[i]; minHeap.push(node); } }然后循环建树while (minHeap.size() 1) { HuffNode* left minHeap.top(); minHeap.pop(); HuffNode* right minHeap.top(); minHeap.pop(); HuffNode* parent new HuffNode(); parent-freq left-freq right-freq; parent-left left; parent-right right; minHeap.push(parent); } HuffNode* root minHeap.top();这段代码的逻辑核心就是“每次找最小的两颗子树合并”。有个细节要特别注意合并时左右子树的顺序不影响压缩率但会影响编码分配结果。你规定左边记0右边记1或者反过来都能编出合法前缀码只是最终二进制流不一样。稳妥起见统一约定左0右1即可。2.3 生成编码表递归遍历与快速查找树建好了下一步是给每个叶子节点生成对应的二进制编码串。经典做法是深度优先遍历从根节点出发向左走追加0向右走追加1void GenerateCodes(HuffNode* node, std::string code, std::string codes[256]) { if (!node) return; if (!node-left !node-right) { codes[node-ch] code; return; } GenerateCodes(node-left, code 0, codes); GenerateCodes(node-right, code 1, codes); }这里有个坑递归遍历的次数叶子节点数×平均深度深度可能超过几十层递归栈深度不是问题最多256层栈空间完全够。如果你的工程后面要做性能优化可以把递归改成显式栈的迭代版本但对当前项目来说递归版本可读性最好不需要过度设计。编码表生成后你可以立刻验证一个性质任何字符的编码都不是另一个字符编码的前缀。这是Huffman编码的核心优势也是解压时能够从比特流里连续解码的前提。验证方法很简单——把每个编码串写入一个哈希集合检查是否有某个编码是另一个编码的前缀串。3. 文件格式设计压缩包的重中之重3.1 压缩文件头部结构Huffman压缩并不是简单地把编码流写进文件就行你还需要设计好文件头让解压端知道怎么还原。我最终采用的文件格式如下字段大小说明文件标识2字节固定0x48 0x46HF校验文件类型原始文件大小8字节64位记录解压后应还原的字节数字符种类数2字节有效叶子节点个数叶子节点信息区变长每种字符的字节值和编码长度Huffman树恢复区变长前序遍历序列化结果编码数据区变长逐个字符按编码表写入的位流这里为什么不用建Huffman树时明确的频率表因为频率表在解压端没用解压只需要编码树的结构。你给解压端一堆频率值它还要重新建一次树麻烦且容易出错。直接把树结构序列化写进去解压端读进来就能用。树结构的序列化格式也简单——前序遍历遇到内部节点写0遇到叶子节点写1字节值。这样递归重建非常方便。还有那个“原始文件大小”字段千万别省。解压到最后一个字节时由于编码是按位写入的文件尾部必然存在填充位没有这个字段你不知道哪些位是有效数据哪些是凑数的。3.2 按位写入的实现细节C/C的文件API都是按字节操作的而Huffman编码是变长的位流。所以核心工作就是把编码串按位拼成一个字节再写入满了就落盘剩下最后不足8位的部分用0补齐。我实现了一个极简的BitWriter类class BitWriter { public: void WriteBits(const std::string bits) { for (char c : bits) { byteBuffer | ((c - 0) (7 - bitCount)); bitCount; if (bitCount 8) { fwrite(byteBuffer, 1, 1, outFile); byteBuffer 0; bitCount 0; } } } void Flush() { if (bitCount 0) { fwrite(byteBuffer, 1, 1, outFile); byteBuffer 0; bitCount 0; } } private: FILE* outFile; unsigned char byteBuffer 0; int bitCount 0; };写入时的核心顺序是“先写的高位”。比如某个字符的编码是101那它占第一个字节的高3位这个字节剩余5位留给后续字符。7 - bitCount这个位移值保证每次写入都紧接上一次的剩余位置。这个小类如果处理不好压缩出来的文件解压时大概率全部乱码——调试这种问题非常痛苦因为你在二进制层面根本看不出错误。踩过一次坑之后我的经验是写一个小测试用例用固定字符串比如abcabcabc走一遍压缩再解压逐步对比中间结果。3.3 压缩主流程代码压缩函数的完整逻辑如下BOOL CompressFile(const CString srcPath, const CString dstPath, CProgressCtrl progress) { // 1. 第一遍读文件统计频率 unsigned long freqTable[256] { 0 }; CountFrequency(srcPath, freqTable); // 2. 构建Huffman树并生成编码表 HuffNode* root BuildHuffmanTree(freqTable); std::string codes[256]; GenerateCodes(root, , codes); // 3. 打开输出文件先预留文件头位置 FILE* out fopen(dstPath, wb); if (!out) return FALSE; WriteFileHeader(out, srcPath, freqTable, root); // 4. 第二遍读文件按编码表逐字符写入 FILE* in fopen(srcPath, rb); BitWriter writer(out); char buffer[4096]; DWORD bytesRead 0; while ((bytesRead fread(buffer, 1, sizeof(buffer), in)) 0) { for (DWORD i 0; i bytesRead; i) { writer.WriteBits(codes[(unsigned char)buffer[i]]); } } writer.Flush(); fclose(in); fclose(out); return TRUE; }有个性能细节值得说如果你在循环里一个字符一个字符地调用fwrite速度会非常慢。所以代码里用4KB缓冲做批量读取WriteBits内部再累积到8位才落盘一次。两层缓冲加在一起压缩几十MB的文件耗时基本在毫秒级到秒级体验完全没问题。4. MFC界面与交互流程4.1 界面布局规划我用MFC对话框模板做了极简布局上方两个编辑框分别显示源文件路径和解压目标路径中间两个按钮“选择源文件”和“选择输出路径”下方两个主操作按钮“执行压缩”和“执行解压”再往下一条进度条和一个多行编辑框Log区域。控件类型和ID规划如下表纯经验值方便你对照着搭控件ID说明源文件编辑框IDC_EDIT_SRC只读路径由文件对话框填充输出路径编辑框IDC_EDIT_DST可编辑允许手动输入选择源文件按钮IDC_BTN_BROWSE_SRC打开CFileDialog执行压缩按钮IDC_BTN_COMPRESS主逻辑入口执行解压按钮IDC_BTN_DECOMPRESS主逻辑入口进度条IDC_PROGRESS显示压缩/解压进度日志列表IDC_EDIT_LOG多行文本只读输出过程信息4.2 按钮事件与主逻辑绑定MFC的按钮消息映射用ON_BN_CLICKED宏绑定。压缩按钮响应函数大概长这样void CHuffmanCompressDlg::OnBnClickedBtnCompress() { CString srcPath, dstPath; GetDlgItemText(IDC_EDIT_SRC, srcPath); GetDlgItemText(IDC_EDIT_DST, dstPath); if (srcPath.IsEmpty() || dstPath.IsEmpty()) { AfxMessageBox(_T(请先选择源文件和输出路径)); return; } // 用AfxBeginThread启动后台线程避免界面卡死 m_pThread AfxBeginThread(CompressWorkerThread, this); // 主线程继续跑消息循环进度条由工作线程通过PostMessage更新 }这里有个非常重要的实战经验压缩大文件时绝不能在UI线程里直接执行耗时操作。一个几百MB的文件光统计频率遍历写编码流就得好几秒主线程卡住会导致窗口无响应、进度条不刷新Windows会提示“程序未响应”。正确做法是用AfxBeginThread开工作线程算法跑完了再用PostMessage通知UI线程更新界面。工作线程里更新进度条你可以自定义一个消息#define WM_UPDATE_PROGRESS (WM_USER 101) // 工作线程中 ::PostMessage(hWnd, WM_UPDATE_PROGRESS, (WPARAM)percent, 0);然后在对话框类里加一个处理函数把percent直接设置给进度条控件。4.3 文件对话框使用细节选择文件那块MFC的CFileDialog有两种形态。普通模太对话框会阻塞界面但对选择文件这种短操作足够。有一个容易踩的坑是从CFileDialog里取出的路径可能是旧的8.3短路径格式也可能带C:\这种反斜杠结尾拼接输出路径时先做统一处理CFileDialog dlg(TRUE, _T(*), NULL, OFN_FILEMUSTEXIST | OFN_HIDEREADONLY, _T(All Files (*.*)|*.*||), this); if (dlg.DoModal() IDOK) { CString path dlg.GetPathName(); SetDlgItemText(IDC_EDIT_SRC, path); // 自动生成默认输出路径原名去掉扩展名后加上.hf CString newPath path.Left(path.ReverseFind(_T(.))); newPath _T(.hf); SetDlgItemText(IDC_EDIT_DST, newPath); }从选择源文件到自动填充输出路径这一步能省用户不少事。加密压缩包的扩展名我用成.hf和文件标识HF对应比较有辨识度。5. 解压流程与细节处理5.1 文件头解析与树重建解压是压缩的逆过程但顺序上有点反直觉读文件头、重建Huffman树、然后按位读取编码数据流、沿着树走叶子节点还原字节。文件头读取逻辑如下BOOL ReadAndRebuildTree(FILE* in, HuffNode* root) { // 校验文件标识 char magic[2]; fread(magic, 1, 2, in); if (magic[0] ! H || magic[1] ! F) { AfxMessageBox(_T(非法的压缩文件格式)); return FALSE; } // 读取原始文件大小 fread(origSize, 8, 1, in); // 读取叶子节点数2字节 unsigned short leafCount 0; fread(leafCount, 2, 1, in); // 之前压缩时记录每个叶子字节值这里直接重建树 root RebuildTreeFromFile(in, leafCount); return TRUE; }树重建的递归函数和压缩时的序列化函数一一对应HuffNode* RebuildTreeFromFile(FILE* in, unsigned short remainLeaves) { unsigned char flag; fread(flag, 1, 1, in); if (flag 0) { // 内部节点 HuffNode* node new HuffNode(); node-left RebuildTreeFromFile(in, remainLeaves); node-right RebuildTreeFromFile(in, remainLeaves); return node; } else { // 叶子节点 HuffNode* node new HuffNode(); fread(node-ch, 1, 1, in); remainLeaves--; return node; } }5.2 按位解码与文件还原解压时的核心循环是这样从压缩流里一次读1位根据位值决定走向左子树还是右子树每到达一个叶子节点就把ch写入输出文件然后回到根节点重新开始。一直到写出字节数等于文件头记录的大小为止。void DecompressCore(FILE* in, FILE* out, HuffNode* root, unsigned long long origSize) { BitReader reader(in); HuffNode* cursor root; unsigned long long written 0; while (written origSize) { int bit reader.ReadBit(); if (bit -1) break; // 数据耗尽防御处理 if (bit 0) cursor cursor-left; else cursor cursor-right; if (!cursor-left !cursor-right) { fwrite(cursor-ch, 1, 1, out); written; cursor root; } } }BitReader的读取逻辑是BitWriter的镜像每次读8位填充内部缓冲维护好位偏移就行。这里有个潜在bug如果压缩文件尾部填充位的0恰好构成某个字符的编码前缀且written origSize的判定放在循环尾部就会多写一字节。所以上面代码把written的检查放在循环开头先判断再解码能有效避免这种越界。5.3 解压结果校验解压完成后建议强制做一次大小校验// 解压完成后检查 if (written origSize) { Log(_T(解压成功共还原 %llu 字节), written); } else { Log(_T(解压失败预期 %llu 字节实际 %llu 字节), origSize, written); return FALSE; }对于重要文件我还会顺手算一下解压前后内容的CRC32或MD5做完整性比对。这一步不是必须的但加上了能让整个工具专业不少。6. 常见问题与排查技巧实录6.1 压缩后文件反而变大新手最容易碰到的现象是压缩一个原本已经很紧凑的文件比如JPEG、MP3、ZIP结果输出比输入还大。这不是代码Bug而是原理性的问题——Huffman对“数据本身已近熵上限”的文件没有增益还要额外付出存放文件头和树的字节开销。处理办法有两个方向要么压缩前判断一下字节种类数与文件尺寸比如果种类太多说明熵很高放弃压缩并提示用户要么至少让用户知道“本算法适合文本、日志、数据库备份等重复度高的数据对多媒体文件效果有限”。实操中我在压缩按钮里加了一个简单的阈值有效字符种类 200或压缩后大小 原始大小时输出警告日志并停止写文件而不是生成一个还不如下不压的文件。6.2 大文件内存溢出还记得最开始用unsigned long存频率吗如果压缩一个超大文件例如视频、磁盘镜像单字符出现次数可能超过unsigned long上限。虽然概率很低但稳妥起见可以把频率类型改成unsigned long long代价是内存占用从1KB变成2KB忽略不计。真正吃内存的是压缩过程中codes数组里存的编码字符串。最坏情况下每个字符的编码长度可能到256位256个字符最多也就64KB内存完全没问题。所以这个项目的内存瓶颈始终不在编码表而在文件读写缓冲的大小——4KB一读的策略对超大文件IO次数偏多可以提到64KB~1MB之间压缩速度会有明显提升。6.3 中文路径和文件权限问题MFC的CFileDialog返回的路径如果是C:\用户\测试文件.txt这种中文路径直接用fopen可能失败。原因在于窄字符版本的fopen依赖系统代码页Windows默认对中文路径支持不稳定。解决办法是使用宽字符版本的_wfopenFILE* in _wfopen(srcPath.GetString(), Lrb); FILE* out _wfopen(dstPath.GetString(), Lwb);这一点能省掉一大半“路径打不开”的毛病。此外如果输出路径所在的目录没有写权限比如Program Files下面程序会弹出权限错误。我在选择输出路径时默认跳到桌面或用户文档目录可以避开权限坑。6.4 进度条和界面卡顿已经说过用AfxBeginThread开线程这里补充一个很容易被忽视的细节工作线程里不能直接操作UI控件必须先PostMessage回UI线程。MFC内部控件不是线程安全的直接跨线程调用进度条的SetPos轻则界面刷不出来重则程序崩溃。正确姿势我已经写在4.2节核心就两步工作线程计算百分比PostMessage通知UI线程UI线程收到消息后调用SetPos。这样进度条丝滑刷新用户不会觉得程序卡死了。6.5 编码表节点内存泄漏最后谈谈树节点的内存管理。压缩和解压都涉及new出来的HuffNode只要建树就要记得释放。我封装了一个递归释放函数void FreeHuffmanTree(HuffNode* node) { if (!node) return; FreeHuffmanTree(node-left); FreeHuffmanTree(node-right); delete node; }在压缩结束和解压结束后各调用一次。别小看这一步虽然单次运行内存泄漏量不大但如果在MFC里反复压缩多个文件泄漏会慢慢累积最终导致进程内存飙升。7. 扩展优化方向做完一个能跑的Huffman压缩解压工具只是起点后面有太多值得折腾的方向。第一把静态Huffman改成动态Huffman。静态方案要扫描两遍文件一遍统计、一遍编码动态方案可以在一次扫描里同时构建并更新编码树虽然算法复杂不少但压缩率和速度都会有改善这也是Deflate所用的方案之一。第二引入算术编码或Range Coder。Huffman编码对每个符号固定分配整数个bit理论上对概率接近1的符号存在浪费。算术编码能把多个符号压缩到一个小数区间里压缩率更高但实现难度也上一个台阶。第三加入多线程编码。前面提到文件读取用缓冲循环你可以把一个大文件拆成多个块每个块独立构建Huffman树最后并行编码再用块索引组织输出。这个思路和zstd、lz4的frame格式某些层面是相通的做出来性能提升会非常可观。第四如果你手头正好在做OpenCV、Matlab相关实验会发现JPEG内部的Huffman编码和这个项目几乎是一个模子——唯一的差异是JPEG对DC系数用差分、对AC系数用Zigzag扫描再跑Huffman。底子打好了看其他格式源码就不发怵。我在实际开发中还有一个体会压缩算法这个领域标准的实现往往不是最难的难的是边界情况和异常处理。比如空文件、单个字符文件、恰好256种字符全出现的文件、文件末尾截断、磁盘写满——每一种情况都要想清楚程序该怎么表现。把这个工具当成一个“完整产品”而不是“作业”来打磨你会收获远超算法本身的东西。本文还有配套的精品资源点击获取 基于MFC的Huffman文件压缩解压工具设计与实现
简介一份演示C结合MFC实现Huffman编码压缩与解压的完整工程源码面向Windows桌面应用开发者尤其适合需要掌握无损压缩算法原理及MFC文件操作的中级C学习者。资源共46个文件以C头文件与实现文件h/cpp为主同时包含MFC工程配置sln/vcxproj、可执行程序exe及调试信息pdb等整体压缩包约40.81MB。已有206人学习下载。代码覆盖字符频率统计、Huffman树构建、编码表生成、二进制压缩与解压还原全流程并在MFC界面中演示文件选择、读取、写入等操作通过运行exe可快速验证效果结合源码便于理解压缩编解码的每个环节也可在此基础上扩展其他压缩算法。1. 需求分析与技术选型为什么是HuffmanMFC1.1 压缩算法的选型逻辑凡是做文件压缩最先碰到的就是选型问题。常见的无损压缩方案无外乎RLE游程编码、LZ77/LZ78系也就是Deflate、zip、gzip的底子、Huffman编码这几条路。我之所以在这个项目里选Huffman核心就一句话在算法复杂度和压缩效果的平衡点上Huffman是最适合教学落地和中小文件处理的方案。RLE实现简单但对文本类、数据类文件几乎无效顶多对付BMP位图、某些配置文件里连续重复的字节LZ系比如zip用的Deflate压缩率确实高但牵扯到滑动窗口、哈希链匹配、动态规划式的最优匹配这些概念程序量级和调试成本都不是一个小项目该承受的。Huffman的思路则异常朴素统计每个字节出现的频率给高频字节分配短编码、低频字节分配长编码整体算下来文件就能变小。它的原理足够经典JPEG、PNG、MP3这些格式内部都在用它做熵编码那一环——换言之你把这个小项目吃透等于把现代压缩体系的最后一块拼图装进了脑子里。1.2 为什么用MFC做界面层再聊界面。现在很多入门项目喜欢用Qt、WinForm甚至纯控制台而我坚持用MFC原因很实在MFC是Windows平台下最容易让学生理解“窗口消息机制”的框架而且网上资料存量极大。做Huffman压缩解压工具核心功能在算法层界面层只需要文件选择、压缩/解压按钮、进度显示、日志输出这几样东西MFC的对话框程序Dialog Based恰好能以最小成本把这些都组织起来。多说一句MFC虽然被一些人吐槽老旧但它在Windows原生开发、特别是工控和传统行业软件里的存量市场依旧可观。你学会了MFC的对话框、按钮、进度条、ListBox这些控件的用法后面再接触什么MFCOpenGL绘图、MFC操作MySQL、MFC项目打包发布都是一条线串下来的事。这个项目正好是把C语法、数据结构和Windows界面编程捏在一起的最佳练习场景。2. 核心算法拆解从字符频率到Huffman树2.1 数据结构设计整个压缩器的基础是一棵二叉树。每个叶子节点对应一个字节值0~255内部节点不存数据只存权重。权重就是该子树下所有叶子节点出现次数的总和。C里我用一个结构体来承载节点信息typedef struct HuffNode { unsigned char ch; // 字节值仅叶子节点有效 unsigned long freq; // 出现频率 struct HuffNode* left; struct HuffNode* right; HuffNode() : ch(0), freq(0), left(nullptr), right(nullptr) {} } HuffNode;这里有几个细节需要讲明白第一freq用unsigned long而不是int。如果一个几GB的大文件要做压缩单个字节的出现次数可能超过21亿32位signed int直接溢出。unsigned long在Windows 64位下是4字节虽然上限也就42亿左右但配合后面的分批处理策略足够覆盖日常场景。真要处理超大规模文件可以进一步扩到unsigned long long代价是内存占用上升没必要一上来就拉满。第二构建Huffman树的标准做法是“贪心 优先队列”。每次从所有节点中取出频率最小的两个节点合并成一个新节点新节点的频率等于两者之和再丢回队列。循环到只剩一个根节点为止。这里有同学喜欢自己写数组扫描找最小值我个人不建议——时间复杂度是O(n²)字符种类只有256个时问题不大但如果将来你想扩展到双字节编码65536种O(n²)就会拖慢构建速度。直接上std::priority_queue代码又短又不容易出逻辑错误struct NodeCmp { bool operator()(HuffNode* a, HuffNode* b) { return a-freq b-freq; // 小顶堆频率小的优先 } }; std::priority_queueHuffNode*, std::vectorHuffNode*, NodeCmp minHeap;2.2 构建Huffman树的关键代码第一步读文件统计频率。我用一个256格的数组存计数每次读入4KB缓冲循环叠加unsigned long freqTable[256] { 0 }; char buffer[4096]; DWORD bytesRead 0; HANDLE hFile CreateFileA(srcPath, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, NULL); if (hFile INVALID_HANDLE_VALUE) { // 文件打开失败弹错误信息 return FALSE; } while (ReadFile(hFile, buffer, sizeof(buffer), bytesRead, NULL) bytesRead 0) { for (DWORD i 0; i bytesRead; i) { freqTable[(unsigned char)buffer[i]]; } } CloseHandle(hFile);搞完频率统计将所有freq 0的字节值包装成叶子节点扔进优先队列for (int i 0; i 256; i) { if (freqTable[i] 0) { HuffNode* node new HuffNode(); node-ch (unsigned char)i; node-freq freqTable[i]; minHeap.push(node); } }然后循环建树while (minHeap.size() 1) { HuffNode* left minHeap.top(); minHeap.pop(); HuffNode* right minHeap.top(); minHeap.pop(); HuffNode* parent new HuffNode(); parent-freq left-freq right-freq; parent-left left; parent-right right; minHeap.push(parent); } HuffNode* root minHeap.top();这段代码的逻辑核心就是“每次找最小的两颗子树合并”。有个细节要特别注意合并时左右子树的顺序不影响压缩率但会影响编码分配结果。你规定左边记0右边记1或者反过来都能编出合法前缀码只是最终二进制流不一样。稳妥起见统一约定左0右1即可。2.3 生成编码表递归遍历与快速查找树建好了下一步是给每个叶子节点生成对应的二进制编码串。经典做法是深度优先遍历从根节点出发向左走追加0向右走追加1void GenerateCodes(HuffNode* node, std::string code, std::string codes[256]) { if (!node) return; if (!node-left !node-right) { codes[node-ch] code; return; } GenerateCodes(node-left, code 0, codes); GenerateCodes(node-right, code 1, codes); }这里有个坑递归遍历的次数叶子节点数×平均深度深度可能超过几十层递归栈深度不是问题最多256层栈空间完全够。如果你的工程后面要做性能优化可以把递归改成显式栈的迭代版本但对当前项目来说递归版本可读性最好不需要过度设计。编码表生成后你可以立刻验证一个性质任何字符的编码都不是另一个字符编码的前缀。这是Huffman编码的核心优势也是解压时能够从比特流里连续解码的前提。验证方法很简单——把每个编码串写入一个哈希集合检查是否有某个编码是另一个编码的前缀串。3. 文件格式设计压缩包的重中之重3.1 压缩文件头部结构Huffman压缩并不是简单地把编码流写进文件就行你还需要设计好文件头让解压端知道怎么还原。我最终采用的文件格式如下字段大小说明文件标识2字节固定0x48 0x46HF校验文件类型原始文件大小8字节64位记录解压后应还原的字节数字符种类数2字节有效叶子节点个数叶子节点信息区变长每种字符的字节值和编码长度Huffman树恢复区变长前序遍历序列化结果编码数据区变长逐个字符按编码表写入的位流这里为什么不用建Huffman树时明确的频率表因为频率表在解压端没用解压只需要编码树的结构。你给解压端一堆频率值它还要重新建一次树麻烦且容易出错。直接把树结构序列化写进去解压端读进来就能用。树结构的序列化格式也简单——前序遍历遇到内部节点写0遇到叶子节点写1字节值。这样递归重建非常方便。还有那个“原始文件大小”字段千万别省。解压到最后一个字节时由于编码是按位写入的文件尾部必然存在填充位没有这个字段你不知道哪些位是有效数据哪些是凑数的。3.2 按位写入的实现细节C/C的文件API都是按字节操作的而Huffman编码是变长的位流。所以核心工作就是把编码串按位拼成一个字节再写入满了就落盘剩下最后不足8位的部分用0补齐。我实现了一个极简的BitWriter类class BitWriter { public: void WriteBits(const std::string bits) { for (char c : bits) { byteBuffer | ((c - 0) (7 - bitCount)); bitCount; if (bitCount 8) { fwrite(byteBuffer, 1, 1, outFile); byteBuffer 0; bitCount 0; } } } void Flush() { if (bitCount 0) { fwrite(byteBuffer, 1, 1, outFile); byteBuffer 0; bitCount 0; } } private: FILE* outFile; unsigned char byteBuffer 0; int bitCount 0; };写入时的核心顺序是“先写的高位”。比如某个字符的编码是101那它占第一个字节的高3位这个字节剩余5位留给后续字符。7 - bitCount这个位移值保证每次写入都紧接上一次的剩余位置。这个小类如果处理不好压缩出来的文件解压时大概率全部乱码——调试这种问题非常痛苦因为你在二进制层面根本看不出错误。踩过一次坑之后我的经验是写一个小测试用例用固定字符串比如abcabcabc走一遍压缩再解压逐步对比中间结果。3.3 压缩主流程代码压缩函数的完整逻辑如下BOOL CompressFile(const CString srcPath, const CString dstPath, CProgressCtrl progress) { // 1. 第一遍读文件统计频率 unsigned long freqTable[256] { 0 }; CountFrequency(srcPath, freqTable); // 2. 构建Huffman树并生成编码表 HuffNode* root BuildHuffmanTree(freqTable); std::string codes[256]; GenerateCodes(root, , codes); // 3. 打开输出文件先预留文件头位置 FILE* out fopen(dstPath, wb); if (!out) return FALSE; WriteFileHeader(out, srcPath, freqTable, root); // 4. 第二遍读文件按编码表逐字符写入 FILE* in fopen(srcPath, rb); BitWriter writer(out); char buffer[4096]; DWORD bytesRead 0; while ((bytesRead fread(buffer, 1, sizeof(buffer), in)) 0) { for (DWORD i 0; i bytesRead; i) { writer.WriteBits(codes[(unsigned char)buffer[i]]); } } writer.Flush(); fclose(in); fclose(out); return TRUE; }有个性能细节值得说如果你在循环里一个字符一个字符地调用fwrite速度会非常慢。所以代码里用4KB缓冲做批量读取WriteBits内部再累积到8位才落盘一次。两层缓冲加在一起压缩几十MB的文件耗时基本在毫秒级到秒级体验完全没问题。4. MFC界面与交互流程4.1 界面布局规划我用MFC对话框模板做了极简布局上方两个编辑框分别显示源文件路径和解压目标路径中间两个按钮“选择源文件”和“选择输出路径”下方两个主操作按钮“执行压缩”和“执行解压”再往下一条进度条和一个多行编辑框Log区域。控件类型和ID规划如下表纯经验值方便你对照着搭控件ID说明源文件编辑框IDC_EDIT_SRC只读路径由文件对话框填充输出路径编辑框IDC_EDIT_DST可编辑允许手动输入选择源文件按钮IDC_BTN_BROWSE_SRC打开CFileDialog执行压缩按钮IDC_BTN_COMPRESS主逻辑入口执行解压按钮IDC_BTN_DECOMPRESS主逻辑入口进度条IDC_PROGRESS显示压缩/解压进度日志列表IDC_EDIT_LOG多行文本只读输出过程信息4.2 按钮事件与主逻辑绑定MFC的按钮消息映射用ON_BN_CLICKED宏绑定。压缩按钮响应函数大概长这样void CHuffmanCompressDlg::OnBnClickedBtnCompress() { CString srcPath, dstPath; GetDlgItemText(IDC_EDIT_SRC, srcPath); GetDlgItemText(IDC_EDIT_DST, dstPath); if (srcPath.IsEmpty() || dstPath.IsEmpty()) { AfxMessageBox(_T(请先选择源文件和输出路径)); return; } // 用AfxBeginThread启动后台线程避免界面卡死 m_pThread AfxBeginThread(CompressWorkerThread, this); // 主线程继续跑消息循环进度条由工作线程通过PostMessage更新 }这里有个非常重要的实战经验压缩大文件时绝不能在UI线程里直接执行耗时操作。一个几百MB的文件光统计频率遍历写编码流就得好几秒主线程卡住会导致窗口无响应、进度条不刷新Windows会提示“程序未响应”。正确做法是用AfxBeginThread开工作线程算法跑完了再用PostMessage通知UI线程更新界面。工作线程里更新进度条你可以自定义一个消息#define WM_UPDATE_PROGRESS (WM_USER 101) // 工作线程中 ::PostMessage(hWnd, WM_UPDATE_PROGRESS, (WPARAM)percent, 0);然后在对话框类里加一个处理函数把percent直接设置给进度条控件。4.3 文件对话框使用细节选择文件那块MFC的CFileDialog有两种形态。普通模太对话框会阻塞界面但对选择文件这种短操作足够。有一个容易踩的坑是从CFileDialog里取出的路径可能是旧的8.3短路径格式也可能带C:\这种反斜杠结尾拼接输出路径时先做统一处理CFileDialog dlg(TRUE, _T(*), NULL, OFN_FILEMUSTEXIST | OFN_HIDEREADONLY, _T(All Files (*.*)|*.*||), this); if (dlg.DoModal() IDOK) { CString path dlg.GetPathName(); SetDlgItemText(IDC_EDIT_SRC, path); // 自动生成默认输出路径原名去掉扩展名后加上.hf CString newPath path.Left(path.ReverseFind(_T(.))); newPath _T(.hf); SetDlgItemText(IDC_EDIT_DST, newPath); }从选择源文件到自动填充输出路径这一步能省用户不少事。加密压缩包的扩展名我用成.hf和文件标识HF对应比较有辨识度。5. 解压流程与细节处理5.1 文件头解析与树重建解压是压缩的逆过程但顺序上有点反直觉读文件头、重建Huffman树、然后按位读取编码数据流、沿着树走叶子节点还原字节。文件头读取逻辑如下BOOL ReadAndRebuildTree(FILE* in, HuffNode* root) { // 校验文件标识 char magic[2]; fread(magic, 1, 2, in); if (magic[0] ! H || magic[1] ! F) { AfxMessageBox(_T(非法的压缩文件格式)); return FALSE; } // 读取原始文件大小 fread(origSize, 8, 1, in); // 读取叶子节点数2字节 unsigned short leafCount 0; fread(leafCount, 2, 1, in); // 之前压缩时记录每个叶子字节值这里直接重建树 root RebuildTreeFromFile(in, leafCount); return TRUE; }树重建的递归函数和压缩时的序列化函数一一对应HuffNode* RebuildTreeFromFile(FILE* in, unsigned short remainLeaves) { unsigned char flag; fread(flag, 1, 1, in); if (flag 0) { // 内部节点 HuffNode* node new HuffNode(); node-left RebuildTreeFromFile(in, remainLeaves); node-right RebuildTreeFromFile(in, remainLeaves); return node; } else { // 叶子节点 HuffNode* node new HuffNode(); fread(node-ch, 1, 1, in); remainLeaves--; return node; } }5.2 按位解码与文件还原解压时的核心循环是这样从压缩流里一次读1位根据位值决定走向左子树还是右子树每到达一个叶子节点就把ch写入输出文件然后回到根节点重新开始。一直到写出字节数等于文件头记录的大小为止。void DecompressCore(FILE* in, FILE* out, HuffNode* root, unsigned long long origSize) { BitReader reader(in); HuffNode* cursor root; unsigned long long written 0; while (written origSize) { int bit reader.ReadBit(); if (bit -1) break; // 数据耗尽防御处理 if (bit 0) cursor cursor-left; else cursor cursor-right; if (!cursor-left !cursor-right) { fwrite(cursor-ch, 1, 1, out); written; cursor root; } } }BitReader的读取逻辑是BitWriter的镜像每次读8位填充内部缓冲维护好位偏移就行。这里有个潜在bug如果压缩文件尾部填充位的0恰好构成某个字符的编码前缀且written origSize的判定放在循环尾部就会多写一字节。所以上面代码把written的检查放在循环开头先判断再解码能有效避免这种越界。5.3 解压结果校验解压完成后建议强制做一次大小校验// 解压完成后检查 if (written origSize) { Log(_T(解压成功共还原 %llu 字节), written); } else { Log(_T(解压失败预期 %llu 字节实际 %llu 字节), origSize, written); return FALSE; }对于重要文件我还会顺手算一下解压前后内容的CRC32或MD5做完整性比对。这一步不是必须的但加上了能让整个工具专业不少。6. 常见问题与排查技巧实录6.1 压缩后文件反而变大新手最容易碰到的现象是压缩一个原本已经很紧凑的文件比如JPEG、MP3、ZIP结果输出比输入还大。这不是代码Bug而是原理性的问题——Huffman对“数据本身已近熵上限”的文件没有增益还要额外付出存放文件头和树的字节开销。处理办法有两个方向要么压缩前判断一下字节种类数与文件尺寸比如果种类太多说明熵很高放弃压缩并提示用户要么至少让用户知道“本算法适合文本、日志、数据库备份等重复度高的数据对多媒体文件效果有限”。实操中我在压缩按钮里加了一个简单的阈值有效字符种类 200或压缩后大小 原始大小时输出警告日志并停止写文件而不是生成一个还不如下不压的文件。6.2 大文件内存溢出还记得最开始用unsigned long存频率吗如果压缩一个超大文件例如视频、磁盘镜像单字符出现次数可能超过unsigned long上限。虽然概率很低但稳妥起见可以把频率类型改成unsigned long long代价是内存占用从1KB变成2KB忽略不计。真正吃内存的是压缩过程中codes数组里存的编码字符串。最坏情况下每个字符的编码长度可能到256位256个字符最多也就64KB内存完全没问题。所以这个项目的内存瓶颈始终不在编码表而在文件读写缓冲的大小——4KB一读的策略对超大文件IO次数偏多可以提到64KB~1MB之间压缩速度会有明显提升。6.3 中文路径和文件权限问题MFC的CFileDialog返回的路径如果是C:\用户\测试文件.txt这种中文路径直接用fopen可能失败。原因在于窄字符版本的fopen依赖系统代码页Windows默认对中文路径支持不稳定。解决办法是使用宽字符版本的_wfopenFILE* in _wfopen(srcPath.GetString(), Lrb); FILE* out _wfopen(dstPath.GetString(), Lwb);这一点能省掉一大半“路径打不开”的毛病。此外如果输出路径所在的目录没有写权限比如Program Files下面程序会弹出权限错误。我在选择输出路径时默认跳到桌面或用户文档目录可以避开权限坑。6.4 进度条和界面卡顿已经说过用AfxBeginThread开线程这里补充一个很容易被忽视的细节工作线程里不能直接操作UI控件必须先PostMessage回UI线程。MFC内部控件不是线程安全的直接跨线程调用进度条的SetPos轻则界面刷不出来重则程序崩溃。正确姿势我已经写在4.2节核心就两步工作线程计算百分比PostMessage通知UI线程UI线程收到消息后调用SetPos。这样进度条丝滑刷新用户不会觉得程序卡死了。6.5 编码表节点内存泄漏最后谈谈树节点的内存管理。压缩和解压都涉及new出来的HuffNode只要建树就要记得释放。我封装了一个递归释放函数void FreeHuffmanTree(HuffNode* node) { if (!node) return; FreeHuffmanTree(node-left); FreeHuffmanTree(node-right); delete node; }在压缩结束和解压结束后各调用一次。别小看这一步虽然单次运行内存泄漏量不大但如果在MFC里反复压缩多个文件泄漏会慢慢累积最终导致进程内存飙升。7. 扩展优化方向做完一个能跑的Huffman压缩解压工具只是起点后面有太多值得折腾的方向。第一把静态Huffman改成动态Huffman。静态方案要扫描两遍文件一遍统计、一遍编码动态方案可以在一次扫描里同时构建并更新编码树虽然算法复杂不少但压缩率和速度都会有改善这也是Deflate所用的方案之一。第二引入算术编码或Range Coder。Huffman编码对每个符号固定分配整数个bit理论上对概率接近1的符号存在浪费。算术编码能把多个符号压缩到一个小数区间里压缩率更高但实现难度也上一个台阶。第三加入多线程编码。前面提到文件读取用缓冲循环你可以把一个大文件拆成多个块每个块独立构建Huffman树最后并行编码再用块索引组织输出。这个思路和zstd、lz4的frame格式某些层面是相通的做出来性能提升会非常可观。第四如果你手头正好在做OpenCV、Matlab相关实验会发现JPEG内部的Huffman编码和这个项目几乎是一个模子——唯一的差异是JPEG对DC系数用差分、对AC系数用Zigzag扫描再跑Huffman。底子打好了看其他格式源码就不发怵。我在实际开发中还有一个体会压缩算法这个领域标准的实现往往不是最难的难的是边界情况和异常处理。比如空文件、单个字符文件、恰好256种字符全出现的文件、文件末尾截断、磁盘写满——每一种情况都要想清楚程序该怎么表现。把这个工具当成一个“完整产品”而不是“作业”来打磨你会收获远超算法本身的东西。本文还有配套的精品资源点击获取