高効率のデータ圧縮−ハフマン符号化（388号）

一回間を置きましたが、データ圧縮の技法についてのお話を続けます。

最初に書いておきますが、今回お話するハフマン符号化（ハフマン法）は現在でも様々なシーンで利用されている現役のデータ圧縮技術でして、その仕組みはかなりわかりにくいものです。

今回の内容がわからなかったとしても気にしないでください。
「データ圧縮ってなんか複雑なことやってるんだな」程度でも十分かと思います。


1. ハフマン符号化

ハフマン（haffman）符号化のハフマンはこの手法を考案したデビッド＝ハフマンという人の名前から取っています。
1952年だそうですから、もう70年も昔の話です。

前回にモールス信号のお話とパターン辞書のお話をしました。
最適な構成のパターン辞書を作れば、データ量をグンと小さくすることができます。

このパターン辞書の作り方を工夫して、それによってデータ部を小さくすることでさらなるデータ圧縮を目指そうというのがハフマン符号化の考え方です。

ところで、ハフマン符号化の理解が難しい理由の一つが2進数の理解が前提である点です。

「がんばりすぎないセキュリティ」としては、2進数の理解を前提にするわけには参りません。

というわけで、この記事では、10進数をベースに書いています。
そのため、一般的なハフマン符号とはかなり違った部分があります。
が、本質は同じです。この記事を読んで興味を持った方は次は是非2進数ベースでの解説に挑戦してください。


2. パターンが増えると圧縮が困難に

パターン辞書を説明した時に、次のような例を挙げました。

パターンＡ：　ABC-ABC-ABC-ABC-ABC-（ABC-を5回繰り返し）
圧縮データ：
　（辞書部）1:ABC-
　（データ部）11111

パターンＡは同じデータの繰り返しですから、かなり効率良く圧縮ができます。
元データが20文字なのに対して、圧縮データは辞書部で6文字＋データ部が5文字の計11文字です。

ですが、パターンが増えるとかなり雲行きが怪しくなってきます。

パターンＢ：　AAAABAAAACAAAADAAAAEAAAAFAAAAGAAAAHAAAAIAAAAJ
圧縮データ：
　（辞書部）1:AAAA,2:B,3:C,4:D,5:E,6:F,7:H,8:I,9:J
　（データ部）1213141516171819

似たようなパターンなのに、めちゃくちゃ圧縮率が悪いです。
元データが45文字なのに、圧縮データは辞書部が38文字＋データ部が16文字の計54文字になってしまいます。

この時点で既に圧縮失敗なのですが、ちょっとそこは置いておいて、さらにパターンが増えたケースを見てみます。
こちらはもっと悲しい結果になります。

パターンＣ：　AAAABAAAACAAAADAAAAEAAAAFAAAAGAAAAHAAAAIAAAAJAAAAK
圧縮データ：
　（辞書部）01:AAAA,02:B,03:C,04:D,05:E,06:F,07:H,08:I,09:J,10:K
　（データ部）010201030104010501060107010801090110

元データにAAAAKというパターンを加えただけで、辞書部もデータ部もガクンと増えてしまっています。
元データの50文字に対して、辞書部だけで52文字、データ部も倍以上の36文字、合わせると88文字という膨らみ方です。
もはや圧縮どころの話ではありません。

さて、パターンＢとパターンＣの圧縮結果を比較していただくとわかるのですが、大巾に増えた理由は明らかですよね。
辞書部のパターンが10種類を越えてしまったからです。
10種類を越えてしまったので、データ部を全て2ケタで書かなくてはならなくなりました。

こんなのどうしようもないですよね。


3. よく使うデータは短かくしたい！

いや、それならパターン辞書の番号を数字だけじゃなくてアルファベットも使おう！という考え方も可能です。それなら26種類（大文字＋小文字＋数字なら62パターン）までいけます。が、それとても上限があるのはいっしょです。
それこそ、何メガバイト、何ギガバイトといった巨大なデータを圧縮する時にはパターンが数十で収まるはずがないのですから。

とはいっても、パターンＣの圧縮結果はちょっとひどいですよね。
再掲します。

パターンＣ：　AAAABAAAACAAAADAAAAEAAAAFAAAAGAAAAHAAAAIAAAAJAAAAK
圧縮データ：
　（辞書部）01:AAAA,02:B,03:C,04:D,05:E,06:F,07:H,08:I,09:J,10:K
　（データ部）010201030104010501060107010801090110

データ部なんて、無駄としか思えない0の羅列です。
よく見ると、010というパターンが8回も出ています。
せめてこれだけでも何とかならないのでしょうか？

これ、ちょっとした工夫で減らせます。

