哈夫曼编码（Huffman Coding）——交互演示与验证

原理简介

哈夫曼编码是一种基于符号频率构造前缀(无歧义)最优二进制编码的方法。对符号的概率分布，哈夫曼算法产生平均码长最短的无前缀码。

熵：$$H(X)=-\sum_i p_i\log_2 p_i$$ 平均码长：$$\bar{L}=\sum_i p_i l_i$$ Kraft 不等式：$$\sum_i 2^{-l_i}\le 1$$

交互：输入文本 / 频率构建哈夫曼树

树形可视化（SVG）

编码结果

符号 — 频率 — 代码

编码位串（部分）：

统计量

符号总数：—

熵 H：— bits

平均码长 L：— bits

理论下界：H ≤ L < H+1

压缩比（相对 8-bit）：—

应用

  • 数据压缩（如 ZIP 的部分变体、图像/文本编码前的熵编码）。
  • 与算术编码、霍夫曼变种一起用于实际编解码器。
  • 通信系统中统计冗余的去除与信源编码。