ハフマン符号化の基礎と実装方法

ハフマン符号化とは

ハフマン符号化は、データ圧縮アルゴリズムの一種で、頻繁に使われるデータに対して短いビット列を、あまり使われないデータには長いビット列を割り当てる手法です。

これにより、全体のデータ量を減らすことができます。

このように、可変長符号を使用することで、データの効率的な圧縮が可能になります。

ハフマン符号化は、無駄のない最適な符号を生成できるため、さまざまな分野で使われています。
たとえば、ファイル圧縮ソフトウェアやネットワークでのデータ伝送に利用されています。

ハフマン木の構築

ハフマン符号化の基礎にはハフマン木と呼ばれる特別な木構造があります。

この木構造を用いることで、文字やデータの頻度に基づいて最適な符号を決定します。

ハフマン木の基本概念

• 葉ノード：データのシンボル（例: 文字や数字）を持つノード。
• 内部ノード：他のノードを接続するノードで、シンボルは持たない。

具体的なハフマン木の作り方

1. 頻度の確認
   最初に、すべてのシンボルの出現頻度を確認します。
   たとえば、テキストファイル内の各文字の出現回数を数えます。
2. 最小頻度の選択
   シンボルの出現頻度が最も低い2つを選び、それらを新しい内部ノードに結びつけます。
   この新しい内部ノードの頻度は、選んだ2つのノードの頻度の合計になります。
3. 新しいノードの生成
   この過程を繰り返し、最終的にすべてのノードが1つのハフマン木にまとめられます。
   木の構造が完成するまで、このプロセスを続けます。
4. 木構造の再構築
   各内部ノードが生成されるたびに、ツリー全体の構造が再計算され、効率的な木が作られます。

コードの割り当て方

ハフマン木が完成したら、葉ノードに対して0または1のビットを割り当てます。

木の左側の枝には0、右側の枝には1を割り当て、各シンボルに対してユニークなビット列を生成します。

これにより、頻度が高いシンボルには短いビット列、頻度が低いシンボルには長いビット列が割り当てられます。

木構造によるハフマン符号化の作り方

ここでは、具体的な例を使ってハフマン符号化の手順を説明します。

頻度テーブルの生成

まず、以下のようなシンボルとその出現頻度が与えられたとしましょう：

優先度付きキューを使った木の構築

ハフマン符号化では、頻度に基づいて効率的な木を作成するために、優先度付きキューを使用します。

優先度付きキューは、常に最も頻度の低い2つの要素を取り出すことができるデータ構造です。

以下は、優先度付きキューを使って木を構築する手順です。

1. 各シンボルを優先度付きキューに追加します（優先度はシンボルの頻度）。
2. 頻度が最も低い2つのシンボルを取り出し、新しい内部ノードを生成します。
3. この内部ノードの頻度は、取り出した2つのシンボルの頻度の合計です。
4. 新しい内部ノードを優先度付きキューに追加します。
5. このプロセスを繰り返し、1つのハフマン木が完成するまで続けます。

木の構築の具体例

先ほどの頻度テーブルを用いて、木を構築する手順を説明します。

ステップ1: 各シンボルを優先度付きキューに追加

最初に、シンボルとその頻度を持つノードを優先度付きキューに追加します。

• キューの初期状態：
  • A: 5
  • B: 9
  • C: 12
  • D: 13
  • E: 16
  • F: 45

ステップ2: 最小頻度のノード2つを取り出し、新しい内部ノードを作成

次に、最小頻度の2つのノード（A: 5 と B: 9）を取り出し、新しい内部ノードを作成します。

この内部ノードの頻度は、2つのノードの頻度の合計（5 + 9 = 14）です。

新しい内部ノード（頻度14）は、元のノードAとBを子として持つことになります。

• 新しいキューの状態：
  • 内部ノード: 14 (A: 5, B: 9)
  • C: 12
  • D: 13
  • E: 16
  • F: 45

