2

私は C でハフマン コーディング/デコード プロジェクトに取り組んでおり、アルゴリズムがハフマン ツリーに関する情報を格納し、デコード中にツリーを再構築し、可変長コードを使用して元の入力ファイルに解凍する方法をよく理解しています。 .

圧縮ファイルに書き込むとき、一意の頻度を含む 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 に答える