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的策略。
SFF文件中的Read Data部分主要压缩策略
Read Data中的Bases是可以计算出来的,Flow Index代表一种偏移,这就对应着Bases,而Flow Index也是可以用Flowgram算出来的。Flowgram落在[k*100 - 50, k*100 + 50] (k>0)区间内就对应着一个Flow Index,并且这个Flow Index后面有k-1个Flow Index是0,当然,Flowgram小于50就不对应任何Flow Index。这些都是观察出来的。起初我不存储Flow Index,觉得这样能压缩很多。后来发现其实可以存储Flow Index,然后用Flow Index推出每个Flowgram落在什么区间上。因为Flow Index有非常好的压缩策略,可以让每个值最多只占用2 bits。这是我在最后一天才发现的一个规律:Flow Index的累加对应一个位置(偏移量求和),每个位置上可以取到的Flow Index最多只有4种(其实除去开头和结尾都是刚好4种),所以只要打表记录每个位置可以是哪些Flow Index就行了。然后压缩的时候根据打的表,用至多2bit标记每个Flow Index是哪一个。存储Quality的策略是利用连续性,每个Quality的取值和前一个Quality相关,一般都变化不大,很可能相同,另外和Flow Index也有关,Flow Index是0或者不是0的时候Quality取值分布不一样。我的做法是建立2*2*Quality_Range个Huffman树,Quality_Range是Quality的范围,人工观察是在4-38之间。当推第k个Quality的时候,根据第k-1个Quality取值,第k-1个Flow Index是否是0,第k个Flow Index是否是0来决定使用那个Huffman树计算当前Quality的编码。压缩Flowgram的时候是利用Quality,因为观察到Quality高的时候Flowgram通常更接近整百。所以建立Quality_Range个Huffman树压缩<50的Flowgram,再建立Quality_Range个Huffman树压缩>50的Flowgram,根据Flowgram对应位置的Quality取值来决定使用哪个Huffman树,如果Flowgram<50不对应任何Quality则选择他之前最近的一个>50的Flowgram对应的Quality来当作这个位置的Quality(类似插值?)
关于Huffman的技巧
关于Huffman树也有一些技巧,以后可能会用到。Huffman编码要用int或者其他比较大的数据结构存,之前用char存编码,只存储1bit,这样写编码的时候会非常慢,很多10几位的编码就要操作10几次。如果用int压位的话,小于32bits的编码都只要写一次就行了,只是需要进行一些位运算把那几位取出来。会提高很多效率。Huffman解码的时候一般是建立出二叉树,每次从根出发走1位,同样的道理这样也很慢。一个不错的改进是建立二叉树之后从根节点出发,枚举8bits(也可以替换为其他数值)的所有可能情况(0-255),计算如果解码遇到这8bits会跳跃到Huffman树的什么位置:如果跳跃到了叶子节点那么记录下实际是使用了多少bits跳跃到叶子节点的;如果没跳到叶子节点则需要继续从那个节点出发,枚举8bits继续同样的计算。这样在解码的时候就可以8步8步的跳,效率可以提高很多。这个解码的方法是licstar想到的,我实现了一下,实际测试很理想。
我总结使用Huffman就得活学活用,根据实际数据情况,可以使用多个Huffman树对应不同数据。也可以对数据进行某种处理之后再用Huffman(比如前后项求差),这样对于那种前后项依赖关系较大的就有很大优势。Huffman最大的缺点就是和上下文无关,因此通过各种人工预处理将前后关系融入每个数据单位中,再用Huffman就会非常有效。
SFF文件其他部分的压缩
其他部分占的不是很多,Read Header还稍微多一些。Read Header中Name都是”%s:%d:%d”的格式,并且%s在所有Read中都一样,可以只存储一次。%d前后变化不大,可以相邻求差再建立Huffman树。

这次确实很遗憾,如果没挂数据可能是第三或者第四,不过只要有第五我就很满足了,有一些物质回报,会有更多的纪念价值。不过做Marathon很耽误时间,以后一年最多也就做一次吧。

本文来自Dora Blog,题目为SFF Compression 纪念第一次TC Marathon,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987