よく出る記号へ短い符号を割り当てる
Huffman符号は、記号の出現回数や確率に応じて長さの異なるビット列を割り当てる可逆圧縮の方法です。よく出る記号を短くすることで、全体の平均符号長を小さくします。ただし短い符号を自由に付ければよいわけではありません。ある記号の符号が別の記号の符号の先頭にならない接頭語自由の性質が、区切り文字なしの復号を支えます。たとえば0と01を別の記号へ割り当てると、0を見ただけで記号が完成したかを決められません。Huffmanの二分木では記号を葉へ置くことで、このような途中の曖昧さを避けます。
最小の二つをまとめて木を育てる
各記号を一つの葉とし、その出現回数を重みにします。最も軽い二つの木を取り出し、新しい親で結び、親の重みを二つの合計にします。これを一つの木になるまで繰り返します。左右の枝へ0と1を付けると、根から葉までの経路が符号になります。同じ重みの選び方や左右の配置によって、ビット列そのものは変わる場合があります。最適な平均長が得られることと、符号表が一意であることは異なります。圧縮側と復号側が同じ表を使えるように、木の表現や符号長の伝え方も形式の一部として決めます。
四記号の併合とビット数を計算する
説明用にAが5回、Bが2回、CとDが各1回現れるとします。CとDを重み2へまとめ、重み2のBと併合して4にし、最後にAの5と4をまとめます。Aの符号長は1、Bは2、CとDは3になります。本文に使う総ビット数は5×1+2×2+1×3+1×3で15です。四記号すべてを固定2ビットにすると9記号で18ビットなので、この本文部分では3ビット小さくなります。ただし符号表や元の長さを保存する費用はまだ含めていません。短い入力では、その付加情報の方が節約分より大きい場合もあります。
復号は葉へ着くたび根へ戻る
たとえばAを0、Bを10、Cを110、Dを111とする符号表を使えます。ビット列010110111は、0、10、110、111と読めるため、ABCDへ戻せます。葉へ達したら記号を出力し、再び根から次のビットを読む手順です。復号器は途中で入力が終わった場合、無効な木や長さが渡された場合も扱う必要があります。一種類の記号しかない入力や空の入力では、一般の併合手順だけでは形式の扱いが決まらないので、符号長や元の記号数の規則を明示します。学習用の小さい例を、そのまま任意の壊れた入力も受け付ける実装にしないようにします。
何に対して最適かを限定する
Huffmanの最適性は、与えた頻度に対して一記号ずつ二進の接頭語符号を割り当てる範囲での重み付き長さに関するものです。すべての圧縮方式、すべての入力、すべてのファイル形式で最小になるという意味ではありません。記号同士の並びの偏りを利用する方式や、別の符号化方法では異なる結果になり得ます。実際の入力で頻度が変われば、先に作った表の効率も変わります。文字を記号とするか、バイトを記号とするかも設計の条件です。Unicodeの見た目の一文字と、保存した一バイトを同じ単位として数えないようにします。
優先度付きキューで実装する
異なる記号がk種類あるとき、最小ヒープなどの優先度付きキューから二つずつ取り出せば、木の構築は一般にO(k log k)で行えます。入力全体の出現回数を数える処理や、符号を出力する費用は別に加えます。圧縮率を評価するときは、本文ビットだけでなく付加情報とパディングも含め、復号後に元の入力へ一致することを確認します。頻度が同じ記号、空入力、一種類だけの入力、不正な切詰めを試すと、通常例では見えない境界を検査できます。ここでの15ビットは手計算の結果で、特定の圧縮ツールのファイルサイズを測定した値ではありません。