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

Question

我正在写一个Huffman文件,我在那里将规范代码的代码长度存储在文件的标题中.在解码过程中,我能够重新生成规范代码并将它们存储到一个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 */
}