2

ハフマン符号をファイルに保存したい。これどうやってするの？ハフマン コードを文字列に保存していますが、生成されたファイルのサイズが元のファイルよりも大きくなります。

4

3 に答える 3

4

非常に簡単な方法は、次のように一度に 1 ビットずつ書き込むことです。

unsigned char acc; // Accumulator of bit waiting to be written
int bitcount;      // How many bits are aready present in the accumulator

// write a single bit (0/1)
void writebit(int bit)
{
    acc |= (bit << bitcount);
    if (++bitcount == 8)
    {
        writebyte(acc);
        acc = 0;
        bitcount = 0;
    }
}

少しだけ読み返す手順は対称的です

unsigned char acc;   // bits waiting to be extracted
int bitcount;        // how many bits are still available in acc

int readbit()
{
   if (bitcount == 0)
   {
       bitcount = 8;
       acc = readbyte();
   }
   --bitcount;
   return (acc >> (7 - bitcount)) & 1;
}

もちろん、これは最も単純な方法ですが、エンコードされたデータを正しく保存してロードできるようになるまで、コードの速度について心配することはありません。

例：

次のハフマン符号化された記号があるとします。

A - 0
B - 10
C - 110
D - 111

そして、シーケンスをエンコードしたい

A B A A C D A D B B

次に、順番に呼び出します

writebit(0);                           // A
writebit(1); writebit(0);              // B
writebit(0);                           // A
writebit(0);                           // A
writebit(1); writebit(1); writebit(0); // C
writebit(1); writebit(1); writebit(1); // D
writebit(0);                           // A
writebit(1); writebit(0);              // B
writebit(1); writebit(0);              // B

したがって、書き込まれる実際のバイト数は次のようになります。

(01100010) = 0x62
(01010111) = 0x57

(表示されているコードは最下位ビットから始まることに注意してください。つまり、記号を認識したい場合は、括弧内のビット シーケンスを右から左に読む必要があります)。

于 2011-07-07T19:44:32.503 に答える
1

あなたが保存しているのは 1 と 0 の文字列だと思います。真のハフマン コードは、バイナリで保存し、後で解析する必要があります。出力を単に文字列として保存するだけでは、ハフマン コードの目的が無効になります。各 0 と 1 は 1 ではなく 8 ビットです。

于 2011-07-07T19:21:30.183 に答える
1

おそらく、各パターン/文字のバイト全体を保存しています。

e が最も一般的な文字であるとしましょう。ビットパターンは 0 になります。

z が最も一般的でない文字で、1 で始まるパターンがあるとしましょう。1111 111 に割り当てましょう。

書き込みたいファイルは次のようになります。

0111 1111

あなたはおそらくこれを書いています：

0000 0000 0111 1111.

これを行うには、ビット演算を利用する必要があります。

于 2011-07-07T19:24:00.757 に答える