UUUMエンジニアブログ

UUUMのエンジニアによる技術ブログです

圧縮アルゴリズム(ハフマン符号)

アルゴリズム

おはこんばんちは 尾藤 a.k.a. BTO です。

少し間が空きましたが、前回は連長符号について書きました。

system.blog.uuum.jp

今回はハフマン符号について書きます。 ハフマン符号は、平均符号長が最小になるコンパクト符号として良く知られています。

圧縮アルゴリズムはよく特許が問題になるケースが多く、採用する場合には常にそのアルゴリズムが特許上問題ないのかを検証する必要があります。 その点、ハフマン符号はパテントフリーなアルゴリズムなので、特許問題に悩まされることもないです。

このように、ハフマン符号は符号長が最小であること(高効率)、パテントフリーであること(訴えられるリスクがない)から、データ圧縮では非常に採用率の高いアルゴリズムです。 例えば身近なところだと、HTTP2のヘッダはハフマン符号で圧縮されています。 応用範囲の広いアルゴリズムですので、覚えておいて損はないでしょう。

可変長符号

ハフマン符号に入る前に、可変長符号について考えてみます。 可変長符号とは、その名の通り符号長が可変する符号です。

例えば、ASCIIコードは7ビットでビット長が固定されているので、固定長符号です。 UTF-8 は、1バイトだったり、2バイトや3バイトで表現したりしますので、可変長符号です。

ハフマン符号の場合は、データ圧縮が目的ですので、UTF-8のように1バイト単位で符号長が変化したりせず、ビット単位で符号長を変えます。

データ圧縮での可変長符号を考えるときには、次のような点を考慮しないといけません。

  • 一意復号可能
  • 瞬時復号可能
  • 平均符号長

一意復号可能

一意復号可能かどうかということは、復号結果が一つに定まるかどうかということです。 これは可変長符号に限らずどの符号にも言えることですが、復号結果が一意定まらなければ元の情報を取り戻すことができません。 ですので、符号化には絶対必要な条件であると言えます。

例えば次のような符号を考えてみます。

記号 符号
a 0
b 1
c 00
d 01

この符号に対して、010001 を復号してみましょう。 やってみるとわかりますが、複数の復号結果があります。

abcd
dcd
abaaab

どの文字列も同じ 010001 に符号化できるのが確認できると思います。

このように一意復号可能でなければ、復号結果が複数になりますので、元のデータを復元することができません。 符号を決めるときには一意復号可能な符号を定めてやる必要があります。

瞬時復号可能

仮に一意復号可能な符号を決めても、瞬時復号可能でなければ効率よく処理することができません。 瞬時復号可能とは、データを読み込んだ時に前後のデータに依存しないで復号可能なことを言います。

瞬時復号可能な符号は前後のデータに依存しないので、すぐに復号でき、復号が終わったデータはもう必要ないので捨てることができます。 一方で瞬時復号可能でない符号は、前後のデータを保持しないと復号結果は定まらないので、処理が複雑になりますし、使用するメモリ量も多くなってしまいます。

語頭条件

ある可変長符号が瞬時復号可能になるためには、一番簡単なのは語頭条件を満たすことです。

語頭条件とは、ある符号が他の符号の先頭部分と一致しないという条件です。 この条件を満たせば、復号を始めたポイントから符号が見つかった場合に、他の符号とかぶることが絶対にない(先頭部分に一致する符号が存在しない)ので、瞬時復号可能になります。

例: 瞬時復号不可能

次のような符号を考えてみます。

記号 符号
a 0
b 01
c 011
d 111

この符号は一意復号可能ですが、語頭条件を満たしてなく瞬時復号不可能な符号になっています。 aは0という符号が割り当てられていますが、bの01とcの011の先頭部分に含まれています。 つまり0を読み込んだ時点では、a|b|cのいずれで複合すればいいかが確定できないわけです。

この符号を使って001011111を復号してみます。 結論から言うと、復号結果はabcdになるのですが、その過程を考えてみます。

