Visual C++ 12.0 Visual Studio 2013 VC++设计/图形架构师中级开发 Windows C++Linux

实现 Huffman 自适应算法来压缩 256 色深度图形图像

Arthur V. Ratz

4.94/5 (68投票s)

2015 年 8 月 22 日

CPOL

15分钟阅读

30327

2209

本文演示了如何实现 Huffman 自适应压缩算法来压缩 256 色深度图形图像和其他多媒体文件

引言

本文演示了如何实现 Huffman 自适应算法。该算法为灰度图像和 256 色深度图形图像提供无损压缩。Huffman 压缩算法由 David A. Huffman 于 1952 年发明。它是最高效的压缩算法，具有最小的代码冗余。最初，Huffman 压缩算法由其发明者用于压缩通过电缆或无线电频道信号传输的数据报。如今，Huffman 自适应算法被用作“有损”JPEG/MPEG 压缩器的“后端”。它还用于 RAR、ZIP 等压缩器的开发过程中。自 D. Huffman 创立以来，该算法基本上有两种修改：

经典 Huffman 算法，其中编码过程主要基于使用静态固定长度代码和构建 Huffman 树；
Huffman 自适应算法，它主要基于使用可变长度对称编码，而不是在编码过程中构建 Huffman 树；

使用 Huffman 自适应编码方法主要的好处是减少编码数据的量。它比经典的 Huffman 压缩算法提供更好的压缩比。

背景

经典的静态 Huffman 编码模型基于已估计的字符频率。每个字符的频率在编码过程之前进行估计。使用静态模型，我们首先构建 Huffman 树，从树中获取适当的代码，然后编码输入缓冲区中的每个字符。以下方法有两个缺点：

需要两次查看编码后的字符序列。这可能会导致性能下降；
为了正确解码，必须将整个 Huffman 树和频率表传递给解码器；

因此，我们实现了基于可变长度对称代码的 Huffman 自适应算法。它提供即时数据编码，无需构建 Huffman 树或处理字符序列一次以上。

通常，Huffman 自适应算法比静态 Huffman 编码模型以及算术编码或概率编码等其他压缩算法更具成本效益。

例如，Huffman 自适应算法用于 UNIX 操作系统 POSIX 的一部分 `compact` 工具。

注意：本文讨论的 Huffman 自适应压缩算法实现只能用于压缩任意文件大小的灰度或 256 色深度图像或其他多媒体文件。经过编码的文件不应使用 JPEG/MPEG/RAR/ZIP 等其他压缩算法进行预先压缩。

使用 Huffman 自适应编码算法对数据进行编码

在本节中，我们将演示如何使用 Huffman 自适应算法对字符串进行编码。假设我们有一个包含字符串“ABBRRAAACCAADDAABBRAAA”的输入字符缓冲区。该字符串长 23 字节。它由在字符串中出现多次的字符组成。我们想使用 Huffman 自适应算法对其进行压缩。要将 Huffman 自适应编码应用于字符串，我们通常需要遍历字符字符串。我们对字符串中的每个字符执行编码。Huffman 自适应算法的主要思想是编码从“空”Huffman 树开始，该树

不包含字符的条目。该树将通过追加新字符及其代码来进一步修改。在编码或解码过程中，Huffman 树都应以类似方式修改。在这两种情况下，我们都需要为输入字符缓冲区中的每个字符生成相同的代码。回想一下，在 Huffman 自适应编码/解码期间，我们实际上不需要构建 Huffman 树。我们正在使用代码生成方法来生成 Huffman 代码。但有一个重要的限制：在编码大量数据时，使用以下方法生成代码的代码空间可能会逐渐耗尽。请注意，我们只分配 8 位（1 字节）代码空间来为每个编码字符生成代码。我们使用左移位按位运算“<<”来生成新代码值。对于要编码的输入缓冲区中的最多八个字符，可以生成代码。在这种情况下，我们必须重新初始化 Huffman 树或字符频率表。

