■圧縮の限界 [etc]

誰も書いていないな、と思ったので。

圧縮度が一番高いアプリケーションを教えてください。動画をzipで圧縮してみたら全然軽くなりませんでした。
http://q.hatena.ne.jp/1157966304

「あるアルゴリズムを適用することで、いかなるデータであってもデータサイズを減らすことができ、かつ可逆的である(元のデータに戻すことができる)」ということはありえない。言葉を換えると「そんなアルゴリズムは存在しない」。
もし存在するならば、そのアルゴリズムを繰り返し適用することで、どんなに大きなデータであっても最終的に単一の状態に集約できることになってしまう。しかし単一の状態に集約されてしまったら「元のデータに戻すことができる」はずがない。

さて、あるデータを可逆的に圧縮するとして、その限界は那辺にあるのか?
その理論的限界が「情報量」という概念であり、単位はシャノンである*1(多分)。