TopCoder马拉松DATCompression2解题思路

  这是一个月前的比赛了。一直 YY 着能拿到奖金,直到膝盖中了一箭:事情发生在比赛的最后一天,神一般的提交都诞生于那天,直接破灭了我保住第五的希望。最后一晚上的苦逼挣扎由于编码速度太慢,也没完成理想中质的飞跃。总而言之就是好久不编程,高估了自己的实力,最后花了不少时间没刷到奖。

  简单介绍一下比赛的题目。这次马拉松是一个压缩问题。有一个 pH 测试仪的阵列,摆成 X*Y (其实就是 900*900)的方阵。仪器运行 L(L在60左右)个时间单位,每个时刻记录一下 pH 值。也就是说,一次实验一共记录了 X*Y*L 个实验数据。现在的任务是,压缩这些值,压缩率越高越好。比较有意思的是,比赛允许有损压缩,但是复原以后的值和原值的差、以及差的平方和都有误差限制。

我的方法

  观察数据发现,pH 测试仪里面每个测试点得到的测试结果,在总体上是连续的,不会有太大的变化。于是对于每个测试点的 L 个测试结果,可以采样若干点,并用插值算法对完成复原。
  于是就形成了这样的算法框架:

原始序列: d[0] ... d[L-1]
抽样其中的某些点:d[x_0], d[x_1] ... d[x_n]
用不精确的方式存储:d[x_1]-d[x_0], d[x_2]-d[x_1] ... d[x_n]-d[x_{n-1}], 以及d[x0]。 (x_0 = 0, x_n = L-1)
最后插值产生没存储的点

  由于存储的那些数据是使用 Huffman 编码的,重复的数字越多,压缩率就越高。在比赛中,我使用的“不精确的方式存储”是使用 val/t*t 代替 val。其中 t 是参数,一般在 8 到 20 之间。使用这种方式可以将相邻的 t 个数计入一个数,使用 Huffman 编码时压缩率会有显著地提高。
  这里同时要解决两个参数的优化,抽样的点集(对于每个位置的 pH 仪器使用相同的抽样点)、t。抽样点集可以使用 DP 算法求的在有 n 个抽样点时,最佳的抽样位置在哪(见参考文献,基本类似他的思路。实际上比均匀采点好不了多少,但还是用了)。确定了抽样点之后,穷举 t,找到符合精度要求的压缩率最高的 t。
  经过这两步计算,就可以得到一大堆 <n, t> 对的集合,有着不同的误差和压缩率。从中选取出最佳的搭配即可。最后使用的 n 一般在 10 到 20 之间。

  在实践中,直接对整个数据集进行优化,复杂度较高,不能在 10 秒内完成计算。我先从 X*Y 个仪器中抽样出 1000 个样例仪器,只对这 1000*L 个数据进行压缩,求得参考的 <n, t> 对集合,并选择若干个最优的跑一遍完整的数据,选择在实际数据集上符合误差要求且压缩率最优的。

  只有这些优化还不足以让我刚刚没奖,还有两个重要优化可以提升较多。
  1. 使用多棵 Huffman 树代替一棵树。观察数据可以发现,在各时刻,不同位置的 pH 仪器获得的结果是有一个总体趋势的,可能总体上涨,或者总体下跌。这样的话,在不同的时间用不同的 Huffman 树存储,由于数据的分布更集中了,压缩率会有提升。
  2. 对于某些特殊位置的 pH 仪,使用一套特别的压缩方式。在开放的数据集中,有些数据有一些 pH 仪测试出来的结果不符合主流分布。它们的记录结果随机震荡,非常不适合插值。如图 1 中第二行第五列的黑色区域。由于这部分区域非常难插值,选用较少的抽样点(n)会造成很大的误差(即便这只是 5% 的仪器造成的误差)。这个优化就是,对于这些特殊的位置,采用大量抽样点(甚至不抽样)的方式存储,当然 t 可以选取的比较大;同时对于大部分数据,仍然采用之前描述的方法存储。

  最后就是一大堆常数优化了,模运算打表之类。

  自认为这套框架已经走到基本极限了,从最后的结果来看也是。排在前面的人都有独到之处。

zaq1xsw2tktk 的方法

  赛后,我向 zaq1xsw2tktk 大神请教了他的方法。和我前面描述的方法基本类似,zaq1xsw2tktk 大神也是采样加上 val/t*t 的方式取近似值。不同的是,他在采样时,采样点非常的多,每隔一个位置就设一个采样点。由于采样点非常密集,求差时 0 会非常多。如果误差还没有超过阈值,则会修改某些值,使得连续的 0 变得更多。
  对于生成的差值序列,zaq1xsw2tktk 大神并没有直接使用 Huffman 编码压缩,而是先作了一步预处理。对于连续的 0,只存储 0 的个数。下面是一个 zaq1xsw2tktk 大神提供的例子:

0,0,0,0,0,10,10,0,0,0,0,-10
编成两个序列(5,0,4),(10,10,-10)
5个0 , 一个10 ,0个0,一个10, 4个0,一个-10

  预处理之后,再使用 Huffman 编码压缩,会有巨大的提升。

delicato 的方法

  delicato 在这场比赛中是毫无悬念地夺冠了,比赛排行榜的前面大概是这个样子的:

名次 成绩 handel
1 4143 delicato
2 2649 zaq1xsw2tktk
3 2490 Psyho
4 2479 Celebrandil
5 2204 davies
6 2156 venco
7 2089 licstar

  冠军的方法究竟是什么呢?其实我挣扎了这么久,早应该想到……裸的 SVD。不用多解释了,SVD 就是干这个的。(细节上 delicato 也对震荡激烈的特殊位置的 pH 值做了单独处理。)

总结

  对我来说,处理这种问题很重要的一步就是“看”数据,包括一行行地看,分析其中的关联等等。
  这次我用了两种比较简单的方法可视化数据,第一个图描述了 0 时刻各位置的测试值大小,颜色越亮表示值越大。里面的每个小图表示一个待压缩的文件。
  每张第二个图是相邻两个时刻各位置的变化情况,图片里的每个小图依次描述了某个文件不同时刻的变化情况。绿色表示值变小了,红色表示值变大了。如果仔细观察,会发现里面有比较明显的区域化现象,前面几个小图中能看出一些有规律的方块。另一个规律是变化总是从右下往左上推进的。这两点在比赛中并没有用到,或许能有好的方法可以用上各种数据特征,达到更优的结果。
  最后又回到老问题,遇事总是先 YY,吃了一次又一次的亏。什么时候才会先去找已有工作呢……

图1

图2

3 评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注