ICFP2007 (13) gene tableのpage 15

ICFP2007 (12) 修復済みgene tableの続きです。

怪しいものを見つけました。gene tableは1/14～14/14です。helpScreenを42にして、ページ番号をAAA_geneTablePageNrに設定すると表示されます。試しに15ページ目を表示してみたところ、右下に今までなかった小さな絵が表示されています。鯨の噴水のさかさまっぽいです。こんな所にまで隠されているんですね。



この絵を表示するRNAはDNA上では圧縮されています。圧縮は20種類あるRNAに0～19の番号をつけて、ひたすら番号を並べています。20が終わりのマークになっています。圧縮しないときのRNAは7文字なのが、圧縮したときは最短が1 (0はP一文字) 最長が6 (19はCIICCP)になります。出現頻度の高い順に番号をつけているっぽいです。圧縮したRNAは、展開するコードと符号表と一緒にDNAの中に埋め込まれています。page 123456のRNA Compression(ICFP 2007(4))とpage 1024のCompressor(ICFP20007(5))に書かれている話です。Compressor自体は自己書き換えしまくりで命令の内部まで書き換えているので、やたら読みずらいコードでした。

printGeneTableに含まれているcompressorは50528バイトで23103個のRNAを表現しています。RNAは1個あたり7文字ですが、DNAに埋め込むときはRNA出力コマンドのIIIに連結してやらないといけないので10バイト必要です。結局231030バイトが50528バイトになったということで、1RNAあたり2.18文字、つまり21.8%に圧縮したことになります。ただしcompressor自身のサイズはテーブルも含めて1028バイトあります。compressorのサイズも含めて考えると51556バイトなので圧縮率は22.3%と多少効率が落ちます。

圧縮ということで思ったのは、prefixとかも既存の部分列の並びみたいな感じで圧縮可能な気がします。