ハフマン符号化

コンピュータサイエンスと情報理論において、ハフマン符号は、ロスレスデータ圧縮によく使用される特定の種類の最適なプレフィックス符号です。このような符号を見つけたり使用したりするプロセスがハフマン符号化であり、これは、 MITの理学博士課程の学生だったデビッド・A・ハフマンが開発したアルゴリズムで、1952年の論文「最小冗長性符号の構築方法」で発表されました。^[1]

ハフマンアルゴリズムの出力は、ソースシンボル（ファイル内の文字など）をエンコードするための可変長コードテーブルとして見ることができます。アルゴリズムは、ソースシンボルの可能な値ごとに推定される発生確率または発生頻度（重み）からこのテーブルを導き出します。他のエントロピーエンコード方式と同様に、より一般的なシンボルは、より一般的でないシンボルよりも少ないビットを使用して表されるのが一般的です。ハフマンの方法は、入力重みがソートされている場合、入力重みの数に線形の時間でコードを見つけることで、効率的に実装できます。 ^{[2]ただし、シンボルを個別にエンコードする方法の中では最適ですが、ハフマン符号化はすべての圧縮方法の中で常に最適であるとは限りません。より良い圧縮率が必要な場合は、}算術符号化^[3]または非対称数値システム^[4] に置き換えられます。

1951年、デビッド・A・ハフマンとMITの 情報理論のクラスメートは、学期末レポートか期末試験のどちらかを選択するよう求められた。ロバート・M・ファノ教授は、最も効率的なバイナリコードを見つける問題についての学期末レポートを課した。ハフマンは、どのコードが最も効率的であるかを証明できず、あきらめて期末試験の勉強を始めようとしていたところ、頻度ソートバイナリツリーを使用するというアイデアを思いつき、すぐにこの方法が最も効率的であることを証明した。^[5]

そうすることで、ハフマンは、クロード・シャノンと協力して同様のコードを開発したファノを上回りました。シャノン・ファノ符号化のトップダウンアプローチとは異なり、下から上へ木を構築することで最適性が保証されました。

ハフマン符号化では、各シンボルの表現を選択するための特定の方法を使用し、プレフィックス コード(「プレフィックスフリー コード」と呼ばれることもあります。つまり、特定のシンボルを表すビット文字列は、他のシンボルを表すビット文字列のプレフィックスにはなりません) が生成されます。ハフマン符号化はプレフィックス コードを作成するための非常に一般的な方法であるため、「ハフマン コード」という用語は、ハフマンのアルゴリズムによって生成されたコードではない場合でも、「プレフィックス コード」の同義語として広く使用されています。

与えられた

シンボルとその重みのセット（通常は確率に比例します）。

探す

最小の予想されるコードワード長を持つプレフィックスフリーのバイナリ コード(コードワードのセット) (ルートからの重み付きパス長が最小のツリーと同等)。

入力。
アルファベットは、サイズ のシンボル アルファベットです。 タプルは、(正の) シンボル重み (通常は確率に比例) のタプルです。つまり。出力。 コード は、(バイナリ) コードワード のタプルです。ここで はのコードワードです。目標。コード の重み付きパス長を と します。条件:任意のコード に対して です。 ${\displaystyle A=(a_{1},a_{2},\dots ,a_{n})}$${\displaystyle n}$
${\displaystyle W=(w_{1},w_{2},\dots ,w_{n})}$${\displaystyle w_{i}=\operatorname {重み} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}}$


${\displaystyle C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})}$${\displaystyle c_{i}}$${\displaystyle a_{i},\,i\in \{1,2,\dots ,n\}}$


${\textstyle L\left(C\left(W\right)\right)=\sum _{i=1}^{n}{w_{i}\operatorname {length} \left(c_{i}\right)}}$${\displaystyle C}$${\displaystyle L\left(C\left(W\right)\right)\leq L\left(T\left(W\right)\right)}$${\displaystyle T\left(W\right)}$

5 つの文字と与えられた重みを持つコードに対するハフマン コーディングの結果の例を示します。すべてのコードでL が最小化されるかどうかは検証しませんが、 L を計算して、与えられた重みセットのシャノン エントロピー Hと比較します。結果はほぼ最適です。

