4

ハフマン アルゴリズムを使用してファイル コンプレッサーを開発していますが、現在次のような問題に直面しています。

アルゴリズムを word: stackoverflow に使用すると、次の結果が得られます。

a,c,e,f,k,l,r,s,t,v,w = 1 time repeated
o = 2 times repeated

a,c,e,f,k,l,r,s,t,v,w = 7.69231%
and
o = 15.3846%

そのため、バイナリ ツリーへの挿入を開始すると、結果が得られます。

o=00
a=010
e=0110
c=0111
t=1000
s=1001
w=1010
v=1011
k=1100
f=1101
r=1110
l=1111

これは、ツリー内の文字のパスを意味し、0 を左、1 を右と見なします。

次に、「stackoverflow」という単語は次のようになります。

そして、その値全体をビット単位でバイナリファイルに入れたいのですが、結果として47ビットになり、たまたま6バイトになりますが、代わりに、fwriteでファイルに入れる最小値があるため、47バイトにすることしかできませんまたは、sizeof(something) を使用して fprintf を 1 バイトにします。

私の質問は次のとおりです。ファイルに1ビットだけ印刷するにはどうすればよいですか?

4

3 に答える 3

5

ファイルに「ヘッダー」を書き込むだけです。ビット数を入力し、最後のビットをパディングするバイトにビットを「パック」します。これがサンプルです。

#include <stdio.h>

FILE* f;

/* how many bits in current byte */
int bit_counter;
/* current byte */
unsigned char cur_byte;

/* write 1 or 0 bit */
void write_bit(unsigned char bit)
{
    if(++bit_counter == 8)
    {
        fwrite(&cur_byte,1,1,f);
        bit_counter = 0;
        cur_byte = 0;
    }

    cur_byte <<= 1;
    cur_byte |= bit;
}

int main()
{
    f = fopen("test.bits", "w");

    cur_byte = 0;
    bit_counter = 0;

    /* write the number of bits here to decode the bitstream later (47 in your case) */
    /* int num = 47; */           
    /* fwrite(num, 1, 4, f); */

    write_bit(1);
    write_bit(0);
    write_bit(0);
    /* etc...  - do this in a loop for each encoded character */
    /* 100110000100111010011111000010110110111011011111001010 */

    if(bit_counter > 0)
    {
         // pad the last byte with zeroes
         cur_byte <<= 8 - bit_counter;
         fwrite(&cur_byte, 1, 1, f);
    }

    fclose(f);

    return 0;
}

もちろん、完全なハフマン エンコーダーを実行するには、最初にビット コードを記述する必要があります。

于 2012-06-28T21:41:10.163 に答える
2

これは一種のエンコーディングの問題です。問題は、ファイルにバイトしか含めることができないことです。つまり、1 と 0 はファイル内で「1」と「0」にしかなり得ません。1 と 0 の文字はバイトです。

あなたがしなければならないことは、ビットをバイトにパックし、バイトのセットにビットを含むファイルを作成することです. ファイルをテキスト エディターで開くことはできません。各ビットを 1 または 0 charとして表示するかどうかはわかりません。パックされた各バイトが何であれ表示されます。ただし、バイナリ ファイルの操作方法を理解しているエディターで開くことはできます。たとえば、vimはこれを行うことができます。

余分な末尾のバイトまたはファイルの終わりのマーカーに関する限り、何らかのエンコード規則を作成する必要があります。たとえば、コメントで述べたように、余分なゼロをパックしてパディングすることができますが、慣例により、最初の N バイトをメタデータ (データ長、ファイル内の興味深いビット数など) にします。この種のことは非常に一般的です。

于 2012-06-28T21:35:00.930 に答える
0

書き込むビットをバッファリングし、完全なバイトがある場合にのみ実際にデータを書き込むことにより、これを自分で管理する必要があります。何かのようなもの...

 void writeBit(bool b)
 {
   static char buffer=0;
   static int bitcount=0;

   buffer = (buffer << 1) | (b ? 1:0);

   if (++bitcount == 8)
   {
     fputc(buffer); // write out the byte
     bitcount = 0;
     buffer = 0;
   }
 }

上記は再入可能ではありません (そしてかなり非効率的である可能性があります) - 最後に半分書き込まれたバイトを何らかの方法でフラッシュする必要があります (余分な 7 ゼロビットを書き込むかもしれません) が、一般的な考え。

于 2012-06-28T21:37:43.317 に答える