algorithm - ハフマン アルゴリズムのバイナリ プレフィックス コード

Question

ハフマン コーディング アルゴリズムには、次の補題があります。

最適なバイナリ プレフィックス コードに対応するバイナリ ツリーがいっぱいです

しかし、理由がわかりません。この補題をどのように証明できますか?

Answer 1

Any binary code for data can be represented as a binary tree. The code is represented by the path from the root to the leaf, with a left edge representing a 0 in the prefix and a right one representing 1 (or vice versa.) Keep in mind that for each symbol there is one leaf node.

To prove that an optimal code will be represented by a full binary tree, let's recall what a full binary tree is, It is a tree where each node is either a leaf or has two chilren.

Let's assume that a certain code is optimal and is represented by a non-full tree. So there is a certain vertex u with only a single child v. The edge between u and v adds the bit x to the prefix code of the symbols (at the leaves) in the subtree rooted at v. From this tree I can remove the edge x and replace u with v, thus decreasing the length of the prefix code of all symbols in the subtree rooted at v by one. This reduces the number of bits in the representation of at least one symbol (when v is a singleton node.)

This shows that the tree didnt actually represent an optimal code, and my premise was wrong. Thus proving the lemma.

Answer 2

ウィキペディアから、

フル バイナリ ツリー (2 ツリーまたは厳密にバイナリ ツリーの場合もある) は、葉以外のすべてのノードが 2 つの子を持つツリーです。

ハフマン コードのツリーが生成される方法は、間違いなく完全なバイナリ ツリーを生成します。アルゴリズムの各ステップで、優先度が最も高い (確率が最も低い) 2 つのノードをキューから削除し、これらの 2 つのノードを子として持つ新しい内部ノードを作成するためです。