整数CSV压缩算法

Question

我对压缩逗号分离整数的算法的存在进行了表面级的研究，但是我没有发现任何相关的东西。

我的目标是压缩大量已知值范围的结构化逗号分隔整数。有没有已知的算法来做这样的事情？如果不是的话，从哪里开始阅读一些相关的兴趣领域，这将使我开始开发这样的算法？当然，该算法必须是可逆转的，并且是有损失的，这样我就可以解压缩压缩的数据来检索csv值。

数据结构是一个由三个值组成的数组，一个数的域从0到4，第二个从0到6，第三个从0到n，其中n不是一个大数。此结构被重复以创建数据，该数据位于二维数组中。

Answer 1

在结构化数据上使用标准的压缩算法(如gzip或bzip2 )并不能获得最佳的压缩效率，因此构造一个特定于案例的算法是可行的。

数据结构如下所示，并举例说明。

// cell: a data structure, array of three numbers
// digits[0]: { 0, 1, 2, 3, 4 }
// digits[1]: { 0, 1, 2, 3 }
// digits[2]: { 0, 1, 2, ..., n } n is not an absurdly large number
// Below it is reused in a multi-dimensional array.
var cells = [
    [ [3, 0, 1], [4, 2, 4], [3, 0, 2], [4, 1, 3] ],
    [ [4, 2, 3], [3, 0, 3], [4, 3, 3], [1, 1, 0] ],
    [ [3, 3, 0], [2, 3, 1], [2, 2, 5], [0, 2, 4] ],
    [ [2, 1, 0], [3, 0, 0], [0, 2, 3], [1, 0, 0] ]
];

我使用标准压缩算法对这个数据结构(不包括空格作为字符串)进行了各种测试：

• gz从171字节压缩到88字节
• bzip2从171个字节压缩到87个字节
• 压缩从171字节压缩到76字节

我所构造的算法将数据压缩到33个字节，直到n= 192。因此，在特定情况下，我能够用标准文本压缩算法的双重效率压缩我的数据。

我实现这种压缩的方法是映射所有不同组合的可能值，这些组合可以保持在整数上。如果你想研究这样一个概念，这就是数学中的组合学。然后，我将基10整数转换为字符串表示的较高基值。

由于我的目标是人类可用性(压缩代码将被输入)，我使用了基数62，我表示为{0-9，am，am}，分别从0到61。我将单元格长度转换为Base62时缓冲为两位数。这允许62*62 (3844)不同的细胞组合。

最后，我在表示列数的压缩字符串的开头添加了一个基62位数。解压缩时，y大小用于从字符串长度推断x大小。这样，就可以在不丢失数据的情况下正确地解压缩数据。

上面示例的压缩字符串如下所示：

var uncompressed = compress(cells); // "4n0w1H071c111h160i0B0O1s170308110"

我解释了我解决问题的方法，以帮助其他面临类似问题的人。我没有提供我的代码，因为不清楚的原因。

TL；博士

要压缩结构化数据：

1. 将离散对象表示为整数
2. 将基数10的整数编码为较高的基数。
3. 对所有对象重复
4. 将行数或列数追加到压缩字符串中

要解压缩结构化数据：

1. 读取行或列，并从字符串长度推断其他行或列。
2. 压缩中的反向步骤1和步骤2
3. 对所有对象重复

Answer 2

除非您的列表中有一些特定的结构是您没有透露的，而且这可能会极大地帮助压缩，否则标准的无损压缩算法(如gzip或bzip2 )应该能够很好地处理一系列数字。

这类通用算法的库应该在几乎所有语言和平台上随处可见。