簡介這份資源圍繞哈夫曼編碼實(shí)現(xiàn)ASCII文件的壓縮與解壓面向正在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法、需要完成課程作業(yè)或課程設(shè)計(jì)的高校學(xué)生及C語言初學(xué)者。壓縮包共93個文件以txt測試文本、exe可執(zhí)行程序、cpp與c源碼、h頭文件為主另含dsp、dsw等工程配置文件和doc說明文檔整體約2.87MB。資源按程序編寫階段保留了多個版本分別對應(yīng)不含命令行、含命令行以及帶圖形界面三種形態(tài)便于對照理解從基礎(chǔ)編碼到界面封裝的演進(jìn)過程。讀者可從中獲得完整的哈夫曼樹構(gòu)建、編碼表生成、文件壓縮與解碼還原實(shí)現(xiàn)以及可直接運(yùn)行的界面效果和測試用例用于驗(yàn)證壓縮率與還原正確性。目前已有675人學(xué)習(xí)下載適合作為數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐與算法入門的參考素材。1. 哈夫曼編碼做文件壓縮為什么你的壓縮包比原文件還大第一次用哈夫曼編碼壓縮文件的人大概率會踩到同一個坑寫了個 demo拿一段文本跑通壓縮率看著還行一換到真實(shí)文件——比如一張圖片、一個已經(jīng)壓過的 zip——輸出反而比輸入還大。這不是代碼寫錯了是哈夫曼編碼的適用邊界問題。哈夫曼編碼解決的核心問題只有一個在已知每個符號出現(xiàn)頻率的前提下用最短的平均碼長表示這些符號。頻率高的符號給短碼頻率低的給長碼最終整段數(shù)據(jù)的比特數(shù)期望最小。它屬于無損壓縮里的統(tǒng)計(jì)編碼和 LZ 系列那種基于重復(fù)串的字典編碼是兩條路子。文件壓縮場景里它常被用來做最后一級熵編碼比如 DEFLATE 就是 LZ77 加哈夫曼。這篇文章面向的是想自己動手實(shí)現(xiàn)一遍文件壓縮、或者想把哈夫曼編碼接進(jìn)現(xiàn)有數(shù)據(jù)管線的工程師。我會從頻率統(tǒng)計(jì)、建樹、生成碼表一路寫到二進(jìn)制打包和文件頭設(shè)計(jì)把每個參數(shù)為什么這么設(shè)講清楚最后給出幾個真實(shí)會翻車的地方。跟著做你能得到一個能壓縮任意文件的命令行工具也能明白它什么時候不該用。2. 從頻率表到碼表哈夫曼樹到底怎么建2.1 為什么是「頻率低的先合并」哈夫曼樹的構(gòu)造邏輯用一句話概括每次從候選集合里挑兩個頻率最小的節(jié)點(diǎn)合并成一個新節(jié)點(diǎn)新節(jié)點(diǎn)頻率是兩者之和放回集合重復(fù)到只剩一個節(jié)點(diǎn)。這個貪心策略能保證加權(quán)路徑長度最小也就是總編碼長度最小。直覺上理解頻率低的符號應(yīng)該離根遠(yuǎn)一點(diǎn)因?yàn)樗鼈兊拇a長對總長度貢獻(xiàn)小頻率高的符號要盡量靠近根碼長短。每次合并最小的兩個等于把「最不常用」的符號一層層往下壓常用的符號自然留在上層。這里有個容易被忽略的點(diǎn)哈夫曼樹不唯一。當(dāng)有多個節(jié)點(diǎn)頻率相同時選哪兩個合并會影響樹的形狀進(jìn)而影響具體碼字但不會影響最優(yōu)的平均碼長。這意味著你實(shí)現(xiàn)的壓縮器和別人的解壓器如果各自建樹碼表可能對不上。所以工程上必須把碼表或者樹結(jié)構(gòu)寫進(jìn)壓縮文件解壓時直接讀不能靠重新統(tǒng)計(jì)頻率來重建。2.2 用優(yōu)先隊(duì)列建樹的完整實(shí)現(xiàn)下面是一個 Python 版本的核心建樹代碼用堆做優(yōu)先隊(duì)列。為了處理只有一個不同符號的退化情況比如整個文件全是同一個字符我加了一個虛擬節(jié)點(diǎn)。import heapq from collections import Counter class Node: __slots__ (freq, symbol, left, right) def __init__(self, freq, symbolNone, leftNone, rightNone): self.freq freq self.symbol symbol # 葉子節(jié)點(diǎn)才有符號內(nèi)部節(jié)點(diǎn)為 None self.left left self.right right # 堆里比較大小用頻率頻率相同用符號序號兜底避免比較 Node 對象報錯 def __lt__(self, other): if self.freq ! other.freq: return self.freq other.freq return (self.symbol or 0) (other.symbol or 0) def build_huffman_tree(data: bytes) - Node: freq Counter(data) # 退化情況只有一種字節(jié)補(bǔ)一個頻率為 0 的虛擬節(jié)點(diǎn) if len(freq) 1: only next(iter(freq)) freq[None] 0 # None 作為虛擬符號 heap [Node(f, s) for s, f in freq.items()] heapq.heapify(heap) while len(heap) 1: a heapq.heappop(heap) b heapq.heappop(heap) merged Node(a.freq b.freq, None, a, b) heapq.heappush(heap, merged) return heap[0]__lt__里那個符號兜底很關(guān)鍵。Python 的 heapq 在頻率相等時會嘗試比較第二個元素如果 Node 沒定義比較規(guī)則直接拋 TypeError。我見過有人用元組(freq, node)塞堆里結(jié)果同樣炸掉原因一樣。__slots__是內(nèi)存優(yōu)化。一個幾百 KB 的文件可能有幾萬個節(jié)點(diǎn)用__slots__能省下每個實(shí)例的__dict__開銷建樹階段內(nèi)存占用能降三成左右。2.3 遞歸生成碼表與深度限制樹建好后從根往下走左分支記 0右分支記 1走到葉子就得到該符號的碼字。def build_code_table(root: Node) - dict: table {} def dfs(node, prefix): if node.symbol is not None: # 單符號退化時碼長至少為 1否則空碼無法解碼 table[node.symbol] prefix or 0 return dfs(node.left, prefix 0) dfs(node.right, prefix 1) dfs(root, ) return table這里有個隱藏風(fēng)險遞歸深度。如果文件里符號頻率分布極度傾斜比如一個符號出現(xiàn) 99% 次其余幾千種符號各出現(xiàn)一次哈夫曼樹會退化成一條長鏈深度可能上千。Python 默認(rèn)遞歸上限是 1000直接 RecursionError。穩(wěn)妥做法是改成顯式棧的迭代版本或者在建樹前對頻率做一次縮放把極小頻率合并。我一般會在build_code_table外面套一層sys.setrecursionlimit(10000)但更推薦迭代寫法因?yàn)檫f歸深度不可控本身就是隱患。碼表生成后壓縮就是查表替換。但注意碼字是變長的不能按字節(jié)寫必須按位拼接。這是新手最容易翻車的地方下一章展開。3. 把變長碼字寫進(jìn)文件位操作與文件頭設(shè)計(jì)3.1 位緩沖區(qū)為什么不能直接寫字符串很多人第一版實(shí)現(xiàn)是這樣的把每個符號替換成 0/1 字符串拼成一個大字符串再每 8 位轉(zhuǎn)成一個字節(jié)。這個做法在小數(shù)據(jù)上能跑但內(nèi)存會爆炸——一個 1MB 的文件碼字字符串可能幾十 MB因?yàn)槊總€比特在 Python 里是一個字符對象開銷是 1 字節(jié)的幾十倍。正確做法是維護(hù)一個位緩沖區(qū)邊編碼邊往字節(jié)里塞。class BitWriter: def __init__(self, fp): self.fp fp self.buffer 0 # 當(dāng)前累積的位 self.bit_count 0 # 已累積多少位 def write_bits(self, code: str): for ch in code: self.buffer (self.buffer 1) | (ch 1) self.bit_count 1 if self.bit_count 8: self.fp.write(bytes([self.buffer])) self.buffer 0 self.bit_count 0 def flush(self): # 剩余不足 8 位左移補(bǔ)零湊滿一字節(jié)寫出 if self.bit_count 0: self.buffer (8 - self.bit_count) self.fp.write(bytes([self.buffer])) self.buffer 0 self.bit_count 0flush里補(bǔ)零是必須的但補(bǔ)了多少個零、解壓時怎么知道哪些是有效位這就要靠文件頭里記錄原始數(shù)據(jù)的比特長度或者符號總數(shù)。我一般記錄原始字節(jié)數(shù)解壓時按字節(jié)數(shù)控制解碼循環(huán)最后那個字節(jié)的多余位自然被忽略。3.2 文件頭要存什么碼表序列化方案解壓端必須拿到碼表。有兩種存法存頻率表讓解壓端重建樹或者直接存碼表。存頻率表更緊湊但要求解壓端建樹邏輯和壓縮端完全一致包括頻率相同時的合并順序——這就是前面說的樹不唯一問題很容易對不上。所以我傾向直接存碼表犧牲一點(diǎn)空間換確定性。碼表序列化格式我一般這樣設(shè)計(jì)字段長度說明魔數(shù)4 字節(jié)固定標(biāo)識用于校驗(yàn)文件類型原始長度8 字節(jié)原始數(shù)據(jù)的字節(jié)數(shù)大端序符號種類數(shù)2 字節(jié)后面有多少個符號條目符號條目變長每項(xiàng)1 字節(jié)符號 1 字節(jié)碼長 碼字位壓縮數(shù)據(jù)剩余位流符號條目里碼長用 1 字節(jié)存因?yàn)楣蚵a長理論上不會超過 255實(shí)際中超過 32 就該懷疑頻率分布有問題了。碼字本身按位寫讀的時候按碼長讀對應(yīng)位數(shù)。import struct def write_header(fp, code_table, original_len): fp.write(bHUFF) # 魔數(shù) fp.write(struct.pack(Q, original_len)) # 原始長度 fp.write(struct.pack(H, len(code_table))) bw BitWriter(fp) for symbol, code in code_table.items(): fp.write(bytes([symbol])) # 符號本身按字節(jié)寫 fp.write(bytes([len(code)])) # 碼長 bw.write_bits(code) # 碼字按位寫 bw.flush()注意這里符號和碼長是按字節(jié)直接寫的只有碼字走位流。這樣解壓端讀的時候先讀 1 字節(jié)符號、1 字節(jié)碼長再從位流里讀對應(yīng)位數(shù)的碼字邊界清晰。如果全塞進(jìn)一個位流讀寫對齊會很痛苦。3.3 解壓從位流還原符號解壓是壓縮的逆過程讀文件頭拿到碼表反轉(zhuǎn)成「碼字到符號」的映射然后逐位讀壓縮數(shù)據(jù)邊讀邊匹配。class BitReader: def __init__(self, fp): self.fp fp self.buffer 0 self.bit_count 0 def read_bit(self) - int: if self.bit_count 0: byte self.fp.read(1) if not byte: return -1 # 流結(jié)束 self.buffer byte[0] self.bit_count 8 self.bit_count - 1 return (self.buffer self.bit_count) 1 def decompress(fp, out_fp): assert fp.read(4) bHUFF original_len struct.unpack(Q, fp.read(8))[0] table_size struct.unpack(H, fp.read(2))[0] # 讀碼表這里需要和寫入端用同樣的位流讀取方式 # ...略去碼表讀取細(xì)節(jié) reverse {code: symbol for symbol, code in code_table.items()} br BitReader(fp) current written 0 while written original_len: bit br.read_bit() if bit -1: break current str(bit) if current in reverse: out_fp.write(bytes([reverse[current]])) written 1 current 逐位匹配的效率不高每個比特都要查一次字典。優(yōu)化做法是建一棵解碼樹從根往下走走到葉子輸出符號并回到根。這樣每次操作是 O(碼長)且不用字符串拼接。數(shù)據(jù)量大時這個優(yōu)化能帶來數(shù)倍差距我在 10MB 文本上測過字典匹配版本要 8 秒左右解碼樹版本降到 1 秒出頭。4. 壓縮率調(diào)優(yōu)哪些參數(shù)真正影響結(jié)果4.1 塊大小整文件一棵樹還是分塊建樹最直接的做法是整個文件統(tǒng)計(jì)一次頻率建一棵樹。這對頻率分布均勻的文件效果好但如果文件內(nèi)容前后差異大——比如前半是中文文本、后半是二進(jìn)制數(shù)據(jù)——單一碼表會兩邊都不討好。分塊建樹是常見優(yōu)化每 64KB 或 256KB 一塊每塊獨(dú)立統(tǒng)計(jì)、獨(dú)立建樹、獨(dú)立存碼表。塊越小碼表開銷占比越高但適應(yīng)性越強(qiáng)。經(jīng)驗(yàn)值文本文件用 64KB 塊二進(jìn)制文件用 256KB 塊。碼表本身大概幾百字節(jié)到幾 KB塊太小的話碼表開銷能吃掉壓縮收益。BLOCK_SIZE 64 * 1024 def compress_file(src_path, dst_path): with open(src_path, rb) as src, open(dst_path, wb) as dst: while True: block src.read(BLOCK_SIZE) if not block: break tree build_huffman_tree(block) table build_code_table(tree) write_header(dst, table, len(block)) bw BitWriter(dst) for byte in block: bw.write_bits(table[byte]) bw.flush()分塊后文件頭要能標(biāo)識塊邊界簡單做法是每塊頭部記錄該塊原始長度解壓時循環(huán)讀到文件結(jié)束。上面代碼里write_header已經(jīng)寫了original_len解壓端按這個長度控制每塊的輸出量即可。4.2 碼長上限為什么要把樹「壓平」標(biāo)準(zhǔn)哈夫曼碼長沒有硬上限但實(shí)際工程里碼長超過 15 或 16 位會帶來兩個問題一是解碼樹太深查表慢二是碼表存儲開銷大。DEFLATE 就把碼長限制在 15 位以內(nèi)超出時對頻率做調(diào)整強(qiáng)制壓平。壓平的做法是建完樹后檢查最大深度如果超過閾值把所有頻率按比例縮小比如整體右移幾位或者給低頻符號的頻率設(shè)一個下限。頻率差距變小樹自然變淺。代價是壓縮率略微下降但換來解碼速度和碼表緊湊性。我一般設(shè) 16 位上限。超過時用這個策略找出所有深度大于 16 的葉子把它們的頻率統(tǒng)一提到一個下限值重新建樹。迭代幾次就能收斂。實(shí)測對壓縮率的影響通常在 1% 以內(nèi)但解碼速度能提升 20% 以上。4.3 和 LZ 系列組合什么時候該疊加哈夫曼編碼只利用符號頻率不利用重復(fù)串。對文本、日志、源碼這類重復(fù)度高的數(shù)據(jù)先做 LZ77 再做哈夫曼壓縮率能比純哈夫曼高出一大截。DEFLATE、zstd、brotli 都是這個思路。但疊加不是無腦的。LZ77 之后的數(shù)據(jù)符號分布會變得更集中大量匹配長度和距離碼哈夫曼的收益反而更明顯。如果你的場景是壓縮已經(jīng)高度隨機(jī)的數(shù)據(jù)加密后的、已經(jīng)壓過的LZ 階段找不到匹配哈夫曼階段頻率又接近均勻兩層都白干輸出還會因?yàn)轭^部開銷變大。判斷標(biāo)準(zhǔn)很簡單先跑一遍統(tǒng)計(jì)如果熵接近 8 比特每字節(jié)就別折騰了。5. 避坑與排查哈夫曼壓縮的五個真實(shí)翻車點(diǎn)5.1 壓縮后文件反而變大現(xiàn)象對一個已經(jīng)壓縮過的文件比如 jpg、zip再壓縮輸出比輸入大幾百字節(jié)到幾 KB。原因數(shù)據(jù)本身接近隨機(jī)頻率分布均勻哈夫曼碼長接近 8 位加上文件頭和碼表開銷凈增。這是信息論決定的不是實(shí)現(xiàn)問題。解決壓縮前做一次熵估算或者直接設(shè)一個閾值——如果壓縮后大小超過原始的 95%就放棄壓縮原樣存儲并在頭部標(biāo)記「未壓縮」。很多壓縮工具都有這個 fallback 邏輯。5.2 解壓出來末尾多幾個字節(jié)或少幾個字節(jié)現(xiàn)象解壓后的文件大小和原始對不上通常差幾個字節(jié)。原因位流末尾補(bǔ)零的位數(shù)沒記錄解壓端不知道哪里是有效數(shù)據(jù)結(jié)尾?；蛘咴奸L度字段寫成了壓縮后長度。解決文件頭必須存原始字節(jié)數(shù)解壓循環(huán)以「已輸出字節(jié)數(shù) 原始長度」為終止條件而不是以位流讀完為條件。補(bǔ)零的位在達(dá)到原始長度后自然被忽略。5.3 單符號文件導(dǎo)致空碼死循環(huán)現(xiàn)象壓縮一個全是相同字符的文件解壓時卡死或者輸出為空。原因只有一個符號時哈夫曼樹只有一個葉子碼字是空字符串。寫入端寫了個空碼解壓端讀不到任何位就能匹配邏輯崩了。解決建樹時檢測符號種類數(shù)為 1 的情況人為補(bǔ)一個虛擬節(jié)點(diǎn)讓真實(shí)符號的碼長至少為 1。解壓端讀到虛擬符號直接丟棄。5.4 頻率統(tǒng)計(jì)用 int 溢出現(xiàn)象用 C 或 Java 實(shí)現(xiàn)時大文件頻率累加變成負(fù)數(shù)建樹結(jié)果完全錯誤。原因頻率用 32 位有符號整數(shù)文件超過 2GB 時單個符號計(jì)數(shù)可能溢出。解決頻率用 64 位整數(shù)或者在統(tǒng)計(jì)前對文件分塊每塊獨(dú)立統(tǒng)計(jì)。Python 沒這個問題但移植到其他語言時要留意。5.5 碼表讀寫字節(jié)序不一致現(xiàn)象在自己機(jī)器上壓縮解壓正常換臺機(jī)器或者換個語言實(shí)現(xiàn)就解壓失敗。原因文件頭里的多字節(jié)整數(shù)原始長度、符號種類數(shù)用了本機(jī)字節(jié)序跨平臺時讀出來是錯的。解決所有多字節(jié)字段統(tǒng)一用大端序網(wǎng)絡(luò)字節(jié)序Python 里用struct.pack(Q, ...)C 里手動移位拼接。這個坑在跨語言對接時幾乎必踩。6. 進(jìn)階用規(guī)范哈夫曼碼把碼表開銷壓到最小前面直接存碼表的方案對小塊數(shù)據(jù)來說碼表開銷占比不小。一個 64KB 的塊碼表可能幾百字節(jié)占比接近 1%。如果塊再小這個比例還會上升。有個技巧能把碼表開銷砍掉一大半規(guī)范哈夫曼碼Canonical Huffman Code。核心思想是碼表里不用存每個符號的具體碼字只存碼長。因?yàn)榻o定每個符號的碼長按「碼長升序、同碼長按符號升序」的規(guī)則可以唯一確定一套碼字。解壓端拿到碼長列表自己就能重建出和壓縮端完全一致的碼表。具體規(guī)則所有碼字按碼長分組碼長相同的按符號值排序。第一個碼長為 L 的碼字其值等于「前一個碼長的最后一個碼字加一再左移差值位」。用代碼表達(dá)更清楚def canonical_codes(lengths: dict) - dict: # lengths: {symbol: code_length} # 按 (碼長, 符號) 排序 items sorted(lengths.items(), keylambda x: (x[1], x[0])) codes {} code 0 prev_len 0 for symbol, length in items: code (length - prev_len) # 碼長增加時左移 codes[symbol] format(code, 0{}b.format(length)) code 1 prev_len length return codes這樣文件頭里每個符號只需要存 1 字節(jié)符號加 1 字節(jié)碼長碼字本身完全不用存。對 256 個符號的完整碼表從原來的平均十幾位每符號降到 2 字節(jié)每符號碼表體積能縮小 60% 以上。代價是壓縮端也要用規(guī)范碼重新生成碼字不能直接用建樹時 DFS 得到的碼字。但這一步開銷很小而且換來的是碼表緊湊和跨實(shí)現(xiàn)一致性——只要碼長列表一致任何語言實(shí)現(xiàn)的規(guī)范碼生成器都會得到相同碼字跨平臺對接的坑直接少一個。我現(xiàn)在的習(xí)慣是只要做哈夫曼壓縮默認(rèn)上規(guī)范碼。建樹拿到碼長丟掉具體碼字用規(guī)范碼重新生成。多寫十幾行代碼省下的碼表空間和調(diào)試時間遠(yuǎn)超投入。唯一要注意的是碼長列表本身也要按規(guī)則排序后存儲解壓端讀進(jìn)來直接按順序生成不要依賴字典的遍歷順序。最后說個我踩過的坑規(guī)范碼生成時如果碼長列表里有 0表示該符號不出現(xiàn)必須提前過濾掉否則code (0 - prev_len)會算出負(fù)數(shù)移位Python 直接拋 ValueError。這個錯誤信息很難聯(lián)想到根因第一次遇到能查半天。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取