はじめに なぜ圧縮? いつの時代も CPU は I/O より速い 圧縮の種類 可逆(無歪) lossless 非可逆(不可逆)lossy 一番簡単な圧縮 Run-length coding(連長符号化) あああああいいい → あ5い3 ZeoSync事件 [2002-01-07] ZeoSync Corporation が 1/100 に可逆圧縮する技術を発明したと発表 [2002-03-07] 特許公開 任意の n ビットのファイルを n - 1 ビット以下に可逆に圧縮するアルゴリズムは存在しない。 [証明] n ビットのファイルは 2n 通り存在するが,n - 1 ビット以下のファイルは 1 + 2 + 22 + 23 + …… + 2n-1 = 2n - 1 通りしか存在しない。 もっとちゃんとした圧縮限界はエントロピー - Σ pi log2 pi で与えられる(→ Shannon