ハフマン符号化の解説
コンピューターはふつう、どの文字も同じビット数で保存します。素の ASCII では8ビットです。これは単純ですが無駄があります。ほかの文字よりずっとよく使われる文字があるからです。1951年、ある学生が、各記号にそれぞれの長さの符号を与える最良の方法を見つけました。よく現れる記号は短く、まれな記号は長くする方法で、その構成は数行に収まるほど単純です。ハフマン符号化は今や、あなたが開く圧縮ファイル、画像、音声のほとんどすべてに使われています。
よく現れる記号には短い符号を
モールス符号は1830年代にすでにこの考え方を使っていました。英語で最もよく使われる文字 E は短点1つ、Q は長点・長点・短点・長点です。このような符号は、ほかより頻繁に現れる記号があるときにはいつも、時間と場所を節約します。しかし長さがまちまちだと問題が生じます。モールス符号は間を空けることで解決しましたが、1つの符号がどこで終わり、次がどこから始まるのかをどうやって知るのでしょうか。そして合計をできるだけ小さくするには、各記号にどの長さを与えればよいのでしょうか。
接頭符号
どの符号も別の符号の先頭部分にならなければ、最初の問題は消えます。A = 0、B = 10、C = 110、D = 111 という符号では、ビット列 0101100 は A B C A としか読めません。それまでに読んだビットが1つの符号になった時点で、その符号は完結しているからです。このような接頭符号は、記号を葉に置いた二分木とぴったり対応し、左の枝はそれぞれ 0、右の枝はそれぞれ 1 を表します。符号を選ぶことは、木を選ぶことなのです。
ハフマンの構成法
記号ごとに1枚の葉を用意し、その出現回数で重み付けします。最も軽い2つの木を取り出し、重みがその合計である新しいノードの下にまとめ、木が1つになるまで繰り返します。アルゴリズムはこれだけです。まれな記号は最初にまとめられて木の深いところに行き着き、長い符号を持ちます。よく現れる記号は最後にまとめられて上の近くに残り、短い符号を持ちます。優先度付きキューを使えば、n 個の記号に対して n log n に比例する時間で済みます。
最適である理由
可能な限り最良の木では、最もまれな2つの記号を常に最も深い階層に兄弟として置くことができます。そこにあるものと入れ替えても、合計は短くなるだけだからです。その2つを重みの合計を持つ1つの記号にまとめると、残りは記号が1つ少ない同じ問題になります。そのため、貪欲なこのステップが最良の答えへの道を閉ざすことはありません。使われるビットの総数はすべての内部ノードの重みの合計に等しく、まとめる手順はそれをできるだけ小さく保ちます。
試験の代わりにレポート
1951年、MIT の大学院生だったデビッド・ハフマンは、ロバート・ファノの情報理論の講義を受けていました。ファノは学生たちに、期末試験を受けるか、最も効率のよい二進符号を見つけることについてレポートを書くかを選ばせました。ハフマンはレポートをあきらめかけましたが、そのとき、シャノン・ファノ法のように上から分割していくのではなく、下から木を組み上げれば常に最良の結果が得られることに気づきました。彼は1952年にそれを発表しました。学生の方法が、教授がクロード・シャノンとともに考え出した方法を上回ったのです。
エントロピーに迫る
クロード・シャノンは、平均して1記号あたり情報源のエントロピーより少ないビット数で済む符号は存在しないことを示しました。ハフマン符号は、すべての確率が2分の1のべき乗のときにちょうどエントロピーに達し、1記号あたりまる1ビット上回ることは決してありません。この差が問題になるのは、ある記号がとても多いときです。99% を占める記号は約 0.015 ビットの情報しか持たないのに、少なくとも1ビットまるごと必要です。算術符号化や、新しい圧縮プログラムの非対称数系(ANS)はこの制約を避けます。
あらゆるところにあるハフマン符号
ハフマン符号化が単独で使われることはまれですが、多くの形式の最終段階を担っています。ZIP、gzip、PNG の中にある Deflate は、まず繰り返しを参照に置き換え、その結果をハフマン符号で書き出します。JPEG は画像を変換した後に残る数値に、MP3 は音声データに、ファクスは白と黒のランの長さにハフマン符号を使います。各形式ではふつうカノニカルハフマン符号を送ります。符号そのものは符号長から作り直せるので、保存するのは符号長だけで済むのです。
試してみよう
ハフマン符号ビルダーを開いて、ABRACADABRA、MISSISSIPPI RIVER、自分で作った文、そのほか好きなテキストの木を1ステップずつ作ってみましょう。各ステップで最も軽い2つの木がまとまる様子を見て、葉をクリックして符号を確かめ、符号化されたビット列の中で記号を追い、合計を固定長符号、UTF-8、エントロピーと比べられます。
よくある質問
ハフマン符号化とシャノン・ファノ符号化の違いは何ですか?
シャノン・ファノ符号化は、記号を重みがほぼ等しい2つのグループに分けることを繰り返し、上から木を作ります。多くの場合よい結果になりますが、常に最適とは限りません。ハフマン符号化は最も軽い2つの木をまとめて下から木を作り、常に可能な限り最短の接頭符号を与えます。
復号器には木が必要ですか?
はい、同じ符号が必要です。そのため圧縮ファイルはそれを保存します。ふつうはカノニカル符号の符号長のリストとして保存し、数十バイトしかかかりません。短いテキストではこの付加分が削減分を上回ることがあります。このビルダーは符号化されたビットだけを数えています。
ハフマン符号化でファイルが大きくなることはありますか?
符号化された記号が、同じ記号の固定長符号より多くのビットを使うことはありません。しかし符号表も保存しなければならないので、とても短いデータやほぼランダムなデータでは、結果が元よりわずかに大きくなることがあります。
クラフトの不等式とは何ですか?
符号長 l₁, l₂, … の接頭符号が存在するのは、すべての記号についての 2 の −l 乗の和が 1 以下であるときであり、そのときに限る、というものです。少なくとも2つの記号を持つすべてのハフマン木のように、どの内部ノードも子を2つ持つ木では、和はちょうど 1 になります。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
ハフマン符号ビルダーを開く