ハフマン符号化ではどのようなデータ構造が使用されますか?

ハフマン符号化で使用されるデータ構造は「木構造」です。ハフマン アルゴリズムのサポートにより、最適な二分木が構築され、このタイプの木をハフマン ツリーと名付けます。したがって、正確には、ハフマン符号化は、ハフマン木に基づいて構築された符号化形式です。

このチュートリアルの動作環境: Windows 7 システム、Dell G3 コンピューター。

ハフマン符号化で使用されるデータ構造は「木構造」です。

ハフマン符号化 (ハフマン符号化とも呼ばれる) は、可変長符号化 (VLC) の一種である符号化方式です。ハフマンは 1952 年にコーディング方法を提案しました。この方法は完全に文字の出現確率に基づいて、さまざまなプレフィックスの平均長が最も短いコードワードを構築します。これは最良のエンコーディングと呼ばれることもあり、一般にハフマンコーディングと呼ばれることもあります（別名ハフマンコーディングとも呼ばれます）。ハフ符号化)、マン符号化)。

ハフマン コーディングでは、データ構造のツリー構造を使用して、ハフマン アルゴリズムのサポートにより最適なバイナリ ツリーを構築します。このタイプのツリーをハフマン ツリーと呼びます。したがって、ハフマン符号化は、正確に言えば、ハフマン木に基づいて構築された符号化形式であり、非常に幅広い応用範囲を持っています。

ハフマン ツリー

N 個の重みを N 個の葉ノードとして与えて、バイナリ ツリーを構築します。ツリーの重み付けされたパスの長さが最小値に達すると、そのようなバイナリ ツリーが作成されます。ツリーは最適バイナリ ツリーと呼ばれ、ハフマン ツリーとも呼ばれます。ハフマン ツリーは、重み付けされたパスの長さが最も短いツリーであり、より大きな重みを持つノードはルートに近くなります。

ツリーのいわゆる重み付きパスの長さは、ツリー内のすべての葉ノードの重みに、ルート ノードまでのパスの長さを乗算したものです (ルート ノードがレベル 0 の場合、その長さは、葉ノードから根ノードまでの経路（点の経路長は葉ノードの層数）。ツリーのパス長は、ツリーのルートから各ノードまでのパス長の合計であり、WPL= (W1*L1 W2*L2 W3*L3...Wn*Ln)、N 重み Wi (i=1) として記録されます。 、２、…ｎ）はＮ個の葉ノードを有する二分木を構成し、対応する葉ノードの経路長はＬｉ（ｉ＝１、２、…ｎ）である。ハフマン木の WPL が最小であることが証明できます。

さらに関連記事を読みたい場合は、PHP 中国語 Web サイト にアクセスしてください。 ！

以上がハフマン符号化ではどのようなデータ構造が使用されますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。