ステップ3: 優先度付きキューに戻し、再び2つの最小ノードを選択

内部ノードを優先度付きキューに戻し、次に最も頻度の低い2つのノード（C: 12 と D: 13）を選びます。

これらから新しい内部ノード（頻度25）を作成します。

• 新しいキューの状態：
  • 内部ノード: 14 (A: 5, B: 9)
  • 内部ノード: 25 (C: 12, D: 13)
  • E: 16
  • F: 45

ステップ4: 次の最小ノードを選択

さらに、次に最も小さい2つのノード（14 と 16）を選び、新しい内部ノード（頻度30）を作成します。

• 新しいキューの状態：
  • 内部ノード: 25 (C: 12, D: 13)
  • 内部ノード: 30 (14, E: 16)
  • F: 45

ステップ5: 最後の内部ノードを作成

次に、最小頻度の2つのノード（25 と 30）を選び、最終的な内部ノード（頻度55）を作成します。

このノードがハフマン木の根となります。

• 新しいキューの状態：
  • 内部ノード: 55 (25, 30)
  • F: 45

最後に、55と45を統合し、最終的な木を完成させます。

• 完成したハフマン木：
  • 根ノード（頻度100）は、内部ノード55とシンボルF: 45を持つ。

ハフマン木の完成

完成したハフマン木は以下のような形になります：

        [100]
       /    \
    [55]    F(45)
   /    \
[25]    [30]
 / \     /  \
C  D   A   E
(12)(13)(5)(16)

各シンボルにビット列が割り当てられます。

ノードへの符号の割り当て

最後に、ハフマン木を使って各シンボルにビット列を割り当てます。

たとえば、Fは木の右側にあるので、0という短いビット列が割り当てられ、頻度の低いAには長いビット列が割り当てられます。

シンボルの割り当てが完了すると、以下のような符号が得られます：

このように、優先度付きキューを使って頻度に基づいてハフマン木を構築し、効率的な符号を生成できます。

平均ビット長の算出

ハフマン符号化のもう一つの重要なステップは、平均ビット長を計算することです。

これは、圧縮効率を評価するために役立ちます。

平均ビット長の定義

平均ビット長は、各シンボルに割り当てられたビット長と、そのシンボルの出現頻度の積の合計を、全体のシンボル頻度で割った値です。

ビット長の計算方法

以下の式で計算できます：

$$
\text{平均ビット長} = \frac{\sum (\text{シンボルの頻度} \times \text{符号の長さ})}{\text{総出現頻度}}
$$

具体的な例と計算手順

上記のシンボルと符号を使用して、平均ビット長を計算してみましょう。

$$
(5 \times 4) + (9 \times 4) + (12 \times 3) + (13 \times 3) + (16 \times 3) + (45 \times 1) = 20 + 36 + 36 + 39 + 48 + 45 = 224
$$

全体の出現頻度は 100 なので、平均ビット長は：

$$
\frac{224}{100} = 2.24 \text{ビット}
$$

ハフマン符号化の実用性

ハフマン符号化は、多くの分野で利用されています。

代表的な例として、以下のものがあります：

• ファイル圧縮：ZIPやRARといったファイル圧縮形式で使われています。
• ネットワーク伝送：データ量を削減するために、通信プロトコルでハフマン符号化が使用されます。

メリット

• 圧縮効率が高い：データに応じて最適な符号が作られるため、無駄がありません。

デメリット

• リアルタイム性には不向き：シンボルの頻度を事前に知る必要があるため、リアルタイムでの圧縮には適していません。

まとめ

ハフマン符号化は、データの出現頻度に基づいて効率的に符号を割り当てる優れた圧縮アルゴリズムです。

特に、ファイル圧縮やネットワーク通信など、データ量を削減するための技術として広く利用されています。

平均ビット長の算出も含め、具体的な手順を理解することで、ハフマン符号化を実際に実装し、活用することができます。

この記事が、ハフマン符号化についての理解を深める一助となれば幸いです。