データ圧縮の基礎『ハフマン符号化』の仕組みを見てみよう

何度かこのブログでデータ圧縮（書庫やエンコードなど）について解説してきましました。

しかし、その詳しい仕組についてはまだ書いていません。実際、実践的なところは難しすぎるので私もよく分かっておらず、専門的なことまではわかりません。（プログラミングは今後しっかり勉強していきたいですね。）

ですが、漠然と「取り敢えずデータが少なくなるんだよ！」と言われても釈然としないでしょう。少なくとも、私は「元の情報を残したままデータを小さくするってどうやるんだろう？」と疑問を持ちました。

なので、この記事ではデータ圧縮の基礎部分でよく使われる「ハフマン符号化」について書いてみたいと思います。

情報数学のお話になりますが、概要だけならとても理解しやすいものなので、今回はこれをテーマにしてみます。データの圧縮とはどうゆうことなのか、その一端でも知りたい方はお付き合いください。

ついでに「なぜコンピューターは0と1で構成させているのか」「ビットとは」なども最初に補足として解説します。

この記事を書く動機

このブログは「パソコン初心者～中級者」を対象とした内容で書いていることが多いです。

ではなぜ、このような小難しい話を書こうと思ったのか。

私は、できる限り「仕組み」についても知ってもらいたいと思っています。もっとコンピューターを知って好きになってもらいたいです。また概要だけでも仕組みが分かれば、何か問題に出会った時でも根底部分から解決を試みることができるようになります。引き出しが多くなるわけですね。

そういった意味でも、初心者的な操作方法などとはかけ離れたことでも長々と今まで書いてきました。

今回もその流れです。データ圧縮について様々書いてきたので、圧縮技術の基礎となる「ハフマン符号」について、その概要を書いてみようと思い立ちました。

「ハフマン符号化」、なんか小難しそうに見えますが概要はそんなに難しいものではありません。比較的簡単な部類ですので、「なんでデータサイズを小さくできるのか」その一片でも知りたい方はお付き合いください。

コンピューターの基礎「すべての情報は 0 と 1 で構成される」

ハフマン符号の解説の前に、まずはコンピューターの基礎から書いていきます。これが理解できてないと「符号化」の意味がわからないと思いますので。もう知っているよ！と言う方はスルーしてください。そこそこ長いです。

通常、一般的なコンピューターはすべて「電気」によって動いています。

コンピューター内の回路には電気が流れています。この電気の流れをコントロールすることでコンピューターは計算をしています。ここまでは一般的な常識範囲かと思います。

では、実際どのように電気が流れているのか。

実はかなり単純で、回路内は「電気が流れている状態（ON）」 or 「電気がながれていない状態（OFF）」の2つの状態しかありません。一見不便そうに見えますが、エラーを起こさない方法としては非常に優秀な方法なのです。

電流というのは、どんなに精密に作っても少なからず「ゆらぎ」、誤差のようなものが発生してしまいます。しかし、例えば電圧が「0V～5V」までなら「電気がながれていない状態（OFF）」、「6V～10V」までなら「電気が流れている状態（ON）」と仮に定義すれば、多少電圧が揺れ動いても正しく「ON」「OFF」を認識、切り替えることができます。このように誤差を吸収できる、つまり回路内のエラーを最小限に抑えることができるため、「ON」「OFF」の2つの状態で制御させています。

この「ON」「OFF」を「1」と「0」に対応させてやることですべての情報を操るのです。プログラム側で電流が流れれば「1」、流れなければ「0」と認識するようにすれば電気の流れを数値に変換して処理できるようになります。

このように、 0 と 1 （2進数）で数える方法を「2進法」といいます。私たちはよく「0～9」までの10進数を利用した「10進法」を使って生活に役立てますね。人間の手の指の数が合計で10本あるからという理由が一般的らしいです。（確証はないらしいですけど・・・）

2進法の計算方法

10進法ならば、みなさんも御存知の通り「9」まで数えたら2桁になって繰り上がり「10」となりますね。

2進法でも同じように「0」→「1」と数えたら2桁になり「10」となります。そこから「11」→「100」→「101」・・・のように数えていきます。10進数と違うのは繰り上がりのサイクルが早いだけで基本は同じです。

なので計算は以下の通りになります。Windows7以降の電卓ならば2進数の計算もできるので一度お試しを。

「スタートメニュー」→「アクセサリ」に標準の電卓があります。Windows8ならばスタート画面で「電卓」と入力すれば見つかります。