パターンＣ２：　AAAABAAAACAAAADAAAAEAAAAFAAAAGAAAAHAAAAIAAAAJAAAAK
圧縮データ：
　（辞書部）0:AAAA,11:B,12:C,13:D,14:E,15:F,16:H,17:I,18:J,19:K
　（データ部）011012013014015016017018019

頻繁に登場するAAAAのパターン番号だけを1ケタにしました。
これだと、辞書部が1文字、データ部が10文字も小さくなります。（それでも元データより大きいので、圧縮失敗である事実は変わりませんが、ここでは短かくできたことに着目です）

要は、一番登場するパターンを短かい値にして、登場回数の少ないパターンには長い値を割り当てれば良いのです。

これって、モールス信号の一番短かいパターンにＥを割り当てた考え方とそっくりですよね。


4. でも混同しないの？

同時にモールス信号では信号の混同を防ぐため、文字と文字の間には小休止という休止符を置くことになっていました。
でないと、信号の区別ができなくなるからです。

モールス信号では、Eには「・」が、Iには「・・」が、Sには「・・・」が割り当てられています。

ここに「・・・」というパターンが来たとしましょう。
それが、小休止なしの連続ならSですし、「・（休）・・」のように途中に小休止があれば、EとIの意味だとわかります

上記のパターンC2の場合、データ部に小休止はありません。にも関わらず混同しない仕掛けが施されています。

再掲します。

パターンＣ２：　AAAABAAAACAAAADAAAAEAAAAFAAAAGAAAAHAAAAIAAAAJAAAAK
圧縮データ：
　（辞書部）0:AAAA,11:B,12:C,13:D,14:E,15:F,16:H,17:I,18:J,19:K
　（データ部）011012013014015016017018019

辞書部をよく見ると、最初のAAAAしか"0"という文字を使っていません。
つまり、一番短かい0という文字はAAAA専用にしていて、他のパターンには割り当てていないのです。

これなら、小休止がなくてもパターンの混同が起きません。

なお、0は最も頻繁に出てくるパターン用ですが、次に頻繁に出てくる値には11〜99（0を使わない2ケタの値）が、その次は222〜999（0と1を使わない3ケタの値）が、といった具合で桁数を増やすことができますので、辞書部が膨大となってもよく使うパターンにはより短かい値を割り当てることができるのです。

この考え方こそがハフマン符号化と呼ばれる方式です。

なお、ここでは10進数で解説しましたが、本来のハフマン符号化はこれを2進数で考えます。この場合、10進数よりもずっと圧縮率を上げることができます。


5. （余談）パターンＣは結局圧縮できないの？

ここまでの解説では結局、パターンＣは圧縮失敗のままです。
これでは、あんまりですので、もう少し実際的な圧縮結果を出しておきます。

パターンＣ３：　AAAABAAAACAAAADAAAAEAAAAFAAAAGAAAAHAAAAIAAAAJAAAAK
圧縮データ：
　（辞書部）AAAA,B,C,D,E,F,H,I,J,K
　（データ部）011012013014015016017018019

データ部は変わっていませんが、辞書部がひどく素っ気ないものになっています。
これは、ハフマン符号に基づけば辞書部の最初の項目は0、次は11、12となると決まりきっていて、省略してもどの値用のパターンかが自明だからです。
こうすれば、辞書部は22文字、データ部が27文字で合計47文字まで圧縮できます。
ほんの少しですが、元データの50文字よりは小さくなりますね。

符号化を2進数で行う前提にすれば、データ部は63ビットですので、約8文字分です。辞書部の22文字と合わせると30文字となり、ある程度圧縮できたと言えそうです。

実際の圧縮ソフトでは、辞書部も2進数で計算します。ですので、上の例であれば、もっと小さくできます。（計算してませんが、おそらくは20文字程度にはなりそう）


6. まとめ

今回はハフマン符号化というデータ圧縮方式についてお話をしました。

ハフマン符号は現代の多くの圧縮アルゴリズムで採用されています。
デビッド＝ハフマンが考案したハフマン符号化（静的ハフマン符号）を巨大なデータに適用すると最も圧縮できるパターンを見つけるのに膨大な時間がかかります。
その代わり、静的ハフマン法は最も圧縮度が高い方式と言われています。

ただ、静的ハフマン符号化はあまりに時間がかかりすぎるため、ソコソコで妥協する方式がいろいろと考案されています。これは動的ハフマン法と呼ばれています。

皆さんもおなじみのZIP形式（元はPKZIPという製品）、日本で作られたLZH形式、UNIX（Linux）で利用されるgzip形式などはいずれも動的ハフマン法を採用したデータ圧縮ソフトです。

次回もお楽しみに。


（この記事は2025年1月に執筆しました）