バイユニークであるコード、つまり一意にデコード可能なコードの場合、すべてのシンボルの確率予算の合計は常に 1 以下になります。この例では、合計は厳密に 1 に等しいため、コードは完全なコードと呼ばれます。そうでない場合は、追加のシンボル (関連するヌル確率を含む) を追加することで同等のコードを常に導出し、バイユニークを維持しながらコードを完全にすることができます。

シャノン（1948）の定義によれば、各シンボルa _iの情報量h（ビット）は、非ゼロ確率で

${\displaystyle h(a_{i})=\log _{2}{1 \over w_{i}}.}$

エントロピーH (ビット単位) は、すべてのシンボル a i にわたって、各 シンボル_の情報量を 非ゼロの確率w _{iで加重合計したものです。}

$${\displaystyle H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}{w_{i}}.}$$

(注: 確率がゼロのシンボルは、エントロピーへの寄与がゼロです。したがって、簡単にするために、確率がゼロのシンボルは上記の式から除外できます。) ${\displaystyle \lim _{w\to 0^{+}}w\log _{2}w=0}$

シャノンの情報源符号化定理の結果として、エントロピーは、特定のアルファベットと関連する重みに対して理論的に可能な最小のコードワード長の尺度です。この例では、加重平均コードワード長は 1 シンボルあたり 2.25 ビットで、計算されたエントロピーの 1 シンボルあたり 2.205 ビットよりわずかに大きいだけです。したがって、このコードは、他の実行可能なコードよりもパフォーマンスが良いという意味で最適であるだけでなく、シャノンによって確立された理論的限界に非常に近いです。

一般に、ハフマン コードは一意である必要はありません。したがって、特定の確率分布のハフマン コード セットは、その確率分布を最小化するコードの空でないサブセットです。(ただし、最小化するコードワード長の割り当てごとに、それらの長さのハフマン コードが少なくとも 1 つ存在します。) ${\displaystyle L(C)}$

この手法では、ノードのバイナリ ツリーを作成します。これらは通常の配列に格納でき、配列のサイズはシンボルの数 によって異なります。ノードは、リーフ ノードまたは内部ノードのいずれかになります。最初は、すべてのノードがリーフ ノードで、シンボル自体、シンボルの重み (出現頻度)、およびオプションで親ノードへのリンクが含まれます。これにより、リーフ ノードからコードを (逆に) 読みやすくなります。内部ノードには、重み 、2 つの子ノードへのリンク、およびオプションで親ノードへのリンクが含まれます。一般的な規則として、ビット '0' は左の子に続くことを表し、ビット '1' は右の子に続くことを表します。完成したツリーには、最大 個のリーフ ノードと内部ノードが含まれます。未使用のシンボルを省略するハフマン ツリーは、最適なコード長を生成します。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle n-1}$

このプロセスは、表すシンボルの確率を含むリーフ ノードから始まります。次に、確率が最も小さい 2 つのノードを取得し、これらの 2 つのノードを子として持つ新しい内部ノードを作成します。新しいノードの重みは、子の重みの合計に設定されます。次に、新しい内部ノードと残りのノード (つまり、2 つのリーフ ノードを除外) にこのプロセスを再度適用し、ハフマン ツリーのルートである 1 つのノードだけが残るまでこのプロセスを繰り返します。

最も単純な構築アルゴリズムでは、最も確率の低いノードに最高の優先順位が与えられる 優先キューを使用します。

1. 各シンボルのリーフ ノードを作成し、優先キューに追加します。
2. キュー内に複数のノードがある場合:
   1. 最も優先度の高い（確率が最も低い）2つのノードをキューから削除する
   2. これらの 2 つのノードを子として、2 つのノードの確率の合計に等しい確率で新しい内部ノードを作成します。
   3. 新しいノードをキューに追加します。
3. 残ったノードはルートノードとなり、ツリーは完成します。

効率的な優先キューデータ構造では挿入ごとにO(log n )の時間が必要であり、n個の葉を持つツリーには2 n −1個のノードがあるため、このアルゴリズムはO( n log n )時間で動作します（nはシンボルの数）。

