ハフマン符号化

与えられた

記号のセット${\displaystyle S}$そして各シンボルについて${\displaystyle x\in S}$周波数${\displaystyle f_{x}}$テキスト中の記号のうち、${\displaystyle x}$[ ^{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 {weight} \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(C(W))=\sum _{i=1}^{n}w_{i}\operatorname {length} (c_{i})}$コードの重み付きパス長${\displaystyle C}$。 状態：${\displaystyle L(C(W))\leq L(T(W))}$任意のコードに対して${\displaystyle T(W)}$。

ここでは、5文字の符号と与えられた重みに対するハフマン符号化の結果の例を示します。すべての符号の中でLを最小化するとは断言しませんが、Lを計算し、与えられた重みセットのシャノンエントロピーHと比較します。結果はほぼ最適です。

一意性を持つコード、つまり一意に復号可能なコードの場合、すべてのシンボルにわたる確率予算の合計は常に1以下になります。この例では、合計は厳密に1に等しく、その結果、このコードは完全コードと呼ばれます。そうでない場合でも、追加のシンボル（関連するゼロ確率を持つ）を追加することで、コードを完全化しつつ一意性を維持できる同等のコードを導出できます。

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

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

エントロピーH (ビット単位) は、非ゼロ確率 w i を持つすべてのシンボル a 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ビットよりわずかに大きいだけです。したがって、この符号は、これより優れた性能を持つ他の実現可能な符号が存在しないという意味で最適であるだけでなく、シャノンによって確立された理論上の限界に非常に近いと言えます。

一般に、ハフマン符号は一意である必要はありません。したがって、与えられた確率分布に対するハフマン符号の集合は、以下の値を最小化する符号の空でない部分集合です。${\displaystyle L(C)}$その確率分布に対して。（ただし、符号語長を最小化する各割り当てに対して、その長さを持つハフマン符号が少なくとも1つ存在する。）

この手法は、ノードの二分木を作成することで機能します。これらは通常の配列に格納でき、そのサイズはシンボルの数に依存します。${\displaystyle n}$ノードは、リーフノードまたは内部ノードのいずれかになります。最初は、すべてのノードはリーフノードであり、シンボル自体、シンボルの重み（出現頻度）、およびオプションで親ノードへのリンクが含まれています。これにより、リーフノードから始めてコードを（逆方向に）簡単に読み取ることができます。内部ノードには、重み、 2 つの子ノードへのリンク、およびオプションで親ノードへのリンクが含まれています。一般的な慣例として、ビット「0」は左の子をたどることを表し、ビット「1」は右の子をたどることを表します。完成したツリーには最大で${\displaystyle n}$葉節と${\displaystyle n-1}$内部ノード。使用されていないシンボルを除外したハフマン木は、最適なコード長を生成します。

このプロセスは、葉ノードにそれぞれのシンボルの確率を格納することから始まります。次に、確率が最も低い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 つのキューのいずれかの先頭に保持されることが保証されます。^{[ 2 ]}

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

ハフマン木が生成されたら、それを走査して、シンボルをバイナリコードにマッピングする辞書を以下のように生成します。

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

最終的なシンボルの符号化は、ルートノードからシンボルまでのパスに沿ったエッジ上のラベルを連結することによって読み取られます。

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

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

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

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

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

一様確率分布を持ち、要素数が2のべき乗である記号の集合の場合、ハフマン符号化は単純なバイナリブロック符号化（例えばASCII符号化）と同等になります。これは、どのような圧縮方法を用いても、このような入力では圧縮が不可能であること、つまり、データに対して何も処理を行わないことが最適であることを示しています。

ハフマン符号化は、入力ストリームの各位置が既知の独立同分布の確率変数であり、その確率が二進数である場合、あらゆる方法の中で最適です。プレフィックスコード、特にハフマン符号化は、アルファベットが小さい場合、効率が悪くなる傾向があります。アルファベットが小さい場合、確率はこれらの最適な（二進数）点の間にあることが多いためです。ハフマン符号化の最悪のケースは、最も可能性の高いシンボルの確率が 2 ⁻¹ = 0.5 をはるかに超える場合であり、非効率性の上限は無制限になります。

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

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

n進ハフマンアルゴリズムは、通常 {0, 1, ..., n-1} のサイズnのアルファベットを使用してメッセージをエンコードし、n進木を構築します。このアプローチは、ハフマンが元の論文で検討しました。バイナリ (${\displaystyle n=2}$）コードですが、可能性が最も低い 2 つのシンボルを組み合わせる代わりに、可能性が最も低いn個のシンボルがグループ化されます。

n > 2の場合、すべてのソースワードのセットがハフマン符号化用の完全なn進木を適切に形成できるとは限らないことに注意してください。このような場合、確率が 0 の追加のプレースホルダーシンボルを追加する必要があるかもしれません。これは、ツリーの構造がn個の枝を繰り返し 1 つに結合する必要があるためです。これは「 n対 1」の組み合わせとも呼ばれます。バイナリコーディングでは、これは「 2 対 1」の組み合わせであり、任意の数のシンボルで機能します。n進コーディングでは、完全なツリーは、シンボルの総数 (実数 + プレースホルダー) を (n-1) で割ったときに余りが 1 になる場合にのみ可能です。^{[ 1 ]}

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

ハフマン符号化の実装で使用される重みは、多くの場合、数値確率を表しますが、上記のアルゴリズムではこれを要求しません。必要なのは、重みが完全順序付き可換モノイドを形成すること、つまり重みを順序付け、加算する方法があることだけです。ハフマンテンプレートアルゴリズムを使用すると、あらゆる種類の重み（コスト、頻度、重みのペア、非数値重み）と、多くの結合方法（加算だけでなく）のいずれかを使用できます。このようなアルゴリズムは、最小化などの他の最小化問題を解決できます。${\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 ]}によって整数コストの場合に改良されました。

標準的なハフマン符号化問題では、任意の符号語が任意の入力シンボルに対応できると仮定されます。アルファベット版では、入力と出力のアルファベット順が一致する必要があります。したがって、たとえば、${\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\}}$これは、最初の論文を発表したTC HuとAlan Tuckerにちなんで、 Hu-Tucker問題としても知られています。${\displaystyle O(n\log n)}$この最適なバイナリアルファベット問題に対する時間解法は、 ^{[ 11 ]}ハフマンアルゴリズムと類似点があるものの、このアルゴリズムの変種ではない。後の手法である、アドリアーノ・ガルシアとミシェル・L・ワックスによるガルシア・ワックスアルゴリズム（1977年）は、同じ合計時間制限内で同じ比較を実行するために、より単純なロジックを使用している。これらの最適なアルファベットバイナリツリーは、バイナリサーチツリーとしてよく使用される。^{[ 12 ]}

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