c++ - 更好的 vector 数据压缩算法？

Question

我需要压缩一些空间相关的数据记录。目前我使用 zlib 获得 1.2x-1.5x 压缩，但我认为应该有可能获得更接近 2x 的压缩。数据记录有各种字段，但例如，zlib 似乎无法压缩点列表。

这些点代表道路网络。它们是 XXXXYYYY 形式的定点 4 字节整数对。通常，如果单个数据 block 有 100 个点，则 X 和 Y 的前两个字节(空间相关)的组合只会很少。但是底部字节总是在变化，并且对于 zlib 来说必须看起来像随机数据。

同样，记录具有 4 字节 ID，往往具有恒定的高字节和可变的低字节。

是否有另一种算法能够更好地压缩这种数据？我正在使用 C++。

编辑:请不要再提出更改数据本身的建议。我的问题是关于自动压缩算法。如果有人链接到所有流行压缩算法的概述，我会接受它作为答案。

Answer 1

如果您尝试根据您对数据结构的了解自行压缩数据，您可能会获得更好的结果。

通用压缩算法只是将您的数据视为比特流。他们寻找常用的位序列，并用较短的字典索引替换它们。

但是重复数据并没有消失。重复的序列变短了，但它仍然像以前一样经常重复。

据我了解，你有大量表格的数据点

XXxxYYyy，其中大写字母非常统一。所以将它们排除在外。

将列表重写为类似于此的内容:

XXYY // a header describing the common first and third byte for all the subsequent entries
xxyy // the remaining bytes, which vary
xxyy
xxyy
xxyy
...
XXYY // next unique combination of 1st and 3rd byte)
xxyy
xxyy
...

现在，很少变化的字节的每个组合只列出一次，而不是为它们出现的每个条目重复。这加起来显着节省了空间。

基本上，在通过 zlib 运行它之前，尝试自己删除重复数据。您可以做得更好，因为您对数据有更多的了解。

另一种方法可能是，不是将这些坐标存储为绝对数字，而是将它们写为增量，与选择的某个位置的相对偏差尽可能接近所有条目。您的增量将是更小的数字，可以使用更少的位来存储。