データ構造のt-aryツリーのハフマンアルゴリズム
単純なアルゴリズム
- n個の初期ハフマンツリーのコレクションが準備され、それぞれが単一の葉ノードです。 n本の木を重み（頻度）で整理された優先キューに保持します。
- 最初の2つのツリー（重みが最も小さいツリー）を削除または削除します。これらの2つのツリーを組み合わせて、ルートが子として2つのツリーに関連付けられ、重みが2つの子ツリーの重みの合計である新しいツリーを作成します。
- この新しいツリーを優先キューに入れておきます。
- すべての部分的なハフマンツリーが1つに結合されるまで、ステップ2〜3を繰り返します。
これは欲張りアルゴリズムです。各反復で、アルゴリズムは「欲張り」決定を作成して、重みが最小の2つのサブツリーをマージします。アルゴリズムが望ましい結果を出すことは可能ですか？
- 補題：xとyを最も頻度の低い2つの文字とします。 xとyが兄弟であり、ツリー内の他のリーフノードと同様に深さが最小である最適なコードツリーがあります。
- 定理：ハフマンコードは、プレフィックスのない最適なバイナリコードとして扱われます（欲張りアルゴリズムは、特定の文字セットに対して最小の外部パス重みでハフマンツリーを構築します）。
-
データ構造の範囲ツリー
範囲ツリーは、ポイントのリストを保持するための順序付けられたツリーデータ構造として定義されます。これにより、特定の範囲内のすべてのポイントを効率的に取得でき、通常は2次元以上で実装されます。 O（log d のクエリ時間が速いことを除いて、kdツリーと同じです。 n + k）が、O（n log d-1 のストレージが悪い n）、dはスペースの次元を示し、nはツリー内のポイントの数を示し、kは特定のクエリで取得されたポイントの数を示します。範囲ツリーは、間隔ツリーで区別できます。ポイントを格納して特定の範囲内のポイントを効率的に取得できるようにする代わりに、間隔ツリーは間隔を保存し、特定のポ
-
データ構造内の高さが制限されたハフマンツリー
高さ制限または深さ制限のハフマンツリーの図を以下に示します ツリーの深さの制限は、ほとんどの実際のハフマンの実装が対処しなければならない重要な問題です。 ハフマン構造は高さや深さを制限しません。もしそうなら、それが「最適」である可能性はありません。確かに、ハフマンツリーの最大の深さはフィボナッチ数列によって制限されますが、それは必要以上の深さのための十分な余地を残します。 ハフマンツリーの深さを制限する理由は何ですか？高速ハフマンデコーダーはルックアップテーブルを実装します。メモリコストを軽減するために複数のテーブルレベルを実装することは可能ですが、Huff0などの非常に高速なデコ