从规范形式解码Huffman文件
我正在编写一个Huffman文件，其中我存储了文件头中规范代码的代码长度。在解码过程中，我能够重新生成规范代码并将它们存储到std::map<std:uint8_it, std::vector<bool>>中。实际数据被读取到单个std::vector<bool>中。在有人建议我使用std::bitset之前，让我澄清一下，霍夫曼码具有可变的位长，因此，我使用std::vector<bool>。那么，假设我有我的符号及其对应的规范代码，我该如何解码我的文件呢？我不知道下一步该怎么走。有人能告诉我如何解码这个文件，因为我在搜索时找不到任何与它相关的东西。
回答 2
Stack Overflow用户
发布于 2015-04-11 22:49:38
您不需要创建代码或树来解码规范代码。您只需要按顺序列出符号列表和每个代码长度中的符号计数即可。所谓“按顺序”，我的意思是按代码长度从最短到最长排序，在每个代码长度内，按符号值排序。
由于代码长度内的规范代码是连续的二进制整数，您可以简单地进行整数比较，以查看您的比特是否在该代码范围内，如果是，则进行整数减法以确定它是哪个符号。
下面是来自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[]数组中的值，使其不会超额预订可在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'}。
#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 */
}Stack Overflow用户
发布于 2015-04-11 16:09:14
您的地图包含相关信息，但它将符号映射到代码。然而，您尝试解码的数据包含代码。因此，您的map不能用于获取与以有效方式读取的代码相对应的符号，因为查找方法需要一个符号。搜索代码并检索相应的符号将是线性搜索。
相反，您应该重建为压缩步骤构建的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
}
}请注意，反转映射以获得正确方向的查找仍然会导致性能不佳(与二叉树遍历相比)，因为它不能像遍历那样利用对较小搜索空间的限制。
https://stackoverflow.com/questions/29575309
复制相似问题
腾讯云开发者
