1

ハフマンツリーを構築しました。しかし、方法がわからないため、コードをビットに保存する方法がわかりません

可変長を処理します。

エンコードされた結果を出力するために、ハフマン コードをビット単位で格納するテーブルを作成したいと考えています。

bitset のような STL コンテナを使用できません。

私はそのようにしてみました

   void traverse( string code = "")const
   {
        if( frequency == 0 ) return;
        if ( left ) {
             left->traverse( code + '0' );
             right->traverse( code + '1' );
        }
        else {//leaf node
             huffmanTable[ch] = code;
        }
   }

それを処理するためのアルゴリズムを教えてもらえますか?

「0」は1ビット、「1」は1ビットを使用して保存したい。

事前にt​​hx。

4

3 に答える 3

2

バッファ、バッファのサイズをバイト単位で追跡するための変数、およびバッファ内の有効なビット数を追跡​​するための変数が必要です。

少し保存するには：

  1. ビットを追加すると格納されるバイト数が増えるかどうかを確認します。そうでない場合は、手順 4 に進みます。

  2. バッファに追加のバイトを格納する余地はありますか? その場合は、手順 4 に進みます。

  3. ストレージ バッファを数バイト大きく再割り当てします。既存のデータをコピーします。バッファーのサイズを保持する変数を増やします。

  4. 次のビットが格納されるバイト位置とビット位置を計算します。そのビットを適切に設定またはクリアします。

  5. 格納されたビット数を保持する変数をインクリメントします。

于 2012-12-11T00:02:41.500 に答える
1

基本的に、ツリーの最大キー長/深さに基づいて、ここでは2つの異なるアプローチのいずれかを使用します。

  • 固定長があり、使用可能な整数データ型（など）よりも短い場合はlong int、perrealで示されているアプローチを使用できます。

  • 最大深度がわからず、スペースが不足している可能性があると思われる場合はstd::vector<bool>、コード値として使用します。これは、値ごとに1ビットを使用するベクトルの特別な実装です（基本的にはDavidのアプローチ）。

于 2012-12-11T00:12:02.147 に答える
1

固定サイズの構造体を使用してテーブルを格納し、ビットだけを使用してエンコードされた入力を格納できます。

struct TableEntry {
  uint8_t size;
  uint8_t code;
};

TableEntry huffmanTable[256];

void traverse(uint8_t size; uint8_t code) const {
        if( frequency == 0 ) return;
        if ( left ) {
             left->traverse(size+1, code << 1 );
             right->traverse(size+1, (code << 1) | 1 );
        }
        else {//leaf node
             huffmanTable[ch].code = code;
             huffmanTable[ch].size = size;
        }
}

エンコードには、 Davidが投稿したアルゴリズムを使用できます。

于 2012-12-11T00:03:20.160 に答える