まず最初に0を読み込みます。 この時点で復号の候補はa|b|cです。 なぜなら3つとも0で始まるので、この時点はどれで復号するかがわからないからです。

次に2つめの0を読み込みます。 ここで初めて、最初の0がaであることが確定します。 なぜなら、00で始まる符号がないので、最初の0はa以外ありえないからです。

同じ用に処理していくと、復号過程は次のようになります。

0:         a|b|c
00:        a(a|b|c)
001:       a(b|c)
0010:      ab(a|b|c)
00101:     ab(b|c)
001011:    ab(bd|c)
0010111:   ab(bd|cd)
00101111:  ab(bd|cd)
001011111: abcd

このように瞬時復号不可能な符号は、データを先読みしないと一意復号できないので、著しく処理が複雑になりますし、使用するメモリ量を多くなってしまいます。

平均符号長

次に平均符号長について考えてみます。 平均符号長は、その名の通り平均した時の符号長です。 アスキーコードは元々7ビットの固定長符号なので、平均符号長は当然7ビットになります。 データ圧縮する可変長符号では、もちろんこの7ビットよりも平均符号長が短くなるように符号を決めます。

基本的な考え方としては、頻出頻度の高いデータには短い符号を割り当て、頻出頻度の低いデータには長い符号を割り当てるということになります。 平均符号長は短くなればなるほど、圧縮率は高くなります。

計算自体は簡単で、各符号の符号長×頻出頻度の総和を求めるだけです。

ΣP_i * L_i

P_i は i番目の記号の出現確率
L_i は i番目の記号の符号長

ハフマン符号

さて、ようやくハフマン符号の話に入ります。 ハフマン符号は上記で示した条件を全て満たしています。

  • 一意復号可能
  • 瞬時復号可能
  • 平均符号長が最も短い

ハフマン木

ハフマン符号を作るために、ハフマン木という木構造のデータを作成します。 ハフマン木が次のような処理で作成します。

  1. すべての記号の種類、出現率を調べる
  2. 各記号を葉とする
  3. 出現率の最も小さいもの同士で接点を作る
  4. 枝に0,1のラベルをつける
  5. 接点に2つの葉の出現率の合計を書き、これを新たな葉と考える
  6. 3-5を葉(接点)が1つになるまで繰り返す

では、実際にハフマン木を作成してみましょう。 次のような記号の出現率をもったデータを考えてみます。

記号 出現率
a 0.44
b 0.19
c 0.17
d 0.15
e 0.05

まず出現率の一番低いd, e で木を作ります。

     0.20
   /0     \1
d(0.15) e(0.05)

テキストなので少しわかりづらいですが、dとeで接点を作りそれぞれ0, 1のラベルをつけています。 また2つの出現率の合計を接点に設定し、これを新たな葉として考えます。

記号 出現率
a 0.44
d,e 0.20
b 0.19
c 0.17

新たな出現表はこのようになります。 これを元にまた木を作っていきます。 今度は出現率の一番少ないb, cです。

     0.36            0.20
   /0     \1       /0     \1
b(0.19) c(0.17) d(0.15) e(0.05)

以下同じように繰り返していくと、次のようなハフマン木が出来上がります。

        1.00
      /0     \1
a(0.44)      0.56
        /0          \1
     0.36           0.20
    /0   \1        /0   \1
b(0.19) c(0.17) d(0.15) e(0.05)

ハフマン木ができたら、枝を辿ってラベルにつけられた符号を割り当てればハフマン符号のできあがりです。

記号 符号
a 0
b 100
c 101
d 110
e 111

この符号が語頭条件を満たしていて、瞬時復号可能であることが確認できると思います。 また一意復号可能で、他の符号とも被っていません。 出現率の多いaという記号に短い符号が割り当てられていて、出現率の低い記号には長い記号が割り当てられています。

実際にこのハフマン符号の平均符号長を計算してみましょう。

1*0.44 + 3*0.19 + 3*0.17 + 3*0.15 + 3*0.05 = 2.21

