怎样可以较简便的压缩存储一串数据，已知该数据是单调递增的序列。

wsc810

如题，同时也可设数据中有多个相同的数。

gxqcn

需要看具体的原始数据。

比如说对前n个连续素数来说，

方案一、除去2、3、5后，其它数关于模30的余数只能为{1、7、11、13、17、19、23、29}八个数之一，
这样，在每跨度为30的范围内，仅需一个BYTE就可记录其里面哪些是素数。

方案二、从3开始，相邻两数只差为偶数，可以用相邻数差值的一半记录。
在一定范围内（已大于2³²），该半差值最大值若不超过255，则可以仅用一个BYTE即可实现。

以上举例虽不具有通用性，但可作为特例供参考。

wsc810

想到一个办法，即便不是单调递增的序列(要求数列中不出现零)，可以将这些数通过一种数学方法，转换为两个大数，方法就是将这些数看做是两个数$p_n,p_{n-1}$进行辗转相除法后得到商数$[a_1,a_2,a_3...a_n]$,利用
      $p_n=a_np_{n-1}+p_{n-2}$,得到$p_n,p_{n-1}$，问题就转化为求两个大数的压缩存储问题。
同样若对一串数据包压缩，则可用由一个字节或半个字节的构成的$a_n$,(这些数不超过256，或16，即遇到0变为256，或16)转化为两个大数。不知目前对大数压缩存储目前都用什么方法。

wsc810

想到一个办法，即便不是单调递增的序列(要求数列中不出现零)，可以将这些数通过一种数学方法，转换为两个大数，方法就是将这些数看做是两个数$p_n,p_{n-1}$进行辗转相除法后得到商数$[a_1,a_2,a_3...a_n]$,利用
      $p_n=a_np_{n-1}+p_{n-2}$,得到$p_n,p_{n-1}$，问题就转化为求两个大数的压缩存储问题。
同样若对一串数据包压缩，则可用由一个字节或半个字节的构成的$a_n$,(这些数不超过256，或16，即遇到0变为256，或16)转化为两个大数。不知目前对大数存储压缩用什么方法。

仙剑魔

因为是递增的，所以先相邻做差。。。
这样每个数据需要的bit就会下降。。。

最YY的方法是拟和出曲线。。。

liangbch

以素数递增表为例，若仅记录相邻素数差，则可能大部分数是，2，4，6等，这样，
  1. 数的分布很有规律，如果用哈弗曼编码则可进一步减少数据量。、
  2. 考虑采用FFT变换或者JPG图像编码中的离散余弦变换，不知是否可进一步压缩数据。

仙剑魔

6# liangbch


FFT和DCT涉及小数计算，量化后不知道能不能实现无损
就变换后的结果而言，貌似是把能量集中（我老师说的）
似乎和LZ的原始数据的递增效果相同？（我不是很清楚，最好有人解释下。。。）

无心人

楼上的算法都是有损压缩的

可以多次求相邻差啊