イベントが発生する確率を示す表があります。パート 1 は問題ありませんが、パート 2 は気に入りません。パート 2 で 2 進数がどのように導出されるかについて頭を悩ませようとしていますか?
0 が最大の確率に割り当てられていることは理解していますが、そこから作業を進めますが、次の 2 進数のセットをどのように計算するのでしょうか? 数字の周りの円は何を意味しますか? 2 つのグレーの色合いは区別されますか?
クリックしていないだけです。たぶん、誰かが私を理解できるように説明してくれるでしょうか？
ハフマン コードを作成する方法の 1 つは、優先度キューを使用してバイナリ ツリーを作成することです。このキューには、コードが割り当てられるデータが挿入され、頻度によって並べ替えられます。
まず、各データを表すリーフ ノードのみを持つキューがあります。
各ステップで、優先度の最も低い 2 つのノードをキューから取得し、削除された 2 つのノードの合計に等しい頻度で新しいノードを作成し、それらの 2 つのノードを左右の子としてアタッチします。この新しいノードは、その頻度に従って、キューに再挿入されます。
ルートになるノードがキューに 1 つだけになるまで、これを繰り返します。
これで、ルートから任意のリーフ ノードまでツリーをたどることができ、各レベルでたどるパス (左または右に行くかどうか) から 0 または 1 のいずれかが得られ、パスの長さ (どのくらい下に移動するか) が得られます。ツリーはノードです) コードの長さを示します。
実際には、ツリーを構築するときにこのコードを構築できますが、各ノードのコードに 0 または 1 を追加します。これは、それが含まれるサブツリーが新しい親の左または右に追加されているかどうかに応じて異なります。 .
あなたの図では、円の中の数字は、ツリーを構築する各段階で結合された 2 つのノードの頻度の合計を示しています。
また、結合されている 2 つに異なるビットが割り当てられていることも確認できます (一方は 0、もう一方は 1)。
図が役立つ場合があります。手書きのお詫び：