加法：1001 + 1101 = 10110　/　減法：1110 – 1001 = 101

文字とかはどうやって表現するの？　- 符号化・復号化 –

さて、これで「0」と「1」に関しては表現できるようになりました。

では、2以上の数字や文字などはどう表現すればいいのでしょうか。気になりますよね。

コンピューターの回路は 0 と 1 の2つしか電気信号として回路内へ乗せられないので、すべての数字・文字を「0」と「1」で構成させてやらないといけません。そこで、世界共通の「対応表」が考えださせれました。

尺の関係でかなり省いていますが、以上は「ASCⅡ」と呼ばれるコード対応表（文字コード）の一部です。

それぞれの文字がすべて2進数で表現できるようになっています。これをプログラムが辞書として使うように設計すれば、すべての文字が 0 と 1 で処理できるようになります。今回は「ASCⅡ」を例にしましたが、他にも用途によって「Shift_JIS」「UTF-8」などの文字コードがあり、それぞれ割り当てられている文字が異なります。

そして、これら0と1に変換されたデータを「符号」と呼び、符号にすることを「符号化」と呼びます。

逆に、符号化されたデータを元の記号に戻すことを「復号化」といいます。

ビット

ビット【bit】とは、コンピューターが扱えるデータの最小単位を示す言葉です。「binary digit」を略したものらしいです。

ここまで勉強してきた方ならばお分かりでしょう。コンピューターはすべて2進数でデータを処理するということは、これらがコンピューターにおける最小単位となります。「1bit」ならば、「1」または「0」というデータになります。

そして、一般的に「8bit = 1Byte（バイト）」と定義付けられています。これは昔、爆発的に広まったコンピューターが8bitを1Byteとして設計したから、という理由らしいです。（7bit=1Byteというコンピューターもありました。）

例えば、100KByte（キロバイト）のデータは80万bit、つまり80万個の 0 と 1 のデータで構成させていると言い換えることができます。コンピューターはこれだけの情報をいとも簡単に処理できる能力を持っているということですね。

ハフマン符号化

前知識を解説したところで、本編「ハフマン符号化」について書いていきます。

ハフマン符号とは

ハフマン符号化【Huffman coding】とは、1952年にDavid Albert Huffman氏（デビット・ハフマン）によって考案された、可逆圧縮の代表的アルゴリズムです。（アルゴリズム【Algorithm】：仕事をさせるための手順）

コンパクト符号という符号化の一種で、一意に復号可能な符号のうち平均符号長が他より小さい符号のことを言います。

一意とは、2つ以上の値が存在しないことです。つまり、復号する際に解釈の違いによって復号後の結果が異ならないということを意味します。平均符号長とは、名前の通り全体の符号長の平均です。符号化前の符号の平均の長さより、符号化後の平均の長さが短くなれば圧縮成功となります。

まとめると、コンパクト符号の一種であるハフマン符号は『復号後の結果はちゃんと元の符号に戻ることができ、かつ全体のデータ量を減らすことができる符号化』ということになります。各記号の出現確率を事前に求め、出現度の高い文字を短い符号で、出現率が低い文字を長い符号で表現することで、平均符号長を最小とする圧縮技術です。

JPEGやZIP (Deflate) などの圧縮フォーマットで使用されているところをみれば分かる通り、ハフマン符号は算術符号などと異なり特許の問題がありません。誰もが自由に使うことができます。

符号化の手順

ハフマン符号化をすると、元の符号よりも必ず短くなります。常に最適解を求めることができるのです。
では、どのように平均符号長を短くするのでしょうか。

以上がハフマン符号化の大まかな手順になります。どうでしたか、意外に簡単なものかと思ったのではないでしょうか。

これがJEPG圧縮やZIP圧縮の基礎部分で使われている圧縮技術です。JPEG圧縮は不可逆圧縮なので、ハフマン符号化を適用する前に複雑なデータのカット処理が実行されていますが、その後は以上のようなハフマン符号化をしています。

ハフマン符号は、各記号の出現率の幅が広ければ広いほど圧縮率が高くなります。

今回解説した手順は、最初にすべての文字の出現頻度を調査してからハフマン木を作りました。このように、最初にデータの解析をして2度目に符号化を実行するハフマン符号化を「静的ハフマン符号 【Static Huffman coding】」といいます。汎用性が高く、多くのデータで実行できる圧縮方法です。ただ、全体の調査に1回、符号化に1回と最低でも2回のデータ走査が必要になるため、圧縮速度はそこまで早くないデメリットがあります。

