0

TL;DR：使用霍夫曼代码压缩纯文本实际上是如何工作的？

我目前正在学习霍夫曼编码算法及其在文本文件压缩中的应用。我知道我们可以通过使用由文本文件中每个字符的频率分布确定的编码技术（例如霍夫曼编码）来以更小的大小存储相同的数据。

在霍夫曼编码中，我们希望文本文件中最常见的字符获得最短的二进制表示（可变长度编码），因此文件所需的总存储量少于固定长度编码（如 ASCII）的存储量。

但是我仍然不知道如何实际实现压缩。我应该使用哪种文件来存储文本文件的 Huffman 编码二进制表示？将纯文本（可能是 .txt 格式）压缩成压缩文件的过程实际上是如何工作的？解压缩是否也与压缩相同，只是方向相反？

我尝试在 C 中使用二进制文件来存储 .txt 文件的二进制表示。正如您所料，二进制文件实际上变得比原始文件大。

我读过将纯文本文件转换为压缩文件只是用适当的位字符串替换每个字母，然后处理需要写入一些额外位的可能性。但是，对于什么是位字符串以及如何使用它，我仍然没有找到任何好的参考。

任何参考都会有所帮助，任何 C 实现的答案都是完美的。谢谢你。

4

1 回答 1

1

只有一种文件。一个字节序列。每个字节有八位。对于霍夫曼编码，您认为文件是一系列位而不是字节。您将这些位累积在缓冲区中，当您有字节时，您将它们写到文件中。就像是：

// Write the low bits of code to stdout. The remaining bits of code must be zero.
void put_bits(int bits, unsigned code) {
    static int have = 0;
    static unsigned buf = 0;
    if (bits == -1) {
        // flush remaining bits
        if (have) {
            putchar(buf);
            have = 0;
            buf = 0;
        }
        return;
    }
    buf |= code << have;
    have += bits;
    while (have >= 8) {
        putchar(buf);
        buf >>= 8;
        have -= 8;
    }
}
于 2020-12-01T21:29:59.563 回答