📘

鳩の巣原理と圧縮

2021/04/30に公開

鳩の巣原理というprincipleがあります。

If m objects are placed into n bins, where m > n, then some bin contains at least two objects.

簡単にいうと、「ハトが５羽いて、鳩の巣が４箱しかない場合、ハトが2羽以上となる鳩の巣が少なくとも1つある」というものです。

明らかに思えるこのprincipleですが、どのハトが一緒の箱になるかという情報はありませんが、「ハトが2羽以上となる鳩の巣が少なくとも1つある」 という主張ができます。

ハト以外では、例えば東京都には同じ髪の毛の本数を持つ人が少なくとも2人以上いるなどがいえます。

成人日本人の毛髪の平均は約１０万本、東京都の人口1000万人と想定するとき、東京都の人口 >> 日本人の毛髪の本数のパターンであり、これは、東京都の人口 = ハト、日本人の毛髪の本数のパターン = 鳩の巣とすると鳩の巣原理により、証明されます。

さて、この話ですが、計算機科学においては圧縮の話でもでできます。

コンピューターのなかではあらゆるデータは0と１の並びで表現されます。

もちろんデータの実体である、0,1の並びは、そのままでもいいのですが、データの転送時や保存時の理想的には、この並びが少しでも短い方がいいです。その方が容量や帯域を節約できるからです。

実社会で運用されている情報のほとんどのものには、冗長な部分があります。たとえば、英語であればandやtheなどは繰り返し出てきますし、空の画像であれば雲が描画された部分は同じRGB表現の白がみられるでしょう。

それらの事情から、データを圧縮するというアイデアはとても自然なものです。

たとえば、圧縮前のデータの長さ（=大きさ）をN、圧縮後のデータの長さをN-1とします。これは圧縮するとデータの長さが短くなるので当然です。

圧縮前のデータでは、0と１の数字の並びがN個続くので、2^N種類のデータが考えられます。圧縮後のデータでは2^{N-1}となります。

ここで鳩の巣原理の文脈で

と考えられることができます。

「ハトが5羽いて、鳩の巣が4箱しかない場合、ハトが2羽以上となる鳩の巣が少なくとも1つある」

これを言い換えてみましょう。

「圧縮前のデータがNパターンあって、圧縮後のデータがN-1パターンしかない場合、圧縮前のデータが2個以上となる圧縮後のデータが少なくとも1つある」

圧縮をすると、異なる圧縮前データから同一の圧縮後のデータが生成されるということがわかりました。これは圧縮後データからは追跡できない圧縮前データがあるということです。

圧縮後のデータから圧縮前のデータを完全に復元できることを可逆圧縮（lossless data compression）と呼びます。

実際には可逆圧縮（=圧縮後データを圧縮前に復元できること）と呼ばれる技術が存在しますが、全てのデータを元のデータより小さくするという方式を実現している方法はありません。それは鳩の巣原理により不可能だからです。

この辺の話はwikiに書いてます。

また、可逆圧縮アルゴリズムは、データを可逆な形式でより小さなデータサイズに変換するアルゴリズムとして知られているが、鳩の巣原理を用いれば、データ長Lのデータすべてを、データ長L-1以下となるデータに変換可能な可逆圧縮アルゴリズムは存在しないことが証明できる。

参考