可变长度霍夫曼代码的比特流-如何写入文件? [英] Bitstream of variable-length Huffman codes - How to write to file?

问题描述

我正在使用C进行霍夫曼编码/解码项目，并且对算法应如何存储有关霍夫曼树的信息，在解码期间重新构建树以及使用变量解压缩为原始输入文件有很好的了解.长度的代码.

I'm working on a Huffman coding/decoding project in C and have a good understanding of how the algorithm should store information about the Huffman tree, re-build the tree during decoding, and decompress to the original input file using variable-length codes.

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

When writing to my compressed file, I will output a table of 256 4-byte integers containing unique frequencies, and I know I will also have to figure out a way to handle EOF - worrying about that later.

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

My question is how should I complete the necessary bit-wise operations to write a stream of variable-length codes to a series of 1-byte iterations of fwrite.

如果我创建了以下(虚拟)代码:

If I've created the following (fictitious) codes:

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

"abcd"的位流为:

The bitstream for "abcd" would be:

001010101010011100111110

我知道我需要使用一些按位操作才能将该流切"成可写字节:

I know I'll need to use some bit-wise operations to "chop" this stream up into writeable bytes:

00101010|10100111|00111110

基于代码长度创建8个不同案例的第一次尝试效果不佳，我很沮丧.写入文件时，有没有更简单的方法来处理可变长度代码?

A first attempt at creating 8 different cases based upon lengths of the codes did not work out well and I'm stumped. Is there an easier way to handle variable-length codes when writing to a file?

谢谢

推荐答案

以下是一些伪代码，可以使您大致了解:

Here's some pseudo-code to give you the general idea:

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);
}

这篇关于可变长度霍夫曼代码的比特流-如何写入文件?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！