一方、記号を1つ読み込む度にハフマン木を作り直し符号化を実行するハフマン符号化を「適応型ハフマン符号【動的ハフマン符号, Adaptive Huffman coding】 」といいます。こちらは最初の全体調査は不要なため、符号化も早くなるメリットがあります。ただ、データによっては必ずしも最小符号ができるわけではなく、若干圧縮率に劣ります。ですが、実用性に問題ができるほどではないので、一回で符号化が終わる利点を活かしてリアルタイムの符号化が必要なデータの場合には有効です。

ハフマン符号の復号

さて、符号化（エンコード）ができたら今度は復号（デコード）ができないといけません。

固定長符号の場合は、符号長が常に一定なので「最初から3bitずつ読んでいって、合致した記号に戻す」という作業をすれば一意の復号化ができます。

000011001010001000001010001001010100

固定長符号ならば、以上のようにスペースがない連続した符号でも、3bitずつ（固定長ずつ）読み込んでいけば
「000＝A」「011＝D」「001＝B」…と文字コードに合わせて簡単に復号化できます。

では、可変長符号の場合はどうでしょう。

1101110010011001000101111

可変長符号の場合は、○bitずつという区切り方では元の記号に戻すことができません。上の符号を最初に3bit読みこめば「110＝A」となりますが、同じように次も3bit読み込むと「111」となり「合致する記号なし」と判断されてしまいます。

ではどうするのか。実はハフマン符号化をした時点でこの問題は解決済みです。

ハフマン符号のすごいところは、各記号に対する符号化で「全く同じビットの並びが存在しない」ような符号化をするというところです。

文字	固定長符号	可変長符号
B	001	0
C	010	10
A	000	110
D	011	1110
E	100	1111

復号化する際は左から順に符号を読み取っていきます。上のデータの場合、最初に読み込む符号は「1」ですね。では、この1から予測される元の記号はなんでしょうか。「C」「A」「D」「E」になりますね。では2bit目・3bit目と読んでいってみてください。3bit目で「110」が読み取られ「110＝A」が合致し確定しますね。

ハフマン符号では、この途中で元の記号以外の符号パターンが存在しないような符号化をするのです。

例えば、仮に「110＝A」「11＝B」という符号化をしてしまったとします。すると、「110＝A」を求める前に2bit目で別の記号と合致するようなパターン、つまり「11＝B」が出現してしまいます。ここで復号をしてしまうと、次に読み込まれるのは「0」からになってしまい、1つ左にずれてしまいます。これでは以降正しく復号化することができなくなってしまいます。

しかし、ハフマン符号化をした場合はこのような事態には絶対になりません。

これは、ハフマン木と呼ばれるツリー構造を作ったからです。ツリー構造を作ると、木の葉へ向かって曲がることで、接点に割り振られているビットとは逆のビットが割り振られるためです。

なので、ハフマン符号を復号するためには「○bitずつ」という制限で読み込むのではなく「順にビット列を読み込んでいって、一番最初に合致した記号で復号する」とやっていけば元の記号へ戻すことができます。

1101110010011001000101111

左から順に、最初に合致した記号で複合します。
最初は「110＝A」が合致する、次は「1110＝D」が合致、次は「0＝B」が合致…と順に合致した記号で戻していけば正しく復号できます。

このように、符号の切れ目が無くとも順に読み込んでいけば正しく復号できる符号を「瞬時復号可能な符号」といいます。ハフマン符号は瞬時復号可能な符号のひとつです。

ハフマン符号は瞬時復号可能で一意の復号ができますので、コンパクト符号の条件に一致します。

まとめ

いかがでしたでしょうか。データ圧縮の基本のひとつ「ハフマン符号化」について解説しました。

「広く使われているから、さぞ難しいことをしているんだろうな～」と思っていた方も多いかと思いますが、このハフマン符号は結構理解しやすかったのではないでしょうか。

これを知ったからといって何かに役立つかと言われれば、プログラミングをしない限りは雑学で終わってしまいそうです。ですが、いつも自分が使っているJPEG圧縮やZIP圧縮の原理のひとつが理解できたことになります。

「なんで圧縮するとデータが小さくなるのに元のデータの情報は失わないのか？」という疑問を持った方は、この記事でその原理のひとつを知ったことになります。

今までの記事とは少し方向性が異なりましたが、この記事も何かお役になてたのならば幸いです。