从规范形式解码Huffman文件

Question

从规范形式解码Huffman文件

4

我正在编写一个Huffman文件，将规范码的代码长度存储在文件头中。在解码期间，我能够重新生成规范码并将它们存储到std::map<std:uint8_it, std::vector<bool>>中。实际数据读入单个std::vector<bool>中。在任何人建议我使用std::bitset之前，让我澄清一下，Huffman码具有可变位长，因此我使用std::vector<bool>。那么，考虑到我有我的符号及其对应的规范码，我该如何解码我的文件？我不知道从哪里开始。有人能给我解释一下如何解码这个文件吗？因为我在搜索时找不到相关的内容。

- WDRKKS

一般来说，解压缩的过程就是将前缀码流翻译成单个字节值的过程，通常是通过遍历哈夫曼树节点并在从输入流读取每个位时进行。—哈夫曼编码。 - royhowie

2个回答

1

您的地图包含相关信息，但它将符号映射到代码。然而，您试图解码的数据由代码组成。因此，由于查找方法需要一个符号，所以不能使用您的地图有效地获取与读取的代码对应的符号，搜索代码并检索相应的符号将是线性搜索。

相反，您应该重建用于压缩步骤的Huffman树。这里内部节点的频率值是无关紧要的，但您需要正确位置的叶节点。您可以在读取文件头时即时创建树。最初创建一个空树。对于每个要映射的符号和代码，创建树中相应的节点。例如，如果符号“D”被映射到代码101，则确保在根节点处有一个右子节点，它有一个左子节点，它有一个右子节点，其中包含符号“D”，如果缺少节点则创建节点。

使用该树，您可以按以下方式解码流（伪代码，假设右子节点对应于将1添加到代码中）：

// use a node variable to remember the position in the tree while reading bits
node n = tree.root
while(stream not fully read) {
    read next bit into boolean b
    if (b == true) {
        n = n.rightChild
    } else {
        n = n.leftChild
    }
    // check whether we are in a leaf node now
    if (n.leftChild == null && n.rightChild == null) {
        // n is a leaf node, thus we have read a complete code
        // add the corresponding symbol to the decoded output
        decoded.add(n.getSymbol())
        // reset the search
        n = tree.root
    }
}

请注意，将地图反转以获得正确方向的查找仍将导致性能不佳（与二叉树遍历相比），因为它无法像遍历那样利用对较小搜索空间的限制。

- muued

谢谢回复，muued。我确实有一些疑问。decoded.add(n.getSymbol())...这是我将生成的代码与映射中的现有代码匹配并添加到文件中的地方，对吗？我正在使用std::back_inserter进行添加。另外，如何检查叶节点？node == NULL，对吗？最后，您提到了反转映射...我应该在哪里反转映射？请告诉我。谢谢。 - WDRKKS

我尝试通过编辑进一步解释。decoded.add(n.getSymbol()) 是您成功将读取的代码与符号匹配并将其附加到输出文件的位置。叶子检查是显式执行的。您可以反转映射以获取从代码到符号的映射。这个方向是您想要的，因为您读取代码并希望得到相应的符号。但是，树遍历是更好的方法。 - muued

好的...现在我对这个有了清晰的认识。我会尝试实现并看看它的表现如何。但是还有一件事。由于我在压缩步骤中使用频率构建树，而且我没有将频率写入文件，你也提到频率值是无关紧要的，那么我应该如何仅使用我的映射来重新创建树？我试图搜索此内容，但找不到任何信息。请告诉我这个。非常感谢您的帮助。谢谢。 - WDRKKS

你可以使用你的映射表，或者（更简单的方法）在读取文件时直接使用文件中的信息，从而避免创建映射表。我已经在另一个编辑中解释了如何创建树。正如你所看到的，你只需要创建节点并将符号放入叶子节点中，不需要频率。 - muued

好的...我想我可以处理这个。我会尝试实现它并看看会发生什么。如果遇到任何问题，我会再次在这里发布。非常感谢您的帮助，muued。 - WDRKKS

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mark Adler · Accepted Answer

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

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

以下是源自 puff.c（经过轻微更改）的代码，以明确显示如何执行此操作。 bits(s, 1) 会从流中返回下一个位。（假设始终存在下一个位。）h->count[len] 是编码为长度为 len 的代码的符号数，其中 len 在 0..MAXBITS 范围内。如果将 h->count[1]、h->count[2]，...，h->count[MAXBITS] 相加，那么就是编码的总符号数，并且是 h->symbol[] 数组的长度。在 h->symbol[] 中的前 h->count[1] 个符号具有长度为 1。在 h->symbol[] 中的接下来 h->count[2] 个符号具有长度为 2。以此类推。 h->count[] 数组中的值（如果正确）受到限制，不能超出可以在 len 位中编码的可能代码数。它可以进一步约束以表示完整的代码，即不存在未定义的位序列，在这种情况下，decode() 将不会返回错误（-1）。对于完整且未过度订阅的代码，所有 len 上的 h->count[len] << (MAXBITS - 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 */
}