此时，让我们快速回顾一下 Huffman 自适应编码过程。作为 Huffman 自适应编码的一个例子，我们将编码上面列出的字符串的前六个字符。下一个字符串的第一个字符是‘A’=65₁₀ = (01000001)₂。该字符的 ASCII 码表示为 8 位序列。由于此时 Huffman 树为空，它被未编码地附加到输出缓冲区。通常，第一个字符被附加到 Huffman 树，并且其代码最初被指定为 0₂。我们必须将此字符附加到频率表中，并将与给定字符关联的字符频率计数器变量的值设置为“1”。最后，输出缓冲区将如下所示：01000001。在 Huffman 自适应编码算法中，我们使用可变长度代码。它有时可能被误认为 8 位长的未编码字符。为避免此冲突，在编码过程中，我们必须使用转义码。它表示为一定位的序列。它在每个未编码字符之前被附加到输出缓冲区。在编码第一个字符‘A’时，转义码的值为“1”。从输入缓冲区中检索的下一个字符是‘B’。我们正在 Huffman 树中执行线性搜索，以验证该字符的适当代码是否已存在于 Huffman 树中。这表明该字符已被编码。通常，我们对从输入缓冲区中检索的每个字符执行线性搜索。如果当前字符不存在于 Huffman 树中，我们首先要做的是使用当前转义码 ESC_CODE = 1 获取字符‘B’的代码。这可以通过执行以下按位运算来完成：NEW_CODE = ESC_CODE << 1。在这种特定情况下，字符‘B’的代码是 NEW_CODE = 2₁₀ = 10₂。之后，当前转义码和未编码字符都将被附加到输出缓冲区。此时，输出缓冲区将具有以下位序列：01000001 1 01000010。接下来，我们需要将新字符及其代码 NEW_CODE = 10₂ 附加到 Huffman 树，该代码可以在上面获得，并使用以下按位运算计算新转义码的值：NEW_ESC_CODE = NEW_CODE + 1。显然，转义码的新值为 NEW_ESC_CODE = 3₁₀ = 11₂。下一个字符也是字符‘B’，它已存在于 Huffman 树中。在这种情况下，我们需要将适当的代码附加到输出缓冲区。显然，字符‘B’的代码是 10₂，在这种情况下，输出缓冲区包含：01000001 1 01000010 10。我们还需要将给定字符在频率表中的频率计数器加“1”。字符‘B’的计数器值为“2”。这意味着字符‘B’在输入缓冲区中出现了两次。最后，我们必须使用快速排序算法按字符出现频率的值对频率表进行排序。然后我们必须修改 Huffman 树。出现频率最高的字符使用最短代码进行编码。长度最长的代码对应于出现频率最低的字符。从输入缓冲区中检索的下一个字符是‘R’。此字符也第一次出现，在 Huffman 树中没有条目。显然，我们使用上面讨论的方法获取以下字符的代码和转义序列：NEW_CODE = 6₁₀ = 110₂，NEW_ESC_CODE = 7₁₀ = 111₂。在这种情况下，输出缓冲区将包含以下位序列：01000001 1 01000010 10 11 01010010。在编码过程结束时，Huffman 树将包含以下字符代码：

字符	频率	code	转义码
A	2	0₂	1₂
B	2	10₂	11₂
R	2	110₂	111₂

我们从输入缓冲区检索的另外两个字符是‘R’和‘A’。这两个字符已被编码，每个字符的代码都可以在 Huffman 树中找到。在这种情况下，R = 110₂，A = 0₂。我们将这两个代码附加到输出缓冲区。我们将得到以下序列：01000001 1 01000010 10 11 01010010 110 0。作为上面描述的 Huffman 自适应编码的结果，我们得到了以下数据报：

ABBRRA (L = 48 位) => 010000011010000101011010100101100 (L= 33 位)。

