1

ハフマン貪欲アルゴリズムを使用してバイナリ ツリーを構築すると、4 つのアルファベットすべてが同じ確率である場合、次の結果が得られます。

  • 00
  • 01
  • 10
  • 11

問題は、私のプログラムが 00 と 01 を 0 と 1 しか認識しないことです。0 (ゼロ) から始まるコードの長さを 1 (1) に制限する必要がありますか? ハフマン コードまたはその個々のビットを格納するために使用するデータ型は何ですか?

4

1 に答える 1

1

「プログラムが 00 と 01 を 0 と 1 だけと見なす」場合、プログラムにバグがあります。

4 つの等確率シンボルの場合、コードは実際には 00、01、10、および 11 になります。つまり、デコード時にこれらのビットをすべて探す必要があります。デコードするときは、最初に左側のビットを引きます。つまり、コードが 00 または 01 のいずれかであることを意味します。次に、次のビットをプルします。これは 1 です。これで、完全なコード 01 が得られました。対応するシンボルを発行し、最初からやり直します。

確率が等しくなく、コードの長さが異なる、より典型的なケースを確認するのは簡単です。次のコードを検討してください。

a - 0
b - 10
c - 110
d - 111

デコードするには、ストリームからビットをプルし始めます。最初のビットは 1 です。これで、a、b、c、または d でなければならないことがわかりました。次に、別の 1 を引きます。c または d まで下げます。0 を引くと、d がわかります。次のビットから最初から開始します。

ビットを引っ張って選択肢を絞り込むまで、コードの長さはわかりません。コードをデコードすると、コードの長さがわかります。

于 2013-02-06T16:29:45.357 に答える