コラム
2025/03/31
第103回 プログラミングについて『ファイルを圧縮してみよう！ その2』
ファイルを圧縮といえば、ＵＮＩＸでは pack や compress、ＤＯＳではフリーソフトの lha 、zip などがあり、多分このどれかを一度は使った経験があると思います。これらのソフトは圧縮したファイルを再び伸長すると完全に元のファイルが再現できる機能を持っています。
これに対し、画像を圧縮するソフトは必ずしもそうではありません。というのも画像は少しくらいいい加減なデータであっても人間の目というものはそれほど高機能ではないので（決して低機能という意味ではありません）、品質を少し下げてでも圧縮率を上げる方を優先しているからなのです。
今回は、圧縮したファイルを完全に伸長できるアルゴリズムについて考えてみます。
ＵＮＩＸには pack と compress という２つの圧縮プログラムがあります。この２つは圧縮に使用しているアルゴリズムが全く異なっています。pack はハフマン法、compressはＬＺ法という聞き慣れないアルゴリズムを使用しています。lha はＬＺ法とハフマン法の両方を使っており（多分ＬＺ法とＨｕｆｆｍａｎ法のＡｒｃｈｉｖｅｒということでＬＺＡと命名したのだと思います。）、zip も同様だと思います。
以前こんなことがありました。まだ私が前の会社で働いていた頃のことです。私のいた工場から別の製造工場にデータを転送するということをやったことがあります。今から１５年ぐらい前のことだったと思います。
その頃はあまり難しいことも知らなかったので、単純にコンピュータとコンピュータをＲＳ－２３２Ｃからモデムで接続して一般の電話回線でデータを転送しようということになりました。物理的に接続した後、転送側も受信側も copy コマンドを使うことで単純に実現しようとしたのですが、どうしてもうまく行きません。ある程度は転送できるのですがデータが完全に転送できず、使い物にならないのです。色々と調べてみると、９６００ボーという転送速度が原因だったようです。９６００ボーというと通常ホストコンピュータと端末間の転送速度で高速（今となってはそうでもありませんが）にデータを交換するときに使用するボーレートなのです。
そこで順次ボーレートを下げていき、６００ボーではまず間違いなく転送でき、１２００ボーでは若干の不安が残る程度ということが分かりました。必ずしも完璧ではないので転送ソフトと受信ソフトを作成し、受け取ったデータが正しいのかを送信側にエコーバックするという方法で常に正確に転送できるようになりました。
ところが、６００ボー程度では転送にかかる時間が数十分単位となってしまいいらいらして終了するのを待たなければなりません。そこで転送するデータを少なくしようと
データの圧縮を行なったのです。
そのときに私が圧縮に使ったアルゴリズムは特に有名なものではなく、自分で考えたものでした。転送するデータの内容が、
abcde 1 fghijkl 2 mnopq 3 rstuvwxyz
abcde 1 fghijkl 2 mnopq 4 rstuvwxyz
abcde 2 fghijkl 3 mnopq 4 rstuvwxyz
abcde 2 fghijkl 3 mnopq 5 rstuvwxyz
abcde 3 fghijkl 4 mnopq 4 rstuvwxyz
といった感じのもので、それぞれの行の一部分だけに差異があるものでした。そこで、最初の行はそのままとして、２行目以降は前の行と同じ部分の情報と違う部分の情報
にすることにしました。だいたい次のような感じです。
d35,abcde 1 fghijkl 2 mnopq 3 rstuvwxyz
s24,d1,4s10
s6,d1,2s9,d1,3s18
s24,d1,5s18
s6,d1,3s9,d1,4s6,d1,4s18
この形式は d の後に前の行との違う桁数（コンマで桁数が終了）、コンマの後に文字列が続きます。s の後には前の行と同じ部分の桁数（コンマで桁数が終了）という単純な
形式です。この約束事で元のデータに戻してみて下さい。
このようなデータの場合には有効ではありますが、汎用的には役には立たないでしょう。
そこで一般的なアルゴリズムの中からハフマン法を考えてみましょう。ハフマン法とはその名の如くハフマンおじさんが４０年程昔に考えたアルゴリズムで、文字の出現頻
度を利用した圧縮アルゴリズムです。
いまファイル内のデータが、
ABCDEABABBCBCb
だったとします。このデータの場合、それぞれの文字の数は、
B 5個
A 3個
C 3個
D 1個
E 1個
となっていますので、出現回数の多い文字を少ないビットで、少ない文字を多いビットで表せば圧縮される可能性があります。
（ここからしばらくは私が勝手に考えてうまくいかなかった方法です。）
そこで、各文字を次のようなビットで表現しようと考えました。
B 1
A 01
C 001
D 0001
E 00001
圧縮したファイルには０の個数に対応した文字のテーブルを書き込んでおき、伸長するときにはビットを順番に読んでいき、０の個数でテーブルのインデックス番号を決定することができるはずです。このデータの場合、ビット列の最長のものでも５ビットしか使わないので確実に圧縮できるはずです。
ところがこのアルゴリズムを使用したプログラムを作って実際に試してみると、予想とは全然違ってしまいました。圧縮されるファイルもあれば、逆に大きくなってしまうものもあるのです。
原因は次のようなことでした。
当然のことですが、文字は全部で２５６種類あり、頻度の一番大きい文字が１ビットと次のものが２ビットと少ないビット数で表現できるのですが、頻度が９番目以降は９ビット以上使用し、最も頻度の少ない文字は２５６ビット使用することになります。ですので文字の種類が多くあまり頻度の差がないデータでは逆に大きくなってしまったという訳です。
多分ハフマンおじさんも同じことをやって頭を悩ましたはずです。ここからが私とこのおじさんの違いなのでしょうね。ハフマンおじさんは上の様に単純に表現するのでは
なく別の方法を考えたのです。
ここで２分木のツリーを思い出して下さい。（ここは私の憶測です。）
Ａ
┌─┴─┐
Ｂ Ｃ
┌┴┐ ┌┴┐
Ｄ Ｅ Ｆ Ｇ
理想的な２分木とはこの図のように左右のバランスがとれているもので、このときに検索の効率が最大になります。２５６種類のデータを検索するときには最大でも８回で済
んでしまいます。次にバランスの悪い２分木を見てみると、
Ａ
┌─┴─┐
Ｂ Ｃ
┌┴┐
Ｆ Ｇ
┌┴┐
Ｄ Ｅ
Ｂは２回の比較で発見できますが、ＤやＥは４回の比較が必要になります。ところがこれを逆に考えるとＢを発見するための比較の回数がＤやＥよりも少ないということは、
このようなバランスの悪い２分木を利用すると頻度の大きい文字をツリーの浅いところに、そうでないものを深いところに配置するとファイルを圧縮できる可能性があるとい
うことです。多分ハフマンおじさんはこう考えたのだと思います。
再び
ABCDEABABBCBC
5 B
3 A
3 C
1 D
1 E
の文字列の頻度に戻りましょう。ハフマンおじさんはこのようなバランスの悪い木を作るのに、次のように考えました。
もっとも頻度の低いもの２つを選んで木を作り、その２つの頻度の合計を木の頻度とし、どんどん木を成長させていく。
その考えどおりに木を作ってみると、最初は頻度１どうしの D と E で１つの木が出来上がります。
5 B
3 A
3 C
┌ 1 D
2┤
└ 1 E
次に今作った木の頻度が 2 で最少、次に小さいのが A か C ですので、ここでは C と木を作ります。
5 B
3 A
┌3 C
5┤
│ ┌ 1 D
└2┤
└ 1 E
これを繰返して、
┌5 B
8┤
└3 A
┌3 C
5┤
│ ┌ 1 D
└2┤
└ 1 E
最後に
┌B
┌┤
│└A
┤
│┌C
└┤
│┌D
└┤
└E
という木が出来上がります。この木の根から出発して B に行くには上に２回上がればいいのですから、上に行くときには１とすると、１１となります。A に行くには１０、D
は００１になります。
┌B
１│
↑│
１┌┤
↑│└A
スタート┤
↓│┌C
０└┤
│┌D
└┤
└E
この木をハフマン木というのだそうです。
では次回からは実際にハフマン法で圧縮、伸長を行なうプログラムを作ってみましょう。
これに対し、画像を圧縮するソフトは必ずしもそうではありません。というのも画像は少しくらいいい加減なデータであっても人間の目というものはそれほど高機能ではないので（決して低機能という意味ではありません）、品質を少し下げてでも圧縮率を上げる方を優先しているからなのです。
今回は、圧縮したファイルを完全に伸長できるアルゴリズムについて考えてみます。
ＵＮＩＸには pack と compress という２つの圧縮プログラムがあります。この２つは圧縮に使用しているアルゴリズムが全く異なっています。pack はハフマン法、compressはＬＺ法という聞き慣れないアルゴリズムを使用しています。lha はＬＺ法とハフマン法の両方を使っており（多分ＬＺ法とＨｕｆｆｍａｎ法のＡｒｃｈｉｖｅｒということでＬＺＡと命名したのだと思います。）、zip も同様だと思います。
以前こんなことがありました。まだ私が前の会社で働いていた頃のことです。私のいた工場から別の製造工場にデータを転送するということをやったことがあります。今から１５年ぐらい前のことだったと思います。
その頃はあまり難しいことも知らなかったので、単純にコンピュータとコンピュータをＲＳ－２３２Ｃからモデムで接続して一般の電話回線でデータを転送しようということになりました。物理的に接続した後、転送側も受信側も copy コマンドを使うことで単純に実現しようとしたのですが、どうしてもうまく行きません。ある程度は転送できるのですがデータが完全に転送できず、使い物にならないのです。色々と調べてみると、９６００ボーという転送速度が原因だったようです。９６００ボーというと通常ホストコンピュータと端末間の転送速度で高速（今となってはそうでもありませんが）にデータを交換するときに使用するボーレートなのです。
そこで順次ボーレートを下げていき、６００ボーではまず間違いなく転送でき、１２００ボーでは若干の不安が残る程度ということが分かりました。必ずしも完璧ではないので転送ソフトと受信ソフトを作成し、受け取ったデータが正しいのかを送信側にエコーバックするという方法で常に正確に転送できるようになりました。
ところが、６００ボー程度では転送にかかる時間が数十分単位となってしまいいらいらして終了するのを待たなければなりません。そこで転送するデータを少なくしようと
データの圧縮を行なったのです。
そのときに私が圧縮に使ったアルゴリズムは特に有名なものではなく、自分で考えたものでした。転送するデータの内容が、
abcde 1 fghijkl 2 mnopq 3 rstuvwxyz
abcde 1 fghijkl 2 mnopq 4 rstuvwxyz
abcde 2 fghijkl 3 mnopq 4 rstuvwxyz
abcde 2 fghijkl 3 mnopq 5 rstuvwxyz
abcde 3 fghijkl 4 mnopq 4 rstuvwxyz
といった感じのもので、それぞれの行の一部分だけに差異があるものでした。そこで、最初の行はそのままとして、２行目以降は前の行と同じ部分の情報と違う部分の情報
にすることにしました。だいたい次のような感じです。
d35,abcde 1 fghijkl 2 mnopq 3 rstuvwxyz
s24,d1,4s10
s6,d1,2s9,d1,3s18
s24,d1,5s18
s6,d1,3s9,d1,4s6,d1,4s18
この形式は d の後に前の行との違う桁数（コンマで桁数が終了）、コンマの後に文字列が続きます。s の後には前の行と同じ部分の桁数（コンマで桁数が終了）という単純な
形式です。この約束事で元のデータに戻してみて下さい。
このようなデータの場合には有効ではありますが、汎用的には役には立たないでしょう。
そこで一般的なアルゴリズムの中からハフマン法を考えてみましょう。ハフマン法とはその名の如くハフマンおじさんが４０年程昔に考えたアルゴリズムで、文字の出現頻
度を利用した圧縮アルゴリズムです。
いまファイル内のデータが、
ABCDEABABBCBCb
だったとします。このデータの場合、それぞれの文字の数は、
B 5個
A 3個
C 3個
D 1個
E 1個
となっていますので、出現回数の多い文字を少ないビットで、少ない文字を多いビットで表せば圧縮される可能性があります。
（ここからしばらくは私が勝手に考えてうまくいかなかった方法です。）
そこで、各文字を次のようなビットで表現しようと考えました。
B 1
A 01
C 001
D 0001
E 00001
圧縮したファイルには０の個数に対応した文字のテーブルを書き込んでおき、伸長するときにはビットを順番に読んでいき、０の個数でテーブルのインデックス番号を決定することができるはずです。このデータの場合、ビット列の最長のものでも５ビットしか使わないので確実に圧縮できるはずです。
ところがこのアルゴリズムを使用したプログラムを作って実際に試してみると、予想とは全然違ってしまいました。圧縮されるファイルもあれば、逆に大きくなってしまうものもあるのです。
原因は次のようなことでした。
当然のことですが、文字は全部で２５６種類あり、頻度の一番大きい文字が１ビットと次のものが２ビットと少ないビット数で表現できるのですが、頻度が９番目以降は９ビット以上使用し、最も頻度の少ない文字は２５６ビット使用することになります。ですので文字の種類が多くあまり頻度の差がないデータでは逆に大きくなってしまったという訳です。
多分ハフマンおじさんも同じことをやって頭を悩ましたはずです。ここからが私とこのおじさんの違いなのでしょうね。ハフマンおじさんは上の様に単純に表現するのでは
なく別の方法を考えたのです。
ここで２分木のツリーを思い出して下さい。（ここは私の憶測です。）
Ａ
┌─┴─┐
Ｂ Ｃ
┌┴┐ ┌┴┐
Ｄ Ｅ Ｆ Ｇ
理想的な２分木とはこの図のように左右のバランスがとれているもので、このときに検索の効率が最大になります。２５６種類のデータを検索するときには最大でも８回で済
んでしまいます。次にバランスの悪い２分木を見てみると、
Ａ
┌─┴─┐
Ｂ Ｃ
┌┴┐
Ｆ Ｇ
┌┴┐
Ｄ Ｅ
Ｂは２回の比較で発見できますが、ＤやＥは４回の比較が必要になります。ところがこれを逆に考えるとＢを発見するための比較の回数がＤやＥよりも少ないということは、
このようなバランスの悪い２分木を利用すると頻度の大きい文字をツリーの浅いところに、そうでないものを深いところに配置するとファイルを圧縮できる可能性があるとい
うことです。多分ハフマンおじさんはこう考えたのだと思います。
再び
ABCDEABABBCBC
5 B
3 A
3 C
1 D
1 E
の文字列の頻度に戻りましょう。ハフマンおじさんはこのようなバランスの悪い木を作るのに、次のように考えました。
もっとも頻度の低いもの２つを選んで木を作り、その２つの頻度の合計を木の頻度とし、どんどん木を成長させていく。
その考えどおりに木を作ってみると、最初は頻度１どうしの D と E で１つの木が出来上がります。
5 B
3 A
3 C
┌ 1 D
2┤
└ 1 E
次に今作った木の頻度が 2 で最少、次に小さいのが A か C ですので、ここでは C と木を作ります。
5 B
3 A
┌3 C
5┤
│ ┌ 1 D
└2┤
└ 1 E
これを繰返して、
┌5 B
8┤
└3 A
┌3 C
5┤
│ ┌ 1 D
└2┤
└ 1 E
最後に
┌B
┌┤
│└A
┤
│┌C
└┤
│┌D
└┤
└E
という木が出来上がります。この木の根から出発して B に行くには上に２回上がればいいのですから、上に行くときには１とすると、１１となります。A に行くには１０、D
は００１になります。
┌B
１│
↑│
１┌┤
↑│└A
スタート┤
↓│┌C
０└┤
│┌D
└┤
└E
この木をハフマン木というのだそうです。
では次回からは実際にハフマン法で圧縮、伸長を行なうプログラムを作ってみましょう。
