2

我正在使用 C 语言进行 Huffman 编码/解码项目，并且对算法应该如何存储有关 Huffman 树的信息、在解码期间重新构建树以及使用可变长度代码解压缩到原始输入文件有很好的理解.

当写入我的压缩文件时，我将输出一个包含唯一频率的 256 个 4 字节整数的表，我知道我还必须找出一种处理 EOF 的方法——稍后再担心。

我的问题是我应该如何完成必要的按位操作，将可变长度代码流写入 fwrite 的一系列 1 字节迭代。

如果我创建了以下（虚构的）代码：

a: 001010101010011
b: 100
c: 11111
d: 0

“abcd”的比特流是：

001010101010011100111110

我知道我需要使用一些按位操作将这个流“切”成可写字节：

00101010|10100111|00111110

根据代码长度创建 8 个不同案例的第一次尝试效果不佳，我被难住了。写入文件时是否有更简单的方法来处理可变长度代码？

谢谢

4

2 回答 2

1

这是一些伪代码，可以为您提供总体思路：

static byte BitBuffer = 0;
static byte BitsinBuffer = 0;

static void WriteBitCharToOutput(char bitChar);
// buffer one binary digit ('1' or '0')
{
  if (BitsInBuffer > 7)
  {
    stream.write(BitBuffer);
    BitsInBuffer = 0;
    BitBuffer = 0; // just to be tidy
  }

  BitBuffer = (BitBuffer << 1) | (bitChar == '1' ? 1 : 0);
  BitsInBuffer++;
}

static void FlushBitBuffer()
// call after last character has been encoded
// to flush out remaining bits
{
  if (BitsInBuffer > 0)
  do
  {
    WriteBitCharToOutput('0'); // pad with zeroes
  } while (BitsInBuffer != 1);
}
于 2015-02-18T00:31:34.160 回答
0

作为另一个答案的替代方案，如果您想一次将多个位写入缓冲区，您可以。它可能看起来像这样：（这是伪代码，虽然它看起来相当真实）

uint32_t buffer = 0;
int bufbits = 0;
for (int i = 0; i < symbolCount; i++)
{
    int s = symbols[i];
    buffer <<= lengths[s];  // make room for the bits
    bufbits += lengths[s];  // buffer got longer
    buffer |= values[s];    // put in the bits corresponding to the symbol

    while (bufbits >= 8)    // as long as there is at least a byte in the buffer
    {
        bufbits -= 8;       // forget it's there
        writeByte((buffer >> bufbits) & 0xFF); // and save it
    }
}

未显示：显然，当您完成写入缓冲区时，您必须保存缓冲区中剩余的任何内容。

这假设最大代码长度为 25 或更少。缓冲区中可以保留的最大位数是 7，7+25 是适合 32 位整数的最长位数。这不是一个不好的限制，通常代码长度限制为 15 或 16，以允许最简单的基于表的解码形式，而不需要巨大的表。

于 2015-02-18T07:49:32.740 回答