ZIP圧縮し辛いファイルを求めて

CS

ちなみに16進Champernowne定数では駄目だった．ZIP圧縮できてしまった．考えてみれば例えば "123" という文字列が "123", "1123", "2123", ... "10123", ... という具合に無限回出現するから，そこが圧縮できてしまうのかな．
次はとりあえず円周率10000桁とかどっかから拾ってきて試してみよう．（多分，乱数列でいいんだろうけど
ちなみにヘッダ長が固定らしく（？）十分に短い（数bytesの）ファイルでも圧縮結果は一律に150 bytesを超えてしまうが，そういうのはちょっとね．

上のページのLZ77アルゴリズム解説によれば "sliding window" の幅が32,768 = 2^15であり，つまり2^15文字より離れた重複パターンのペアを探すことはしないらしい．文字すなわち1 byteのデータには2^8 = 256通りあるので，2文字の文字列を全通り作って並べれば2*(2^8)^2 = 2^17 = 131072文字の文字列ができて "window" を十分埋め尽くせる．重複パターンとしては3文字以上のみを探すのでその中に一対の重複パターンも存在しない．つまりLZ77では圧縮できない．
次のHuffman符号化だが，何をアルファベットとするのかまだ理解できない．今日はここまでだな．でも16進Champernowne定数でいいと思うんだけどなぁ... いや，2^15までカウントしたらまた0に戻ればいいのか？（ついでに桁も固定で

nodakai@co:~$ i=16; while [ $i -lt 10000000 ]; do ruby -e "$i.times{|i| printf('%x',i)}" | xxd -r -p > ch$i.dat; i=$((i*16)); done
nodakai@co:~$ i=16; while [ $i -lt 10000000 ]; do zip ch$i.zip ch$i.dat; i=$((i*16)); done
  adding: ch16.dat (stored 0%)
  adding: ch256.dat (stored 0%)
  adding: ch4096.dat (deflated 1%)
  adding: ch65536.dat (deflated 5%)
  adding: ch1048576.dat (deflated 14%)
nodakai@co:~$ ll -rS ch*
-rw-r--r-- 1 nodakai nodakai       8 2008-01-28 01:11 ch16.dat
-rw-r--r-- 1 nodakai nodakai     156 2008-01-28 01:11 ch16.zip
-rw-r--r-- 1 nodakai nodakai     248 2008-01-28 01:11 ch256.dat
-rw-r--r-- 1 nodakai nodakai     398 2008-01-28 01:11 ch256.zip
-rw-r--r-- 1 nodakai nodakai    6008 2008-01-28 01:11 ch4096.dat
-rw-r--r-- 1 nodakai nodakai    6118 2008-01-28 01:11 ch4096.zip
-rw-r--r-- 1 nodakai nodakai  122979 2008-01-28 01:11 ch65536.zip
-rw-r--r-- 1 nodakai nodakai  128888 2008-01-28 01:11 ch65536.dat
-rw-r--r-- 1 nodakai nodakai 2231232 2008-01-28 01:11 ch1048576.zip
-rw-r--r-- 1 nodakai nodakai 2586488 2008-01-28 01:11 ch1048576.dat
nodakai@co:~$ xxd ch256.dat 
0000000: 0123 4567 89ab cdef 1011 1213 1415 1617  .#Eg............
0000010: 1819 1a1b 1c1d 1e1f 2021 2223 2425 2627  ........ !"#$%&'
0000020: 2829 2a2b 2c2d 2e2f 3031 3233 3435 3637  ()*+,-./01234567
0000030: 3839 3a3b 3c3d 3e3f 4041 4243 4445 4647  89:;<=>?@ABCDEFG
0000040: 4849 4a4b 4c4d 4e4f 5051 5253 5455 5657  HIJKLMNOPQRSTUVW
0000050: 5859 5a5b 5c5d 5e5f 6061 6263 6465 6667  XYZ[\]^_`abcdefg
0000060: 6869 6a6b 6c6d 6e6f 7071 7273 7475 7677  hijklmnopqrstuvw
0000070: 7879 7a7b 7c7d 7e7f 8081 8283 8485 8687  xyz{|}~.........
0000080: 8889 8a8b 8c8d 8e8f 9091 9293 9495 9697  ................
0000090: 9899 9a9b 9c9d 9e9f a0a1 a2a3 a4a5 a6a7  ................
00000a0: a8a9 aaab acad aeaf b0b1 b2b3 b4b5 b6b7  ................
00000b0: b8b9 babb bcbd bebf c0c1 c2c3 c4c5 c6c7  ................
00000c0: c8c9 cacb cccd cecf d0d1 d2d3 d4d5 d6d7  ................
00000d0: d8d9 dadb dcdd dedf e0e1 e2e3 e4e5 e6e7  ................
00000e0: e8e9 eaeb eced eeef f0f1 f2f3 f4f5 f6f7  ................
00000f0: f8f9 fafb fcfd feff                      ........