algorithm - 规范的霍夫曼编码比特流的内容是什么？

Question

让我们考虑以下使用符号-代码长度-规范代码数据的示例。

A - 2 - 00
B - 2 - 01
D - 2 - 10
C - 3 - 110 
E - 3 - 111

我想知道编码比特流的内容是什么？它是 00 01 10 110 111(基本上所有代码)还是二进制等效的 2,2,2,3,3 作为相应的代码长度？我想在这里补充一点，一些资源说只是将代码作为编码比特流传输，而很少有其他资源谈到将代码从编码比特流中删除并仅传输代码长度数据。

Answer 1

编码比特流

代码是:

00 01 10 110 111

请注意，如果我们发送 2,2,2,3,3 的代码，则无法确定输入是 AAACC 还是 BBBEE(或许多其他等效选择)。

因为霍夫曼编码是 prefix code这意味着我们可以在不知道空格位置的情况下明确解码比特流。

换句话说，当给定输出 000110110111 时，我们可以将其唯一解码为 ABDCE。

传输码表

我认为混淆可能是因为你需要拥有两个东西来解码比特流:

1. 编码比特流
2. 查找表

这两个东西通常以截然不同的方式编码。

在许多情况下，查找表是预先固定的，因此不需要传输。

但是，如果概率可以改变，那么我们需要告诉接收者使用什么代码表。在这种情况下，我们可以只传输每个代码字的长度，这为接收器提供了足够的信息来构造规范的霍夫曼代码。替代方案也是可能的，例如，我们可以发送每个代码字长度的数字，后跟值。 JPEG 使用此替代方法，并在下面进行了详细说明。

例子

JPEG 图像编解码器使用哈夫曼表。通常使用一些默认表，但可以通过传输自定义霍夫曼代码来优化图像的大小。关于此的教程是 here .

哈夫曼表传输方式的另一种描述是here .代码长度(以字节为单位)后跟代码值(同样以字节为单位)。

读取它的代码(取自链接)是:

// Next sixteen bytes are the counts for each code length
u8 counts[16];
for (i = 0; i < 16; i++) {
    counts[i] = fgetc(fp);
    ctr++;
}

// Remaining bytes are the data values to be mapped
// Build the Huffman map of (length, code) -> value
for (i = 0; i < 16; i++) {
    for (j = 0; j < counts[i]; j++) {
        huffData[table][huffKey(i + 1, code)] = fgetc(fp);
        code++;
        ctr++;
    }
    code <<= 1;
}