平均符号長は2.21ビットとなり、アスキーコードの7ビットよりかなり短くなっていることがわかります。 まあ、これはかなり極端な例ですが、一般的にはデータの出現率には偏りがあるので、ハフマン符号で符号化したデータは元のデータよりも小さくなります。 データの出現率の偏りが大きければ大きいほど圧縮率は上がります。

ハフマン符号のメリット

ハフマン符号には次のようなメリットがあります。

  • 汎用的
    • 出現率に偏りのあるデータを圧縮できる
    • つまりほとんどのデータ
  • パテントフリー
    • 訴えられる心配がない
  • 復号が速い
    • 一致する符号を先頭から順番に復号するだけで良い(瞬時復号可能)

圧縮率は中程度です。 他にも効率のよい圧縮方法があります。

ハフマン符号のデメリット

逆に次のようなデメリットもあります。

  • データの走査が2回必要
    • データの出現率の調査で1回
    • 符号化で1回
    • なので圧縮速度はそこまで速くはない

データを2回走査しないといけないのは大きなデメリットです。 例えばストリーム型のデータをリアルタイムで圧縮しながら転送するような用途には、ハフマン符号は向いていません。

このデータ走査を2回しないといけないというハフマン符号のデメリットを補うアルゴリズムも考案されていて、動的ハフマン符号というものがあります。 動的ハフマン符号は、データを読み込みながらハフマン木を生成していくので、2回読み込む必要がありません。

動的ハフマン符号

適応型ハフマン符号とも呼ばれます。 こちらが動的ハフマンと呼ばれるので、元々のハフマン符号を対比して静的ハフマン符号と呼んだりします。

動的ハフマン符号ではデータを読み込むたびにハフマン木を更新します。 そのため、静的ハフマン符号であったデータを2回読まないといけないというデメリットを克服しています。

静的ハフマンと違って最初に出現頻度の統計をとらないので、最小符号とはなりませんが、そんなに圧縮率は悪くなったりはしません。

副次的な作用としては、データの読み込みとハフマン木の更新を同時に行うので、符号表を持たなくてもすむようになります。 (静的ハフマンは符号化したデータとは別に符号表を保つ必要があった)

例: 動的ハフマン

aabcbbというデータを動的ハフマンで符号化してみます。

まずaというデータを読み込んでハフマン木を作成し、符号0を出力します。 この時ハフマン木には初めて登場した記号なので、それを示すための記号aも出力します。

  /0
a(1)

0a

次の記号のaを読み込みます。 aはすでに符号が割り当てられているので、符号0のみを出力します。 aはこれで2回目の登場なので、出てきた回数を2に更新します。

  /0
a(2)

0a0

次にbを読み込みます。 bは新しく登場した記号なので、ハフマン木の枝葉を増やし符号1を割り当てます。 割り当てられた符号1を出力し、新しく登場した記号なので、それを示すために記号bも出力します。

  /0  \1
a(2) b(1)

0a01b

次にcを読み込みます。 ここでaとbを比べると、bの方が出現回数が少ないので、bの方を伸ばして新たな符号を割り当てます。 枝を伸ばしたことで、bには新たに10という符号が割り当てられ、cには11が割り当てられました。 割り当てられた符号11を出力し、新しい記号cを出力します。

 /0   \1
a(2)
     /0  \1
    b(1)  c(1)

0a01b11c

上記のように処理を繰り返していくと最終的には次のようなハフマン木を出力結果が得られます。

aabcbb(6Byte,48bit)

 /0   \1
a(2)[f:id:masatobito:20160229164431j:plain]
     /0  \1
    b(3)  c(1)

0a01b11c1010(33bit)

元のデータは48ビットでしたが、33ビットに圧縮されました。 最終的なハフマン木を見てみると、aよりもbの方が出現回数が多いにもかかわらず、aの方に短い符号が割り当てられています。 このように動的ハフマン符号では、平均符号長を最小にすることはできませんが、実用には遜色ない圧縮率を出すことができます。

まとめ

UUUM攻殻機動隊は毎月肉(29)の日は、バルバッコアで昼バッコアしてます。

f:id:masatobito:20160229164431j:plain

www.wantedly.com