图 1 显示了说明 Huffman 自适应编码过程的框图。正如从上面的输出可以看出，Huffman 自适应编码能够用一个仅为 33 位长的位序列来编码一个（6 字节 x 8 位 = 48 位）长度的字符串。这意味着 Huffman 自适应方法也提供了数据压缩。Huffman 自适应编码的压缩比可以使用以下表达式进行评估：$r=1-\frac{L_{OUT}}{L_{IN}}=1-\frac{33}{48}\approx 1-0.69\approx 0.31$。根据理论，经典静态 Huffman 压缩模型算法在数据编码过程中使用固定长度的静态代码可确保压缩比为 0.27。Huffman 自适应算法的另一个优点是它不需要将生成的 Huffman 树与输出缓冲区中包含的编码数据报一起存储。这使得用于存储编码数据的空间量显著紧凑。

在本篇文章的下一节中，我们将讨论用于解码使用 Huffman 自适应算法编码的数据的算法。对于下面的编码算法，输出缓冲区实际上是一个位序列。每个数字都有其绝对位置。我们需要将每个位或一部分位附加到受控位序列的末尾，使用其在当前序列中的绝对位置。不幸的是，在编程中，没有数据结构可以用来实现位序列。而且，也没有允许设置或修改单个位的操作。大多数现有的 CPU 允许处理长度为 1 字节 = 8 位的数据。我们将使用字节数组来实现特定长度的位序列。我们需要实现一个长度为 L = 48 位的位序列。我们将实际使用一个字节数组，其大小为 48/8 = 6 字节。图 2 说明了位序列作为字节数组的表示。

另一个最重要的方面是实现例程，用于将位的绝对位置转换为数组中特定字节的相对位位置。为此，我们首先必须通过计算字节索引的值来定位数组中的字节。我们使用以下表达式，其中是位的绝对位置。序列中的所有位都以可逆顺序索引。这意味着最高有效位属于数组中的第一个字节。最低有效位位于最后一个字节内。我们需要通过从分配用于存储位序列的总字节数 `_huff_buf_size` 中减去上述表达式来修改表达式。最后，我们将得到以下表达式，该表达式在程序中实现为 C 宏（请参阅源代码了解有关此宏如何使用的更多信息）。

#define _huff_op_nbyte(nbit) ((_huff_buf_size-1)-nbit/(1<<3))

假设，如果我们有一个绝对位位置 Nbit = 11，数组大小 = 2 字节，那么我们可以使用上面的表达式计算字节索引：((2-1) – 11/8) = 1 – 1 = 0。这意味着，具有绝对位置的位位于索引 Nbyte = 0（第一个字节）的字节中；

之后，我们将不得不使用以下表达式计算指定位的相对位置

#define _huff_loc_nbit(nbit) ((_huff_bits-1)-                                          \
	(((_huff_bits*_huff_buf_size - 1) - (_huff_bits*_huff_op_nbyte(nbit))) - nbit)) \

在这种情况下，我们计算一个字节中的最高位位置 `_huff_bits`-1；例如（8-1）=7；
然后，我们将字节中的位数乘以数组的总字节数。我们这样做是为了找到位序列中的最高绝对位位置。例如：（8 * 2 – 1）= 15；
我们将字节中的位数乘以该位所属字节的索引，并获得相对于该位所属字节的最高位位置。在这种情况下，此值为 0 = (8 * 0)；
我们减去最高绝对位位置和相对于字节的最高位位置以及指定的位位置以获得特定位的偏移量值。
最后，我们将上一步的值从相对于字节的最高位位置中减去，例如，它等于 7。

$ (8-1)-((8*2-1|8*((2-1)-11/8)|-11) = 3$

$ 7 – (15 – |8 * (1 – 1)) – 11|) = 3$

使用 Huffman 自适应可变长度对称代码解码数据

