はじめに
ハフマン符号化方式では、データ圧縮のために二分木を構築する手法が用いられる。
この二分木の左右に振り分ける際のルールや自由度について疑問を抱く方も多いだろう。ここでは、左右の配置や符号化への影響について解説する。
左右の配置は自由である
ハフマン符号化では、左右のノード配置に厳密なルールは存在しない。
例えば、ノードAを左、ノードBを右に配置しても、その逆にしても問題はない。
これは、以下のような理由による。
- 符号長が影響を受けない
ハフマン符号化の目的は、出現頻度が高いデータに短い符号を割り当て、頻度が低いデータに長い符号を割り当てることである。この符号長は、ノードの結合順序と出現確率に依存し、左右の配置には依存しない。 -
符号の0/1割り当ても自由
二分木の枝に割り当てる「0」と「1」の値も、左右を入れ替えて構わない。
例えば、左枝を「0」、右枝を「1」とするルールを採用しても、その逆でも符号化の効果は同じだ。 -
復号時の一貫性が重要
符号化と復号で同じ二分木構造を使用すれば、左右の配置や0/1の割り当てが異なっていても問題は発生しない。
逆に言えば、符号化で使ったルールを復号で再現できなければ正確なデータ復元は不可能である。
二分木構築の基本手順
ハフマン符号化での二分木構築は、以下の手順に従う。
- 出現確率を昇順に並べる
各データとその出現確率を昇順に並べる。例えば、以下のようなデータがあったとする。
B: 56%
D: 20%
A: 12%
E: 8%
C: 4%
- 最小の確率値を持つデータをペアにする
例では、E(8%)とC(4%)をペアにし、新たなノードとして12%を作る。この操作を繰り返し、木を構築していく。 -
構築順序に左右のルールを適用
上記のペアリングでは、左右の配置に関するルールはないため、どのように配置しても構わない。例えば以下のどちらも有効だ。
- 左：E、右：C
- 左：C、右：E
まとめ
左右配置の自由度を考慮すると、ハフマン符号化で作成される二分木には多様な構築パターンが存在する。以下は具体例だ。
- 最初のペアリング
- 左：C、右：E
または
- 左：E、右：C
- 次の結合での自由度
- 新ノード(AEC)を左、Dを右
または
- Dを左、新ノード(AEC)を右
最終的にどのパターンで構築しても、符号長や圧縮効率に変化は生じない。
ただし、符号化と復号で同じ二分木構造を使用する必要がある点を忘れてはならない。
実務への応用
ハフマン符号化をプログラミングで実装する際、左右の配置を明確に定義しておくと、復号時の混乱を避けられる。
また、データ圧縮効率が変わらないことを理解しておくことで、自由度の高い設計が可能になる。
これを踏まえて、あなたならどのようなルールを採用するだろうか？ぜひ自身のプログラム設計に適用してみてほしい。
コメント