【データ構造】t-aryツリーのハフマンアルゴリズムとは?構築手順と最適性の根拠を徹底解説

シンプルな構築アルゴリズム

ハフマン木は、各文字の出現頻度(重み)に基づいて最適な符号木を構築するための手法です。基本的な構築手順は以下の通りです。

1. 初期化：n個の初期ハフマン木を用意します。それぞれの木は単一の葉ノードからなり、これらn個の木を、重み(出現頻度)順に管理できる優先度付きキュー(プライオリティキュー)に格納します。
2. 結合：キューから重みが最小の2つの木を取り出します。この2つの木を子として持つ新しい木を作成し、その根(ルート)の重みは2つの子の木の重みの合計とします。
3. 再登録：作成した新しい木を優先度付きキューに戻します。
4. 反復：手順2〜3を、すべての部分ハフマン木が1本の木に統合されるまで繰り返します。

これは貪欲法(グリーディアルゴリズム)である

ハフマンアルゴリズムは典型的な貪欲法です。各反復のたびに、重みが最小の2つの部分木をマージするという「その時点で最良と思われる」決定を下していきます。

では、このような局所的な判断の積み重ねが、本当に望ましい結果――すなわち全体として最適な符号木――をもたらすのでしょうか。実は、以下の補題と定理によってその正しさが理論的に保証されています。

最適性を支える補題と定理

• 補題：xとyを出現頻度が最も低い2つの文字とする。このとき、「xとyが兄弟ノードとなっており、かつ両者の位置が木内の他のどの葉ノードよりも深くない(=最も深い層にある)」ような最適コード木が必ず存在する。
• 定理：ハフマン符号は最適な接頭辞符号(プレフィックスフリーな2進符号)として扱える。言い換えると、貪欲法によって構築されたハフマン木は、与えられた文字集合に対して外部経路重み(external path weight)が最小の木となる。

補題により「最も頻度の低い2文字を最も深い位置に配置しても最適性は損なわれない」ことが示され、この性質を繰り返し適用することで、貪欲な結合手順が全体最適なハフマン木を導くことが定理として保証されます。

t分木(t-aryツリー)への拡張

上記の手順は2分木の場合の説明ですが、一般のt分木へも拡張可能です。t分木の場合は、1回の反復で重みが最小のt個の木を取り出して結合します。ただし、内部ノードの子の数が常にtとなるようにするため、必要に応じて出現頻度0のダミー文字を追加して調整する点に注意が必要です。