HOFFMANアルゴリズムの証明がどのように最適なツリーTで始まりますか？

Question

この論文請求項1は、 x および y が最小の確率であり、は最適なコードツリーがあり、この2つの文字が最大深度で兄弟姉妹であることを特徴とする。。その主張の証明では、著者は、最大ツリーの深さで B と C を有するツリー t で始まります。 x と y が最小の確率が最も小さいため、ツリー t が最適と呼ばれるのは理解できません。アルゴリズムはそのようなツリーを構築しません。私の問題はここでの最適なツリーを意味するのを理解していると思います。

誰かがCSLRから来た場合、これはLEMMA 16.2についてのものであり、そのための証明です。

Answer 1

平均符号語の長さが最小の場合、コードツリーは最適です。これはハフマンのアルゴリズムとは関係ありません。 Huffmanのアルゴリズムは最適なコードツリーを生成することが保証されていますが、他のコードツリーがあるかもしれません。実際、ハフマンのアルゴリズムは、異なるタイ破断規則を使用して異なるコードツリーを作成することができます。さらに、任意のタイブレイプレークルールでさえも、ハフマンのアルゴリズムを使用してすべての最適なコードツリーを製造することができない。

これは最適なコードツリーの正式な定義です。 $ \ pi $ を配布にする。 $ \ pi $ -cost はコードワードの予想される長さです。 class="math-container"> $ \ pi $ 。 の $ \π$ です。 > -costは、任意のコードツリーの最小 $ \ pi $ に等しい。