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