huffman-code - 从规范形式解码霍夫曼文件

Question

我正在编写一个霍夫曼文件，我将规范代码的代码长度存储在文件的标题中。在解码过程中，我能够重新生成规范代码并将它们存储到 std::map<std:uint8_it, std::vector<bool>> 中。 .实际数据读入单个std::vector<bool> .在有人建议我使用 std::bitset 之前，让我澄清一下，霍夫曼码具有可变位长，因此，我使用 std::vector<bool> .那么，鉴于我有我的符号及其相应的规范代码，我该如何解码我的文件？我不知道从这里去哪里。有人可以向我解释我将如何解码这个文件，因为我在搜索时找不到与它相关的任何内容。

Answer 1

您不需要创建代码或树来解码规范代码。您所需要的只是按顺序排列的符号列表以及每个代码长度中的符号数。 “按顺序”是指按代码长度从最短到最长排序，并在每个代码长度内按符号值排序。

由于代码长度内的规范代码是连续的二进制整数，您可以简单地进行整数比较以查看您拥有的位是否在该代码范围内，如果是，则进行整数减法以确定它是哪个符号。

以下是来自 puff.c 的代码(略有改动)以明确显示这是如何完成的。 bits(s, 1)从流中返回下一位。 (这假设总有下一位。)h->count[len]是按长度编码的符号数 len代码，其中 len在 0..MAXBITS .如果加起来h->count[1] , h->count[2] , ..., h->count[MAXBITS] ，即编码的符号总数，即h->symbol[]的长度大批。第一个h->count[1] h->symbol[] 中的符号长度为 1。下一个 h->count[2] h->symbol[] 中的符号有长度 2。等等。
h->count[] 中的值数组，如果正确，则被限制为不能超额订阅可以在 len 中编码的可能数量的代码。位。可以进一步约束表示一个完整的代码，即没有未定义的位序列，在这种情况下 decode()不能返回错误 (-1)。要使代码完整且未超额订阅，h->count[len] << (MAXBITS - len) 的总和整体len必须等于 1 << MAXBITS .

简单的例子:如果我们正在编码 e一位，t有两位，和 a和 o三位，然后 h->count[]是 {0, 1, 1, 2} (第一个值，h->count[0] 未使用)，和 h->symbol[]是 {'e','t','a','o'} .然后代码到e是 0 , t的代码是 10 , a是 110 , 和 o是 111 .

#define MAXBITS 15              /* maximum bits in a code */

struct huffman {
    short *count;       /* number of symbols of each length */
    short *symbol;      /* canonically ordered symbols */
};

int decode(struct state *s, const struct huffman *h)
{
    int len;            /* current number of bits in code */
    int code;           /* len bits being decoded */
    int first;          /* first code of length len */
    int count;          /* number of codes of length len */
    int index;          /* index of first code of length len in symbol table */

    code = first = index = 0;
    for (len = 1; len <= MAXBITS; len++) {
        code |= bits(s, 1);             /* get next bit */
        count = h->count[len];
        if (code - count < first)       /* if length len, return symbol */
            return h->symbol[index + (code - first)];
        index += count;                 /* else update for next length */
        first += count;
        first <<= 1;
        code <<= 1;
    }
    return -1;                          /* ran out of codes */
}