シンボルが確率によってソートされている場合、2 つのキューを使用してハフマン ツリーを作成する線形時間 (O(n)) の方法があります。最初のキューには初期重み (および関連するリーフへのポインタ) が含まれ、結合された重み (およびツリーへのポインタ) は 2 番目のキューの後ろに配置されます。これにより、最も低い重みが常に 2 つのキューのいずれかの先頭に保持されます。

1. シンボルの数と同じ数の葉から始めます。
2. すべてのリーフ ノードを最初のキューにエンキューします (最も可能性の低い項目がキューの先頭になるように、確率の昇順でエンキューします)。
3. キューに複数のノードがある場合:
   1. 両方のキューの先頭を調べて、重みが最も低い 2 つのノードをキューから削除します。
   2. 削除したばかりの 2 つのノードを子として (どちらのノードも子になることができます)、それらの重みの合計を新しい重みとして、新しい内部ノードを作成します。
   3. 新しいノードを 2 番目のキューの後ろにエンキューします。
4. 残ったノードはルートノードです。これでツリーが生成されました。

ハフマン ツリーが生成されると、次のようにシンボルをバイナリ コードにマッピングする辞書が生成されます。

1. 現在のノードをルートに設定して開始します。
2. ノードがリーフ ノードでない場合は、左の子へのエッジに0のラベルを付け、右の子へのエッジに1 のラベルを付けます。このプロセスを左の子と右の子の両方で繰り返します。

任意のシンボルの最終的なエンコーディングは、ルート ノードからシンボルまでのパスに沿ったエッジ上のラベルの連結によって読み取られます。

多くの場合、ここでのアルゴリズムの選択において時間の複雑さはそれほど重要ではありません。ここでのnはアルファベットの記号の数であり、これは通常非常に小さい数です (エンコードされるメッセージの長さと比較して)。一方、複雑さの分析は、 n が非常に大きくなった場合の動作に関係します。

一般的に、コードワード長の分散を最小限に抑えることは有益です。たとえば、ツリーが特に不均衡な場合、ハフマン符号化データを受信する通信バッファは、特に長いシンボルを処理するために、より大きくする必要があります。分散を最小限に抑えるには、最初のキューの項目を選択して、キュー間の同点を解消するだけです。この変更により、分散を最小限に抑え、最長の文字コードの長さを最小限に抑えながら、ハフマン符号化の数学的最適性を維持できます。

一般的に言えば、解凍のプロセスは、プレフィックス コードのストリームを個々のバイト値に変換するだけの単純な処理です。通常は、入力ストリームから各ビットが読み取られるたびに、ハフマン ツリーをノードごとにトラバースします (リーフ ノードに到達すると、その特定のバイト値の検索は必ず終了します)。ただし、これを行う前に、ハフマン ツリーを何らかの方法で再構築する必要があります。文字の頻度がかなり予測可能な最も単純なケースでは、ツリーを事前に構築し (圧縮サイクルごとに統計的に調整することもできます)、毎回再利用できます。ただし、圧縮効率が少なくともある程度低下します。それ以外の場合は、ツリーを再構築するための情報を事前に送信する必要があります。単純な方法としては、各文字の頻度カウントを圧縮ストリームの先頭に追加する方法があります。残念ながら、このような場合のオーバーヘッドは数キロバイトに達する可能性があるため、この方法は実用的ではありません。データが標準エンコーディングを使用して圧縮されている場合、圧縮モデルは情報ビット ( Bはシンボルあたりのビット数)だけで正確に再構築できます。もう 1 つの方法は、出力ストリームの先頭にハフマン ツリーを 1 ビットずつ追加する方法です。たとえば、0 の値が親ノードを表し、1 がリーフ ノードを表すと仮定すると、後者に遭遇するたびに、ツリー構築ルーチンは次の 8 ビットを読み取って、その特定のリーフの文字値を決定します。このプロセスは、最後のリーフ ノードに到達するまで再帰的に続行されます。その時点で、ハフマン ツリーは忠実に再構築されます。このような方法を使用した場合のオーバーヘッドは、約 2 ～ 320 バイトの範囲です (8 ビット アルファベットを想定)。他の多くの手法も可能です。いずれにしても、圧縮データには未使用の「末尾ビット」が含まれる可能性があるため、デコンプレッサは出力の生成を停止するタイミングを決定できなければなりません。これは、圧縮モデルとともにデコンプレッサ データの長さを送信するか、入力の終了を示す特別なコード シンボルを定義することによって実現できます (ただし、後者の方法はコード長の最適性に悪影響を与える可能性があります)。 ${\displaystyle B\cdot 2^{B}}$

