我不明白 Jpeg 的霍夫曼表包含什么，有人可以向我解释一下吗？谢谢
问问题
7501 次
2 回答
16
霍夫曼编码是一种可变长度数据压缩方法。它通过将输入流中最频繁的值分配给具有最小位长度的编码来工作。
例如，输入Seems every eel eeks elegantly.可以将字母编码e为二进制1，将所有其他字母编码为各种其他更长的代码，均以0. 这样，生成的比特流将小于每个字母都是固定大小的情况。举例来说，让我们检查每个字符的数量并构造一棵将常见字符放在顶部的树。
Letter Count
------ -----
e 10
<SPC> 4
l 3
sy 2
Smvrkgant. 1
<EOF> 1
文件结束标记EOF在那里，因为您的文件中通常必须有八位的倍数。这是为了阻止最后的任何填充被视为真实角色。
__________#__________
________________/______________ \
________/________ ____\____ e
__/__ __\__ __/__ \
/ \ / \ / \ / \
/ \ / \ / SPC l s
/ \ / \ / \ / \ / \
y S m v / k g \ n t
/\ / \
r . a EOF
现在这不一定是最有效的树，但足以确定编码是如何完成的。我们先来看看未压缩的数据。假设使用 8 位编码，这 31 个字符（对于未压缩的数据我们不需要EOF）将占用 248 位。
但是，如果你使用上面的树来定位字符，如果你选择左边的子树输出一个零位，如果你选择右边的输出一个位，你会得到以下结果：
Section Encoding
---------- --------
Seems<SPC> 00001 1 1 00010 0111 0101 (20 bits)
every<SPC> 1 00011 1 001000 00000 0101 (22 bits)
eel<SPC> 1 1 0110 0101 (10 bits)
eeks<SPC> 1 1 00101 0111 0101 (15 bits)
elegantly 1 0110 1 00110 001110 01000 01001 0110 00000 (36 bits)
.<EOF> 001001 001111 (12 bits)
总共有 115 位，因为它需要是字节的倍数，所以四舍五入到 120，但这仍然是未压缩数据大小的一半左右。
现在对于像这样的小文件通常不值得这样做，因为您必须添加实际树本身占用的空间(a)，否则您无法在另一端对其进行解码。但可以肯定的是，对于字符分布不均匀的较大文件，它可以显着节省空间。
因此，毕竟，JPEG 中的霍夫曼表只是允许您将流解压缩为可用信息的表。
JPEG 的编码过程包括几个不同的步骤（颜色转换、色度分辨率降低、基于块的离散余弦变换等），但最后一步是对每个块进行无损 Huffman 编码，这些表用于读取图像时反转。
(a)最小存储该表的最佳情况可能是：
Size of length section (8-bits) = 3 (longest bit length of 6 takes 3 bits)
Repeated for each byte:
Actual length (3 bits, holding value between 1..6 inclusive)
Encoding (n bits, where n is the actual length)
Byte (8 bits)
End of table marker (3 bits) = 0 to distinguish from actual length above
对于上面的文字，那将是：
00000011 8 bits
n bits byte
--- ------ -----
001 1 'e' 12 bits
100 0101 <SPC> 15 bits
101 00001 'S' 16 bits
101 00010 'm' 16 bits
100 0111 's' 15 bits
101 00011 'v' 16 bits
110 001000 'r' 17 bits
101 00000 'y' 16 bits
101 00101 'k' 16 bits
100 0110 'l' 15 bits
101 00110 'g' 16 bits
110 001110 'a' 17 bits
101 01000 'n' 16 bits
101 01001 't' 16 bits
110 001001 '.' 17 bits
110 001111 <EOF> 17 bits
000 3 bits
这使得表 264 位完全消除了压缩带来的节省。但是，如前所述，随着输入文件变大，表格的影响会变得越来越小，并且有一种方法可以完全避免使用该表格。
这种方式涉及使用霍夫曼的另一种变体，称为自适应霍夫曼。这是表实际上并未存储在压缩数据中的地方。
相反，在压缩过程中，表以EOF一个特殊的位序列开始，旨在将一个新的实际字节引入表中。
当向表中引入一个新字节时，您将输出引入位序列，后跟该字节的全部八位。
然后，在输出每个字节并更新计数后，表/树会根据新计数重新平衡以最节省空间（尽管重新平衡可能会延迟以提高速度，但您只需要确保发生相同的延迟在解压过程中，一个例子是每次你为前 1K 的输入添加字节，然后每 10K 的输入，假设你在上次重新平衡后添加了新字节）。
这意味着表本身可以在另一端以完全相同的方式构建（解压缩），从相同的最小表开始，仅具有EOF和介绍器序列。
解压过程中，当看到introducer序列时，可以将其后面的字节（接下来的八位）添加到计数为零的表中，输出字节，然后调整计数并重新平衡（或如前所述延迟） ）。
这样，您不必将表与压缩文件一起提供。当然，这会在压缩和解压过程中花费更多时间，因为您会定期重新平衡表格，但与生活中的大多数事情一样，这是一种权衡。
于 2011-02-10T06:39:05.953 回答
0
DHT 标记不直接指定与代码关联的符号。它包含一个向量，其中包含给定长度的代码数量。之后，它包含一个带有符号值的向量。
因此，当您要解码时，您必须从第一个向量生成霍夫曼代码，然后将每个代码与第二个向量中的符号相关联。
于 2011-02-11T08:45:30.820 回答