Huffman 编码 | 最优前缀码压缩

>> 功能亮点

[OPTIMAL]

最优码长

在给定频率分布下，生成平均码长最短的前缀码。

[PREFIX-FREE]

前缀码

任意一个码字都不是另一个码字的前缀，保证了解码的唯一性。

[ADAPTIVE]

频率驱动

出现频率越高的字符自动获得越短的码字，提高整体压缩率。

>> 技术细节

Huffman 编码的工作原理

Huffman 编码通过自底向上构建一棵二叉树来生成前缀码。算法从每个字符的出现频率开始，反复取出频率最低的两个节点合并为一个父节点，直到只剩下根节点。沿左子树走记为 '0'，沿右子树走记为 '1'。频率越高的字符离根越近，因此码字更短，从而在给定频率分布下实现最优无损压缩。

Huffman 编码示例

Text: "AABBBCCCC"

Frequencies:
A: 2
B: 3
C: 4

Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)

Tree:
     Root(9)
    /      \
   C(4)    AB(5)
          /     \
        A(2)    B(3)

Codes:
C: 0
A: 10
B: 11

Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000

为什么要使用 Huffman 编码？

接近信息论极限的压缩率
实现简单、易于在工程中落地
是 ZIP / JPEG 等格式中的核心组成部分
无损压缩，不丢失任何数据
在实际生产环境中经过长期验证

>> 常见问题

什么是 Huffman 编码？

Huffman 编码是一种最优前缀码无损压缩算法，由 David A. Huffman 于 1952 年提出。算法根据字符的出现频率为其分配不同长度的比特串，频率越高的字符使用越短的码字，从而尽可能减小平均码长。

为什么叫“前缀码”或“前缀无歧义”？

所谓前缀码，是指任何一个码字都不是另一个码字的前缀。例如若字符 A 的码字为 "01"，那么其他字符的码字都不能以 "01" 开头。这样一来，在解码时沿着比特流从左到右扫描，就可以不依赖分隔符唯一地确定每一个码字。

Huffman 编码的压缩效果如何？

对于给定的频率分布，Huffman 编码可以达到理论熵极限附近的最优压缩，一般在 1 bit 以内。对英文文本常见的压缩率大约在 60–70%，当字符频率差异较大时效果尤其明显。

Huffman 编码通常用在什么地方？

Huffman 编码被广泛应用在 JPEG 图像压缩、ZIP 文件压缩（在 DEFLATE 中与 LZ77 结合）、MP3 音频以及许多其他格式中。通常它会与其它算法组合使用，例如 JPEG 在 DCT 和量化之后使用 Huffman，而 ZIP 在 LZ77 之后使用 Huffman。

[Base64.sh]

> huffman | 最优 | 编码 <