用二叉树实现哈夫曼算法、哈夫曼树提升压缩比率及可逆压缩和非可逆压缩

ゞ浴缸里的玫瑰 2024-04-03 08:31 65阅读 0赞

**目录**

一、用二叉树实现哈夫曼算法

二、哈夫曼树能够提升压缩比率

三、可逆压缩和非可逆压缩

--------------------

## 一、用二叉树实现哈夫曼算法 ##

上一篇博客已经提到，莫尔斯编码是根据日常文本中各字符的出现频率来决定表示各字符的编码数据长度的。不过该编码体系中，对 **AAAAAABBCDDEEEEEF** 这种文本来说并不是效率最高的

下面用哈夫曼算法试一下，哈夫曼算法是指，为各压缩对象文件分别构造最佳的编码体系，并以该编码体系为基础来进行压缩。因此，用什么样的编码（哈夫曼编码）对数据进行分隔，就要由各个文件而定。用哈夫曼算法压缩过的文件中，存储着哈夫曼编码信息和压缩过的数据

![e1161cdbd3e840aea944ce4abc0d90fc.png][]

下面，对**AAAAAABBCDDEEEEEF** 中的A - F的字符，按照 **出现频率高的字符用尽量少的位数编码来表示** 这一原则进行整理。按照出现频率从高到低的顺序整理后，结果如下，同时也列出了编码方案：

在上表编码方案中，随着出现频率的降低，字符编码信息的数据位数逐渐增加，从最开始的1位、2位一次增加到3位。不过这个编码体系是存在问题的，你不知道100这个3位的编码，它的意思是用1、0、0这三个编码来表示E、A、A呢？还是用10、0来表示B、A呢？还是用100来表示C呢？

而在哈夫曼算法中，通过借助哈夫曼树的构造编码体系，即使在不使用字符区分符号的情况下，也可以构建能够进行区分的编码体系。不过哈夫曼树的算法要比较复杂，下面式一个哈夫曼树的构造构成

自然界树的从根开始生叶，而哈夫曼树则是叶生枝

![d306d975de1d44b2997548159af120f5.png][]

## 二、哈夫曼树能够提升压缩比率 ##

使用哈夫曼树之后，出现频率越高的数据所占用的位数越少，这也是哈夫曼树的核心思想。通过上图的步骤二可以看出，枝条连接数据时，我们是从出现频率较低的数据开始的。这就意味着出现频率低的数据到达根部的枝条也越多。而枝条越多则意味着编码的位数随之增加

接下来我们来看哈夫曼树的压缩比率，用上图得到的数据表示**AAAAAABBCDDEEEEEF** 为

**000000000000 100100 110 101101 0101010101 111**,40位 = 5字节。压缩前的数据是17字节，压缩后的数据达到了惊人的5字节，也就是压缩比率 = 5 /17 = 29%，达到了如此高的压缩率

可以参考一下，无论哪种类型的数据，都可以用哈夫曼树作为压缩算法：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="text-align:center;"><strong>文件类型</strong></td> 
   <td style="text-align:center;"><strong>压缩前</strong></td> 
   <td style="text-align:center;"><strong>压缩后</strong></td> 
   <td style="text-align:center;"><strong>压缩比率</strong></td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">文本文件</td> 
   <td style="text-align:center;">14862字节</td> 
   <td style="text-align:center;">4119字节</td> 
   <td style="text-align:center;">28%</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">图像文件</td> 
   <td style="text-align:center;">96062字节</td> 
   <td style="text-align:center;">9456字节</td> 
   <td style="text-align:center;">10%</td> 
  </tr> 
  <tr> 
   <td style="text-align:center;">EXE文件</td> 
   <td style="text-align:center;">24576字节</td> 
   <td style="text-align:center;">4652字节</td> 
   <td style="text-align:center;">19%</td> 
  </tr> 
 </tbody> 
</table>

## 三、可逆压缩和非可逆压缩 ##

图像文件的使用目的通常是把图像数据传输到显示器、打印机等设备上。常用的图像格式有：**BMP、JPEG、TIFF、GIF**格式等

> BMP：是使用Windows自带的画笔来做成的一种图像形式
> 
> JPEG：是数码相机等常用的一种图像数据形式
> 
> TIFF：是一种通过在文件中包含"标签"就能够快速显示出数据形式的图像形式
> 
> GIF：是由美国开发的一种数据形式，要求色数不超过256个

图像文件可以使用RLE算法和哈夫曼算法，因为图像文件在多数情况下并不要求数据需要还原得到压缩之前一模一样的状态，允许丢失一部分数据。我们把能还原到压缩前状态的压缩称为 **可逆压缩** ，无法还原到压缩前状态的压缩称为 **非可逆压缩**

![54e01ee1ad844d32beca293aee347841.png][]

一般来说，JPEG格式的文件是非可逆压缩，因此还原后有部分图像信息比较模糊。GIF是可逆压缩

[e1161cdbd3e840aea944ce4abc0d90fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/02a22a3dd32b4e7daccefece261be935.png
[d306d975de1d44b2997548159af120f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/0fd897de066e480283e38b2935cb9990.png
[54e01ee1ad844d32beca293aee347841.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/58ad5fd8c18c4362a58c76b8fa0d3dd9.png