Topcoder marathon match SFFCompression

題材が面白そうだったので、久々にマラソンに参加してみた。それなりにマジメにやったけど11位。個人的には ambrose というのに勝ったので良し。

http://community.topcoder.com/longcontest/stats/?module=ViewOverview&rd=15023

たぶん、 DNA のシーケンサが読んだ情報を保存するファイルフォーマットのファイルがあって、それをなるだけ圧縮しろ、ただし遅いとペナルティ、って話だった。入ってる情報は DNA の配列がたくさん (50k個とかくらい) 、って感じ。具体的には、

一本の DNA ごとに実験番号やら、なんやらのヘッダ。あまり大きくない
bases とか言われる、 TCAGTTACGCTT... みたいなやつ。 DNA 内の塩基配列ってやつかな。これのサイズを NB とする
NF > NB な flowgram とか言われる数字の列。
NF と NB の対応を取るための、 flow_index と呼ばれる物体。 NB 個ある。
一個一個の base ごとに quality って値が入っている。 NB 個ある。

あんまこのフォーマットについて…とかぐぐっても今一つよくわからなかったので、基本的に数秘術的にカンでそれぞれの値の意味を想像していった感じだった。結果としてわかったのは、

base は自明だけど1個保存するのに 2bit しかいらない。 range coder や lz な圧縮するとやや小さくなるけど、速度的に元が取れないのでやめた。

flowgram 一個一個に特定の配列 TGAGCATCGA... みたいなのが固定で割り当てられてて、値が大きい部分が base としてあらわれる。数値が 50 から 150 なら1個、 150 から 250 なら 2個、という具合に。例えば配列 TGAG に対して 130, 20, 90, 211 とかだと、 T が1個あって、 20 は小さいから G はなくて、次の A が1個あって、次の G は2個あって、という具合なので、 base は TAGG とかになる。

というような感じなので、 flowgram の値が 0-50 であるか、 50-150 であるか、 150-250 であるか…みたいなのは、 base からわかるので、その部分は保存しなくていい。

flow_index はえらい base と相関の高いデータだなぁと思ってたけど、 flowgram と base の位置を関連づけるものなので、上記の特定の配列がわかれば base から演繹できるので保存する必要なし。

quality は後ろの値に近い値が出やすい。 8bit のデータなので、後ろの値ごとに range coder を準備する感じで圧縮した。連続してる時はさらに連続する傾向があるみたいだったので、後ろ2つが同じだった場合はまた別の range coder 作る感じにした。

flowgram の細かい部分は、前の quality とやや相関があるみたいだったので、 quality のおおざっぱな値ごとに range coder を作った。

エントロピー符号は、最初は huffman 使ってたんだけど、 range coder の方が少しだけ小さくなって、かつある程度速くしたら huffman とそんなに変わらなかったので、 range coder にした。上位の方の人は速くしたら huffman の方がいいって言ってるんで、 huffman 側をあんま高速化しなかったせいかな…と思う。実際上位の人達より遅いみたいだ。

フォーラムを見た感じ、一番大きい敗因は quality の値をエンコードする時に flowgram の値をコンテキストとして使わなかったことなのかな、と思った。

あとは base の最初が削れる(これは当然気付いてたけど順位変えるくらいデカいわけじゃないのでやらなかった)のと、あと最後の方もなんか削れたらしいぽいのがわかってなかった。それとヘッダは明らかにもうちょい削れたけど、これも見積った感じあんま順位に関係ないのでやらなかった。

最後の方は quality か flowgram のどっちかが削れるんだろうなーと思って、いろいろと試したもののあんまりうまくいかなくて、ひょっとして LZ とか遅いけど案外小さくなるのかなーと試してみて全然ダメだと確認したところで諦めた感じだった。

今回途中経過のスコアとかを google docs で管理してみた。まあ役に立った気がする。別に面白くないけど、 submission 11 から 13 の間で flow_index 全く保存する必要ないことに気付いたんだなぁ…とか。

https://docs.google.com/spreadsheet/ccc?key=0AolcvzoWgN21dHA3LVhodjhra3hWaXBqeXdqTC1VZlE

正直最近マラソン飽きまくってて、どの問題見てもやる気が微塵も起きなくなってきていたんだけど、今回はかなり楽しかった。

あ、 range coder についてはこの記事

http://codezine.jp/article/detail/443

LZ と圧縮全般については、このサイト

http://www.geocities.jp/m_hiroi/light/index.html#python_algo

をそれぞれかなり参考にさせてもらいました。ありがたかった。

range coder は今まで「なんか小難しそうな物体」ってイメージで、たぶん原理は聞いたこともあった気がするんだけど全く覚えてなかった。でも今回で割と簡単で良いものだと学べたのは良かったと思う。