Huffman压缩中的最后一个字节

Question

我想知道处理Huffman压缩中的最后一个字节的最佳方法。我有一些很好的C++代码，可以很好地压缩文本文件，但是目前我必须在我的编码文件中写入编码字符的数量（等于输入文件大小），因为不知道如何更好地处理最后一个字节。

例如，要压缩的最后一个字符是'a'，其编码为011，我刚刚开始写新字节，因此最后一个字节看起来像： 011 + 一些5位垃圾，我将它们设置为零，例如在末尾。 当我对这个编码文件进行编码时，可能会发生代码00000（或更少的零）是某个字符的代码，因此我将在我的编码文件末尾有一些垃圾字符。

正如我在第一段中所写的那样，我通过在编码文件中保存输入文件的字符数来避免这种情况，并且在编码时，我读取编码文件以达到该数字（而不是到达EndOfFile，以避免那些5个零的例子）。 这并不是真正有效的，编码文件的大小增加了很多。

有什么更好的方法来处理这个问题吗？

- Horuss

Answer 1

你的方法（将编码字节数写入文件）是一种完全合理的方法。如果你想尝试其他方法，可以考虑发明一个新的“伪EOF”字符来标记输入的结尾（我将其表示为□）。每当你想要压缩一个字符串 s 时，你需要压缩的是字符串 s□。这意味着在构建编码树时，你需要包括一个 □ 字符的副本，以便你拥有一个唯一的编码方式。然后，当你将字符串写入文件时，你需要如常地写出字符串的位字符，然后写出 □ 的位模式。如果还有剩余的位数，你可以随意设置它们。

这种方法的优点是，在解码文件时，如果你发现了 □ 字符，你可以立即停止解码位，因为你知道已经达到了文件的结尾。这不需要你在任何地方存储已写出的字节数 - 编码隐含地标记了它自己的终点。

这种设置的缺点是它可能会增加某些字符使用的位模式的长度，因为你除了所有其他字符之外还需要分配一个位模式给 □。

我教授一门介绍性编程课程，我们将赫夫曼编码作为任务之一。我们让学生使用上述方法，因为它比在文件内容之前写出位或字节数要简单些。更多详细信息，你可以查看本课程的这个手册或这些讲义幻灯片。

希望这有所帮助！

- templatetypedef

---

实际上没有什么缺点，因为你可以证明这不会比编码长度需要更多的位数。 - Mark Adler

@MarkAdler- 你有关于这个的参考文献吗？我经常想知道这个问题，但我从未见过正式的证明。 - templatetypedef

@Kuba- 你不应该为了伪EOF而牺牲一个字符。相反，你可以选择一个非char值（比如INT_MAX），并假装它是一个字符，因为这个值不可能出现在任何字符串中。我认为最简单的方法是在类型为“int”的值上进行所有编码，而不是在类型为“char”的值上进行编码，因为你总是可以将“char”编码为“int”，然后还可以将伪EOF等额外值作为“int”进行编码。这样有意义吗？ - templatetypedef

我现在明白了，谢谢。在空闲时间里，我会尝试改进我的程序并看看它的运行情况。 - Horuss

@MarkAdler，我仍然对所提到的证明很感兴趣。 - Silicomancer

Answer 2

我知道这是一个老问题，但是还是有一种替代方案，它可能会帮助到某些人。

当你将压缩文件写入输出时，你可能有一些整数来跟踪当前字节中的位置（用于位移）。

char c, p;
p = '\0';
int curr = 7;
while (infile.get(c))
{
    std::string trav = GetTraversal(c);
    for (int i = 0; i < trav.size(); i++)
    {
        if (trav[i] == '1')
            p += (1 << curr);
        if (--curr < 0)
        {
            outfile.put(p);
            p = '\0';
            curr = 7;
        }
    }
}
if (curr < 7)
    outfile.put(p);

在这个代码块的末尾，(curr+1)%8等于最后一个数据字节中垃圾位的数量。您可以将其作为单独的额外字节存储在末尾，并在进行解压缩时牢记它。

- Regan Carver