ハフマン符号化

トップページ研究分野と周辺パターン情報処理

データ圧縮技術は、圧縮したデータを元通りに復元出来る可逆圧縮と、圧縮した後は完全には元に戻せない非可逆圧縮に大別される。ハフマン符号化は、可逆圧縮技術の代表例で、JPEG等の画像圧縮を初めとして幅広く使われている(但し、ハフマン符号化自体は可逆圧縮だが、JPEG自体は他に様々なデータカットを行うため、非可逆である)。
コンピュータは文字や色彩等の全ての情報を、何らかの0と1のビット列で扱う。例えば仮に、A=000、B=001、C=010、等と其々の情報(ここではアルファベット)に同じ長さのビット列を割り当てるのを「固定長符号」、其々の情報に違う長さのビット列を割り当てるのを「可変長符号」という。
ハフマン符号は可変長で、登場頻度の高い情報から順に短い符号を割り当てる事で情報圧縮を行うのが原理である。

符号化(エンコード)の過程

例えば、「AAABBCCDBBAAAABCBA」というデータ(アルファベット18文字)を圧縮したいとする。
固定長符号では、例えば仮にA=0000、B=0001、C=0010、D=0011と4ビットずつの符号化を行う(左の00は共通しているが、26文字を考えて4ビットとした)。
このデータを固定長で表現すると、「0000 0000 0000 0001 0001 0010 0010 0011 0001 0001 0000 0000 0000 0000 0001 0010 0001 0000」と、4×18=72ビットが必要になる。
(静的)ハフマン符号化では、まず其々の情報の登場頻度を数える。A=8回、B=6回、C=3回、D=1回である。
これに基づき、以下のような「ハフマン木」を作る。登場頻度の最も少ない二つ(ここではCとD)を底辺に置き、上に接点(黒丸)を作って、その高さに三番目に少ない情報(ここではB)置いて、また上に接点を作る。
以下、同様に4番目、5番目(ここでは4番目までだが)、と頻度の高い情報ほど上に行くように接点を作っていく。
一番頻度の高い所まで行ったら、其々の段の二本の矢印について、全て左を0、右を1(これは逆でもよい)の番号を振る。
これで、図の曲矢印のように、例えば、Bを表現するう符号は「10」と決まる。上から通った矢印の0か1を繋げていくことで、其々の情報の符号が決まる。
これにより、登場頻度が高いほど、短い可変長符号が割り振られる事になる。

上記のハフマン符号化により、A=0、B=10、C=110、D=111、という可変長符号が割り振られた。
これで、最初の「AAABBCCDBBAAAABCBA」というデータを置き換えて見ると、「0 0 0 10 10 110 110 111 10 10 0 0 0 0 10 110 10 0」となり、計32ビットで、固定長の72ビットよりも(この例では)半分以下の圧縮が出来ている。
なおこのように、最初に情報の頻度を全て数え上げるのを静的ハフマン符号化と言うが、情報を一つずつ読み込むたびに、その時の頻度に基づいてハフマン木を作り変える方法も可能で、これを動的ハフマン符号化という。

復号化(デコード)の過程

符号にして圧縮したデータを、元のデータに復元する事を復号(デコード)という。
この場合は、「0 0 0 10 10 110 110 111 10 10 0 0 0 0 10 110 10 0」から、「AAABBCCDBBAAAABCBA」に戻す過程である。
上記の符号は、見易くするため、元のアルファベットごとにスペースを入れているが、実際には「00010101101101111010000010110100」と詰めて記録されている。これでも正確に復号化出来る仕組みを述べる。
この例では、最初の数字は0だ。0で始まる符合はAしかないので、Aと決まる。左から4番目の1が来ると、すぐにはどのアルファベットか決まらない。しかし、そのすぐ右が0なので「10=B」と決まる。
1が2つ続いて11となった場合は、その次が0なら110=Cと決まる。111となったらDだ。
ハフマン木を見れば一目瞭然であるが、或るアルファベットは、必ず1がいくつか続いた後に0を受けた所で符号化されている。この例では、最後のDだけは、1が3つ続いた場合である。
1が無いか、いくつか続いた後に0が来る事で一つの文字が決まる。このいくつかが文字(情報)ごとに全て異なっているので、正しく復号が行われる。