SFF Compression 纪念第一次TC Marathon

第一次做TC Marathon,基本上可以说是与$擦肩而过,可能是500$或者1000$,有点遗憾。我的算法在Coding Phase可以达到第五名,刚好有$的名次,最终测试掉到了第七名,很杯具。差不多有一半人都挂在了97.sff这个测试文件上,貌似是因为出现了example中没有的情况,于是就0分了(后来下载到数据发现Global Header中的key length是5,但之前所有example都是4)。这个实在太坑爹了。其实算法稍微差一些(最终的第五名其实压缩成绩一般的,但是没挂数据)最后也能进前五的。搞的世界观都改变了……看来应该求稳,不是一直改进就可以的。结果因为那组数据另外还有点其他的问题,管理员删除了,所以杯具消失,又回到了第五名,刚好有$,很圆满,估计不会再改名次了吧。
题目在此
http://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=15023&pm=11734
大致是说有一类文件希望能又快又高效的压缩。文件是一类和DNA测序有关的文件,文件说明在此
http://www.topcoder.com/contest/problem/SFFCompression/sff.html
主要策略是利用文件特征。由于文件中Read Header和Read Data都出现过很多次,因此压缩他们是最重要的。这里主要说我压缩Read Data的策略。

Continue reading »