ハフマン符号

あけましておめでとうございます。CTO長谷川です。

今年は基礎に立ち返って色々なアルゴリズムの復習をするという目標を一つ立てたので、面白いアルゴリズムを取り上げてはブログ記事を書いていこうと思います。今回は情報圧縮技術を勉強していました。圧縮技術は通信速度に限りがあるインターネットの世界ではものすごく重要な位置付けにあります。例えば、ネットで見る画像や動画はほとんどjpgやmp4などで圧縮されたものですし、zipファイルに固められたフォルダなんかも様々な圧縮技術が使われています。

今回はその中でも面白かったハフマン符号という文字の圧縮方式を紹介します。この圧縮方式はデイビッド・ハフマン氏が1951年、若干25歳のMIT学生時代に発明したものです。情報理論の授業で単位を取得するために、期末試験を受けるか、もしくは期末論文を書く選択があり、その論文のテーマが「文字や数字などの情報を最も効率的に表現する手法を探せ」というものでした。ハフマン氏は、その期末論文の回答としてハフマン符号を発明したのです。今でも例えばZipファイルなどの圧縮方式の一部として世界中で使われている圧縮手法を25歳のときに授業の宿題の一環で発明してしまうとは、まさに天才的です。

さて、ハフマン符号とはどのようなものでしょうか。この符号化の方式は、我々が使う文字の頻度に格差があることを利用して情報量の圧縮を実現します。例えば、英語ならば母音の「e」という文字が最も頻繁(英文字の12.5%)に出現し、「z」は最も稀である(全文字の0.09%)という統計をグーグルのPeter Norvig氏が発表しています。この統計を利用して、より頻繁に起きる文字をより少ないスペースで、より稀に起きる文字をより多くのスペースで表現しようというものです。

モールス信号もこれと同じ原理で組まれています。頻繁に起きる文字である「e」には、最も短い信号「.」、稀な文字である「z」には、長い信号「--..」が割り当てられています。

例えば、このブログ記事の冒頭の「あけましておめでとうございます。CTO長谷川です。」という文をハフマン符号化すると、次のようになります。

10000101100001001010111100010010111010011101011010011001111100000100111011011011110101111111000001111100100111

長さにして110ビット(0か1の上記の並びが110桁)です。元々の文は25文字ですが、日本語はUTF8というユニコードで機械の中では表現されており、日本語のユニコード1文字に付き24ビット消費します。

例えば、ひらがなの「あ」はコンピュータから見るとこう見えます。

111000111000000110000010

つまり、元々の文は25文字ですが、データ容量としては600ビット使っているということです。

もっと長い文章ではどうでしょうか。例えば、夏目漱石の「こころ」で試してみたところ、以下のような結果になりました。

Original character count:  174549
Original string bits:     4179584
Encoded string bits:      1268100

元々の文字数は約17万字、符号化による圧縮はなんと70%もデータ容量をセーブできます。

どのように符号化がなされるかというと、ハフマン符号化をするに当たって、以下のような辞書を作成します。前述した通り、頻繁に起きる文字を短いビット数で表現するようにします。

char       n                code
--------------------------------
の      7662               11111
い      6989               11010
私      2695              100010
が      2649              100000
生       784            10110110
事       747            10101101
わ       680            10001110
先       677            10000111
め       644            01111101
人       625            01110011
ろ       586            01100001
時       560            01000100
や       516            00100011
ば       480           111101010
分       470           111011111
出       469           111011110
見       453           111011000
自       415           110001111
K       411           110001110
み       409           110001100
奥       401           110001001
父       388           101101010
来       385           101101000
間       352           100110010
彼       348           100101111

上記の辞書は漱石のこころから算出したものです。漱石のこころに登場する人物たちが見事に符号化されています。「私」、「先生」、「K」などの符号化の順番などを分析していると面白いです。やはりというべきか「私」という文字が「K」という文字の前に来ていますね。この辞書を作るに当たって気を付けなければいけない点として、重複したコードが発生しないようにしなければいけません。例えば、「の」は「11111」ですが、もっと頻度が少ない文字、仮に「z」が「111110」のようなコードだと、「の」に続いて「0」が一つあるのか、「z」なのか分からなくなってしまいます。これを回避するために、内部では以下のような木構造を作ります。

tree structure

(出典:wikipedia)

この木を作成する簡易的なアルゴリズムとして、まずそれぞれの文字の頻度を算出し、頻度が少ないもの同士を繋げて一つの木に合体させていくということをするだけで、ハフマン木ができます。そのハフマン木を今度は天辺から下に辿っていって、右にいくときは1、左にいくときは0とコードを繋げていくと、上記の辞書が出来上がります。

コードを書いてみるとそのアルゴリズムのシンプルさと分かりやすさに感嘆します。私が書いたものを弊社のGitHubにて公開していますので、良かったら見て実行してみてください。