霍夫曼代码表

Question

我不明白Jpeg的霍夫曼表包含什么,有人可以向我解释一下吗？谢谢

Answer 1

霍夫曼编码是一种可变长度数据压缩方法.它的工作原理是将输入流中最频繁的值分配给具有最小位长度的编码.

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

Letter  Count
------  -----
e          10
<SPC>       4
l           3
sy          2
Smvrkgant.  1
<EOF>       1

文件结束标记EOF在那里,因为您的文件通常必须有8位的倍数.这是为了阻止最后的任何填充被视为真正的角色.

                                 __________#__________
                ________________/______________       \
       ________/________                   ____\____   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中的Huffman表只是允许您将流解压缩为可用信息的表.

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一个特殊的位序列开始,旨在将新的实际字节引入表中.

在表中引入新字节时,您将输出介绍器位序列,然后输出该字节的完整8位.

然后,在输出每个字节并更新计数之后,基于新计数重新平衡表/树是最节省空间的(尽管可以推迟重新平衡以提高速度,您只需确保相同的延迟发生在解压缩期间,一个例子是每次为输入的第一个1K添加字节,然后每10K输入一次,假设您自上次重新平衡后添加了新字节).

这意味着表本身可以在另一端以完全相同的方式构建(解压缩),从仅具有EOF导入器序列的相同最小表开始.

在解压缩期间,当你看到的引导顺序,可以将字节后它(上接第8位)表为零的计数,输出字节添加,然后调整计数和再平衡(或如前面提到的推迟).

这样,您不必将表附带压缩文件.当然,这会在压缩和解压缩期间花费更多的时间,因为你会定期重新平衡桌子,但是,就像生活中的大多数事情一样,这是一种权衡.