这是一个月前的比赛了。一直 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，吃了一次又一次的亏。什么时候才会先去找已有工作呢……