使用される確率は、平均的な経験に基づいたアプリケーション ドメインの一般的な確率、または圧縮されるテキストで実際に検出された頻度になります。この場合、圧縮されたテキストとともに頻度表を保存する必要があります。この目的で使用されるさまざまな手法の詳細については、上記の「解凍」セクションを参照してください。

ハフマンのオリジナルアルゴリズムは、入力確率分布が既知のシンボルごとの符号化、つまり、そのようなデータストリーム内の無関係なシンボルを個別に符号化する場合に最適です。ただし、シンボルごとの制約が削除された場合、または確率質量関数が不明な場合は最適ではありません。また、シンボルが独立しておらず、同一に分布していない場合、単一のコードでは最適性が得られない可能性があります。算術符号化などの他の方法の方が、多くの場合、より優れた圧縮能力を備えています。

前述の 2 つの方法は、任意の数のシンボルを組み合わせてより効率的なコーディングを行うことができ、一般に実際の入力統計に適応できますが、算術コーディングでは計算やアルゴリズムの複雑さが大幅に増加することはありません (ただし、最も単純なバージョンはハフマン コーディングよりも遅く複雑です)。このような柔軟性は、入力確率が正確にわかっていない場合やストリーム内で大幅に変化する場合に特に役立ちます。ただし、ハフマン コーディングの方が通常は高速であり、算術コーディングは歴史的に特許の問題で懸念される対象でした。そのため、多くのテクノロジでは歴史的に算術コーディングを避け、ハフマン コーディングやその他のプレフィックス コーディング手法を採用してきました。2010 年半ばの時点で、ハフマン コーディングの代替として最も一般的に使用されている手法は、初期の特許が期限切れになったためパブリック ドメインになっています。

均一な確率分布を持ち、要素の数が2 の累乗であるシンボルの集合の場合、ハフマン符号化は単純なバイナリブロック符号化( ASCII符号化など)と同等です。これは、どのような圧縮方法を使用しても、このような入力では圧縮が不可能であるという事実を反映しています。つまり、データに対して何もしないことが最適な方法です。

ハフマン符号化は、各入力シンボルが既知の独立した同一分布の確率変数であり、その確率が2 項である場合、すべての方法の中で最適です。プレフィックス コード、特にハフマン符号化は、確率がこれらの最適 (2 項) ポイントの間にあることが多い小さなアルファベットでは非効率になる傾向があります。ハフマン符号化の最悪のケースは、最も可能性の高いシンボルの確率が 2 ⁻¹ = 0.5 をはるかに超え、非効率性の上限が無制限になるときに発生する可能性があります。

ハフマン符号化を使用しながら、この特定の非効率性を回避するための 2 つの関連するアプローチがあります。固定数のシンボルを組み合わせる (「ブロッキング」) と、圧縮率が向上することがよくあります (低下することはありません)。ブロックのサイズが無限に近づくと、ハフマン符号化は理論的にエントロピーの限界、つまり最適な圧縮率に近づきます。^[6] ただし、ハフマン コードの複雑さは、エンコードされる可能性の数に比例し、ブロックのサイズに比例するため、任意の大きなシンボル グループをブロッキングすることは実用的ではありません。これにより、実際に行われるブロッキングの量が制限されます。

