jiry_2's Blog

嘛..隔了几百年总算是更新了..也是随便瞎写点东西..

毕竟慢慢淡出算法竞赛圈了，以后就多尝试写一些和算法竞赛关系不大的东西吧..

1.Run-length encoding（游程编码）

非常naive的一种编码方式，核心就是把 000000 这种串用 [6]0 来表示。通常情况下并没有什么卵用。

和FFT的思路一样，可以尝试找到一种可逆的变换，使得文本在作用了这个变换后，相同的字符会变得很多，以此来优化游程编码——Burrows-Wheeler Transformation.

这玩意好像在清华夏令营上也考过。核心就是在一个文本串的最后加上一个 #，然后把新串的所有循环同构串排个序，按照顺序从小到大把所有串的最后一个字符提出来，就得到了一个长度一样的变换后的串。

这样的好处是什么的，就拿英语文本来说，比如单词 KujouKaren 的出现次数非常多，在用后缀数组排序时，这些单词的出现位置倾向于连在一起，即会有很多连在一起的 K。

我试着写了一发，然后用这个来压缩格式化的哈姆雷特，差不多可以压缩 30%。就无损压缩来说还算比较强的。

2.DFT

DFT 可以拿来有损压缩图片。图片压缩的限制其实很松——不像文本压缩一样，容错率很小——有时 RGB 值出现了 10 左右的偏差，肉眼仍然无法识别。

一张图片可以表示为 RGB 三个值域在[0,256)中的整数矩阵。用 DFT 作用这些矩阵后，就得到了它们的点值表示。这时图片的信息变的集中，我们可以把一些信息量较小的点值变成 0 以达到压缩的效果。（直观来讲，模长较小的点值信息量就小，模长较大的信息量就比较大。）

看起来比较玄学，但是实际上效果是非常好的。

这四张图片分别消去了 [tex]0\%,90\%,99\%,99.9\%[/tex] 的点值。 

3.DCT

用 DFT 来作用矩阵虽然能达到比较好的压缩效果，但是要记录的信息比较多——每一个点值都是虚数，需要用两个数字才能记录。

那么自然的思想就是减少记录的信息，需要找到一个变换，使得它能达到 DFT 的效果，同时在变换之后每一个点值都是实数。

在 DFT 的过程中，虚数的部分都要乘上一个 [tex]\sin(x)[/tex]，DCT 的思想就是将序列对称然后下标平移 [tex]\frac{1}{2}[/tex]，使得在 DFT 时，[tex]\sin(x)[/tex] 都等于 [tex]0[/tex]，这样就能避免虚部的出现。

在变换的过程中，只使用了余弦函数，因此这个变换就被命名成离散余弦变换。

因为 DCT 是从 DFT 推导得到的，所以他们的效果也类似：

这四张图片分别消去了 [tex]0\%,90\%,99\%,99.9\%[/tex] 的点值。不过因为 DCT 记录的东西要比 DFT 少，所以在压缩效果上应当是 DCT 更胜一筹的。

4.SVD

当我们把一张图片看成一个 [tex]n \times m[/tex] 的矩阵时，就会有一个挺自然的压缩想法：我能不能找 [tex]r(r<m)[/tex] 个长度为 [tex]m[/tex] 的向量出来，然后把这 [tex]n[/tex] 个行向量用这些向量近似一下，这样我只需要存储 [tex]r \times m + n \times r[/tex]个信息就可以了。

SVD（奇异值分解）就是干这个事情的，运用一些线性代数的知识，可以得到一个 [tex]n \times m[/tex] 矩阵用 [tex]r[/tex] 个向量拟合的理论最好结果。

大致的过程就是对矩阵 [tex]A[/tex]，求 [tex]AA^T[/tex] 和 [tex]A^TA[/tex] 的特征值和特征向量，那么可以将原矩阵分解成特征向量作为列向量的矩阵乘特征值开方后形成的对角矩阵乘特征向量作为行向量的矩阵。

求特征值最暴力的做法就是暴力 [tex]O(n^4)[/tex] 把特征多项式消出来，然后爆解方程。我在写程序的时候用的是网上搜到的Jacobi迭代法，它可以求一个对称矩阵的特征值和特征向量。

它的思想其实很简单，就是利用一个矩阵左乘一个正交矩阵再右乘这个矩阵的转置后，特征值和特征向量不变的特性，通过一系列这样子的变换，将矩阵变成近似对角矩阵的形式，从而得到原矩阵近似的特征值和特征向量。

每一步它都构造一个矩阵，将绝对值最大的一个非对角线上的元素变成 [tex]0[/tex]。这个算法不能保证能在有限步内将矩阵变成对角矩阵，但是可以保证非对角线元素越来越接近 [tex]0[/tex]，在图片压缩这种非常不需要精度的场合来说，还是非常适用的QvQ。

取 [tex]r[/tex] 个向量时，只需要保留绝对值最大的 [tex]r[/tex] 个特征值和它们对应的特征向量即可。

压缩后的效果如下；

第一张图是原图，秩大概为 [tex]300[/tex]，后六张压缩时分别取了 [tex]r=100,50,25,10,5,1[/tex]。使用 SVD 压缩需要记录的信息的常数也是非常小的，效果感觉要比 DFT 和 DCT 都要好一些，但是因为求特征值和特征向量的计算量比较大，所以在时间效率上要略逊一筹。