8

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

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

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

我怎样才能更好地处理这个问题？

4

2 回答 2

8

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

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

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

我教授一门入门编程课程，我们使用霍夫曼编码作为我们的任务之一。我们让学生使用上述方法，因为它比在文件内容之前写出位数或字节数要容易一些。有关更多详细信息，您可以查看此讲义或课程中的这些讲座幻灯片。

希望这可以帮助！

于 2013-02-02T23:39:41.493 回答
3

我知道这是一个老问题，但仍然有一个替代方案，所以它可能会对某人有所帮助。

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

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等于最后一个数据字节中的垃圾比特数。然后，您可以将其存储为最后一个额外的字节，并在解压缩时记住它。

于 2014-12-16T20:38:17.470 回答