実用的な代替手段として広く使われているのが、ランレングス符号化である。この技術は、エントロピー符号化の前に一歩進んだもので、具体的には、繰り返されるシンボルの（ラン）を数えてから符号化する。ベルヌーイ過程の単純なケースでは、ランレングスを符号化するためのプレフィックスコードの中ではゴロム符号化が最適であり、これはハフマン符号化の技術によって証明されている。^{[7]同様のアプローチは、}修正ハフマン符号化 を使用するファックス機でも採用されている。しかし、ランレングス符号化は、他の圧縮技術ほど多くの入力タイプに適応できるわけではない。

ハフマン符号化には多くのバリエーションがあり、^[8]ハフマンに似たアルゴリズムを使用するものもあれば、最適なプレフィックスコードを見つけるもの（たとえば、出力に異なる制限を課すもの）もあります。後者の場合、方法はハフマンに似ている必要はなく、実際、多項式時間である必要もありません。

n進ハフマンアルゴリズムは、{0, 1,..., n − 1} のアルファベットを使用してメッセージをエンコードし、n 進ツリーを構築します。このアプローチは、ハフマンが最初の論文で検討したものです。バイナリ ( ) コードの場合と同じアルゴリズムが適用されますが、最も確率の低い2 つのシンボルだけではなく、最も確率の低い n個のシンボルが一緒に扱われます。n が2 より大きい場合、すべてのソース ワード セットがハフマン コーディングのn進ツリーを適切に形成できるわけではないことに注意してください。このような場合は、追加の 0 確率プレース ホルダーを追加する必要があります。これは、ツリーがn対 1 コントラクターを形成する必要があるためです。^{[説明が必要]}バイナリ コーディングの場合、これは 2 対 1 コントラクターであり、任意のサイズのセットでこのようなコントラクターを形成できます。ソース ワードの数がn −1 を法として 1 に一致する場合、ソース ワードのセットは適切なハフマン ツリーを形成します。 ${\displaystyle n=2}$

適応型ハフマン符号化と呼ばれるバリエーションでは、ソース シンボルのシーケンス内の最近の実際の頻度に基づいて確率を動的に計算し、更新された確率推定値と一致するように符号化ツリー構造を変更します。ツリーの更新コストによって、より柔軟で圧縮率も高い 最適化された適応型算術符号化よりも遅くなるため、実際にはほとんど使用されません。

ほとんどの場合、ハフマン符号化の実装で使用される重みは数値確率を表しますが、上記のアルゴリズムではこれは必要ありません。重みが完全に順序付けられた 可換モノイド を形成すること、つまり重みを順序付けて加算する方法のみが必要です。ハフマン テンプレート アルゴリズムでは、あらゆる種類の重み (コスト、頻度、重みのペア、数値以外の重み) と、多数の結合方法 (加算だけではない) のいずれかを使用できます。このようなアルゴリズムは、 の最小化など、他の最小化問題を解決できます。この問題は、最初に回路設計に適用されました。 ${\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}$

長さ制限ハフマン符号化は、最小の重み付きパス長を達成することを目標とする変種ですが、各コードワードの長さが指定された定数よりも小さくなければならないという追加の制限があります。パッケージマージアルゴリズムは、ハフマンアルゴリズムで使用されるものと非常によく似た単純な貪欲なアプローチでこの問題を解決します。その時間計算量は で、 はコードワードの最大長です。それぞれ事前ソートされた従来のハフマン問題とソートされていない従来のハフマン問題とは異なり、この問題を または 時間 で解決するアルゴリズムは知られていません。${\displaystyle O(nL)}$${\displaystyle L}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

標準的なハフマン符号化の問題では、コードワードを構成するセット内の各シンボルの送信コストは等しいと想定されています。つまり、長さがN桁のコードワードは、桁のうち 0 がいくつあるか、1 がいくつあるかなどに関係なく、常にNのコストがかかります。この想定に基づいて作業する場合、メッセージの総コストを最小化することと、桁の総数を最小化することは同じことです。

不均等な文字コストのハフマン符号化は、この仮定を除いた一般化である。符号化アルファベットの文字は、伝送媒体の特性により、不均一な長さになる可能性がある。一例として、モールス信号の符号化アルファベットが挙げられ、ここでは「ダッシュ」は「ドット」よりも送信に時間がかかるため、伝送時間におけるダッシュのコストは高くなる。目標は依然として加重平均コードワード長を最小化することにあるが、メッセージで使用されるシンボルの数を最小化するだけではもはや十分ではない。従来のハフマン符号化と同じ方法または同じ効率でこれを解決するアルゴリズムは知られていないが、Richard M. Karp ^{[9]によって解決されており、その解決法は Mordecai J. Golin [10]}によって整数コストの場合に改良されている。

