实验06：哈夫曼编码

1.实验目的：

理解贪心算法的思想，掌握哈夫曼编码的技术和图像编解码算法的基本。

2.实验内容：

统计图像像素灰度值的分布特性，利用哈夫曼编码构造码表，实现对图像的编码和解码。

3.实验要求：

首先完成图像分布统计并基于统计特性构造哈夫曼码表保存于文件中；然后利用哈夫曼码表实现对lena图像的编码并保存为码流文件（即二进制文件），统计压缩率（编码后比特数除以编码前比特数）；最后利用哈夫曼码表对码流文件解码，检测是否能正确解码。

$\square$ 基础性实验 $\square$ 综合性实验 $⊠$ 设计性实验

一、问题分析（模型、算法设计和正确性证明等）

根据图像像素值构造霍夫曼树，设$C$是图像不同像素值集合，其中每个像素值$c$的出现次数（频率）是$f(c)$，在霍夫曼树中的深度是 d T ( c ) d_T(c) dT​(c)，$x,y$是$C$中具有最小出现次数的两个像素值。在这个问题中要求解的是 ∑ c ∈ C f ( c ) d T ( c ) \\sum_{c\\in C}{f(c)d_T(c)} ∑c∈C​f(c)dT​(c)的最小值，下简述霍夫曼树构造过程（算法设计）。

统计每个像素值出现次数最为霍夫曼树的权值，先把每个像素值设置为叶节点，每次合并两个权值最小的节点，直到只剩下最后一个节点即可，构造过程使用小根堆实现。

算法正确性：

存在$C$的一棵最优前缀编码树$T$，其中$x$和$y$具有2项性质：

1. 深度最大，即编码长度最长
2. 兄弟叶结点，即仅最后一位编码不同

证明性质1，假设$x,y$不是$T$中深度最大的叶子结点，则将树$T$中深度最大的一对兄弟叶结点和$x,y$的对调得到新树 T ′ T' T′。因为$x,y$出现次数（频率）最小，对调后平均码长减小，所以 T ′ T' T′比$T$更优，矛盾。

证明性质2，最优编码树中x, y都在最深层，但两者原来不为兄弟，则交换后可为兄弟，编码长度不变，所以编码树仍最优。

最优子结构性质：树T’是字符集 C ′ = C − { x , y } ⋃ { z } C' = C - \\{x, y\\} \\bigcup \\{z\\} C′=C−{x,y}⋃{z}的一棵最优前缀编码树。

证明：
B ( T ) = ∑ c ∈ C f ( c ) d T ( c ) = ∑ c ∈ C − { x , y } f ( c ) d T ( c ) + ( f ( x ) + f ( y ) ) ( d T ( z ) + 1 ) = ∑ c ∈ C − { x , y } f ( c ) d T ( c ) + f ( z ) d T ( z ) + f ( x ) + f ( y ) = ∑ c ∈ C − { x , y } ⋃ { z } f ( c ) d T ( c ) + f ( x ) + f ( y ) = B ( T ′ ) + f ( x ) + f ( y ) B(T)=\\sum_{c\\in C}f(c)d_T(c)\\\\ =\\sum_{c\\in C-\\{x,y\\}}f(c)d_T(c)+(f(x)+f(y))(d_T(z)+1)\\\\ =\\sum_{c\\in C-\\{x,y\\}}f(c)d_T(c)+f(z)d_T(z)+f(x)+f(y)\\\\ =\\sum_{c\\in C-\\{x,y\\}\\bigcup \\{z\\}}f(c)d_T(c) + f(x) + f(y)\\\\ =B(T')+f(x)+f(y) B(T)=c∈C∑​f(c)dT​(c)=c∈C−{x,y}∑​f(c)dT​(c)+(f(x)+f(y))(dT​(z)+1)=c∈C−{x,y}∑​f(c)dT​(c)+f(z)dT​(z)+f(x)+f(y)=c∈C−{x,y}⋃{z}∑​f(c)dT​(c)+f(x)+f(y)=B(T′)+f(x)+f(y)
假设$T$是$C$的最优编码树，但是 T ′ T' T′不是 C ′ C' C′的最优编码树，

那么 C ′ C' C′上存在 T ′ ′ T'' T′′是最优的，则将 T ′ ′ T'' T′′中的结点$z$⽤⼦树 { x , y } \\{x, y\\} {x,y}展开，得到的 T ′ ′ ′ T''' T′′′ 是 $C$ 的编码树，且 T ′ ′ ′ T''' T′′′ ⽐ $T$ 更优。这与 $T$ 为最优⽭盾。

二、算法设计复杂度分析（伪代码，不要粘贴源码）

时间复杂度：$T(n)\in \theta (n\log n)$

空间复杂度：$S(n)\in \theta (2\times n-1)=\theta (n)$

三、实验结果记录和分析（测试向量上的测试结果、运行时间）

运行时间：$369.024ms$

压缩率：$237612/262144\ast 100\%=90.64\%$

四、总结（可描述出现的问题和解决方法、经验和反思等）

与动态规划图像压缩方式相比，霍夫曼编码压缩方式无需考虑压缩文件像素值的分布，只考虑出现频率，因此动态规划的压缩效果一定程度上与图像像素值相关，而霍夫曼编码压缩效果不会受到较大影响。