假设我们有一个数据报 01000001 1 01000010 10 11 01010010 110 0。它编码了一定的字符序列。通常，我们将此序列视为输入缓冲区，并遍历表示为位序列的缓冲区。对于检索到的每一位或一部分位，我们执行以下解码操作。图 3 说明了 Huffman 自适应解码过程。最初，我们需要从数据报中检索前八位。这是一个表示字符 ASCII 码的字节。它被未编码地放置在序列的开头。在这种情况下，它是 01000001₂ = 65₁₀ = ‘A’。显然，这是字符‘A’的 ASCII 码。此时，我们将此字符附加到输出缓冲区或 Huffman 树。然后，我们将与该字符关联的代码指定为“0”。请注意，此时输出缓冲区将包含以下字符：OUTPUT = "A"。由于 Huffman 树是空的，这是第一个编码的字符。此外，我们需要初始化转义序列，使其等于 ESC_CODE = "1"。接下来，我们从输入缓冲区中检索下一个 8 位，并将其附加到临时原始位序列。之后，我们将检查原始位序列的值是否与转义码的值完全匹配。如果是，我们将不得不从输入缓冲区中检索接下来的 8 位。我们必须将其视为特定字符的 ASCII 码。最后，我们将它附加到 Huffman 树，并为该字符生成适当的代码。在这种特定情况下，原始位序列的值为“1”，这完全匹配转义码的值。我们可以从输入缓冲区中检索接下来的 8 位。最后，我们将得到下一个字符的 ASCII 码 01000010₂ = 66₁₀ = ‘B’。我们还将它附加到输出缓冲区：OUTPUT = "AB"。同样，我们将字符‘B’附加到 Huffman 树，并使用上面描述的方法获得新代码：NEW_CODE = 2₁₀ = 10₂。此外，我们需要重新计算转义码的值：ESC_CODE = 3₁₀ = 11₂。最后，我们必须刷新临时原始缓冲区，然后继续处理下一个位，其索引为 17。

我们显然需要将此位附加到原始缓冲区，并检查它是否不等于转义码的值。正如我们所注意到的，转义码的值与原始缓冲区的内容不完全匹配。因此，我们将不得不在线性搜索 Huffman 树中查找与原始缓冲区值相等的代码。在这种情况下，Huffman 树中没有适当的代码。因此，我们目前不执行任何解码。我们将接下来的第 18 位附加到原始缓冲区。此时，原始缓冲区将包含以下位序列 RAW_BUFFER = 10₂。我们必须执行类似的检查，以确保这不等于转义码的值 ESC_CODE=11₂。在这种情况下，它不是，然后我们将执行线性搜索 Huffman 树。最后，我们找到了代码 10，它映射到字符‘B’，我们将它附加到输出缓冲区：OUTPUT = "ABB"。同样，我们将从输入缓冲区中检索第 19 位和第 20 位。我们将它们附加到原始缓冲区。在这种情况下，此值等于当前转义码的值。我们需要从输入缓冲区中检索下一个 8 位序列。该序列是 01010010₂，对应于字符‘R’的 ASCII 码。我们将此字符附加到输出缓冲区，其中将包含以下字符串：OUTPUT = "ABBR"。显然，我们将此字符附加到 Huffman 树，其代码为 NEW_CODE = 6₁₀ = 110₂。我们从输入缓冲区中检索下一个位。最后，我们将获得原始缓冲区的以下值 RAW_BUFFER = 110₂，这是 Huffman 树中字符‘R’的代码。我们将此字符附加到输出缓冲区。我们将得到以下字符串：OUTPUT = "ABBRR"。同样，输入缓冲区中的下一个位是‘0’。此值显然代表代码，该代码也可以通过线性搜索在 Huffman 树中找到，并且可以获得与给定字符关联的适当 ASCII 码——01000001₂=65₁₀=‘A’。通过将此字符附加到输出缓冲区，我们将得到最终解码的字符串，如下所示：OUTPUT = "ABBRRA"

010000011010000101011010100101100 (L = 33 位) => "ABBRRA" (L = 48 位)。

关注点

我已经实现了 Huffman 自适应算法，用于压缩存储在大型 SQL 生产数据库中 BLOB 对象中的 256 色深度图形图像，以压缩存储整个数据库所占用的空间。本文讨论的 Huffman 自适应算法的实现也可以在 DEFLATE 压缩算法的实现中使用，以提供 LZ 系列算法的“后端”压缩。此外，Huffman 自适应算法还可以在 JPEG 和 MP3 等多媒体编解码器的实现中使用。