標準的なハフマン符号化問題では、任意のコードワードを任意の入力シンボルに対応させることができると想定されています。アルファベット版では、入力と出力のアルファベット順は同一でなければなりません。したがって、たとえば、 にはコード を割り当てることはできませんが、代わりにまたは のいずれかを割り当てる必要があります。これは、この最適バイナリ アルファベット問題に対する初めての時間解決法を提示した論文^[11]の著者であるTC HuとAlan Tuckerにちなんで、Hu–Tucker問題としても知られています。この論文は、ハフマン アルゴリズムといくつかの類似点がありますが、このアルゴリズムのバリエーションではありません。後の方法である、Adriano GarsiaとMichelle L. Wachs (1977)によるGarsia–Wachs アルゴリズムでは、より単純なロジックを使用して、同じ合計時間制限内で同じ比較を実行します。これらの最適アルファベット バイナリ ツリーは、バイナリ検索ツリーとしてよく使用されます。^[12]${\displaystyle A=\left\{a,b,c\right\}}$${\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}}$${\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}}$${\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}}$${\displaystyle O(n\log n)}$

アルファベット順に並べられた入力に対応する重みが数値順になっている場合、ハフマン コードの長さは、これらの長さを計算することで見つけることができる最適なアルファベット コードと同じになり、Hu-Tucker コーディングは不要になります。数値的に (再) 順序付けられた入力から生成されるコードは、標準ハフマン コードと呼ばれることもあり、エンコード/デコードが容易なため、実際によく使用されるコードです。このコードを見つける手法は、ハフマン コーディングのように最適ですが、シャノン-ファノコーディングのように重みの確率がアルファベット順であるため、ハフマン-シャノン-ファノ コーディングと呼ばれることもあります。例に対応するハフマン-シャノン-ファノ コードは で、これも元のソリューションと同じコードワード長を持ち、最適です。しかし、標準ハフマン コードでは、結果は になります。 ${\displaystyle \{000,001,01,10,11\}}$${\displaystyle \{110,111,00,01,10\}}$

算術符号化とハフマン符号化は、すべてのシンボルが 1/2 ^{k の}形式の確率を持つ場合、エントロピーを達成して同等の結果を生成します。他の状況では、算術符号化はハフマン符号化よりも優れた圧縮率を提供できます。これは、直感的に、算術符号化の「コード ワード」が実質的に非整数ビット長を持つことができるのに対し、ハフマン コードなどのプレフィックス コードのコード ワードは整数ビットしか持てないためです。したがって、長さkのコード ワードは確率 1/2 ^kのシンボルにのみ最適に一致し、他の確率は最適に表現されません。一方、算術符号化のコード ワード長は、シンボルの真の確率と正確に一致させることができます。この違いは、アルファベットのサイズが小さい場合に特に顕著です。^[要出典]

プレフィックス コードは、そのシンプルさ、高速性、特許の保護範囲の少なさから、依然として広く使用されています。プレフィックス コードは、他の圧縮方法の「バックエンド」としてよく使用されます。Deflate ( PKZIPのアルゴリズム) やJPEGやMP3などのマルチメディアコーデックには、フロントエンド モデルと量子化があり、その後にプレフィックス コードが使用されます。ほとんどのアプリケーションでは、ハフマン アルゴリズムを使用して設計されたコードではなく、定義済みの可変長コードが使用されていますが、これらは「ハフマン コード」と呼ばれることがよくあります。

ウィキメディア・コモンズには、ハフマン符号化に関連するメディアがあります。

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Pressおよび McGraw-Hill、2001 年。ISBN 0-262-03293-7。セクション 16.3、pp. 385–392。 

• Rosetta Code のさまざまな言語でのハフマン符号化
• ハフマンコード（Python実装）
• ハフマン符号化の視覚化