霍夫曼码表

Question

我不明白你的JPEG的霍夫曼表包含，可能有人给我讲解一下？ 由于

Answer 1

霍夫曼编码是一种可变长度的数据压缩方法。它通过将输入流中最频繁的值分配给具有最小比特长度的编码来工作。

例如，输入Seems every eel eeks elegantly.可编码信e作为二进制1和所有其它字母各种其他较长的代码，所有的起始与0。这样，结果比特流将小于每个字母都是固定大小的情况。举例来说，让我们检查每个角色的数量并构建一个树，将常见的角色放在顶部。

​​

文件标记EOF的结尾是有，因为你通常必须有八位的倍数您的文件。这是为了阻止任何填充被视为真正的角色。

        __________#__________ 
       ________________/______________  \ 
     ________/________     ____\____ e 
    __/__    __\__    __/__  \ 
/ \   / \   / \ /\ 
/  \  /  \  / SPC l s 
/\ /\  /\ /\  /\ 
y S m v / k g \  n t 
       /\  /\ 
       r .  a EOF 

现在，这并不一定是最高效树，但它足以建立的编码是如何完成的。我们先看看未压缩的数据。假设一个八位编码的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，因为它需要一个字节的整数倍，但仍然未压缩数据的大小约一半。

现在，对于像这样的小文件来说，这通常是不划算的，因为您必须添加实际树自身占用的空间，否则您无法在另一端对其进行解码。但是当然，对于角色分布不均匀的大型文件，这可能会导致节省空间。

所以，毕竟，在一个JPEG的霍夫曼表是简单的，让你解压缩流成有用的信息表。

JPEG的编码过程由几个不同的步骤组成（颜色转换，色度分辨率降低，基于块的离散余弦变换等等），但最后一步是每个块上的无损Huffman编码，读取图像时使用表格进行反转。

---

^（一）也许最佳情况下，此表的最小存储会是这样的：

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和引导序列相同的最小表。

在解压缩期间，当你看到的引导顺序，可以将字节后它（上接第8位）表为零的计数，输出字节添加，然后调整计数和重新平衡（或延迟如前所述）。

这样，您不必将压缩文件附带的表格。当然，这在压缩和解压缩期间需要花费更多时间，因为您定期重新平衡桌面，但与生活中的大多数情况一样，这是一种折衷。

Answer 2

DHT标记不直接指定哪个符号与代码关联。它包含一个向量，其中包含给定长度的代码数。之后它包含一个带有符号值的向量。

所以，当你想解码你必须从第一个向量生成的哈夫曼代码，然后将每个代码与第二个向量中的符号相关联。