更好的向量数据压缩算法？

Question

我需要压缩一些空间相关的数据记录。目前，我使用zlib可以获得1.2x-1.5x的压缩比，但我认为应该可以达到更高的2倍压缩比。这些数据记录有各种字段，但例如，zlib似乎难以压缩点列表。

这些点表示道路网络。它们是固定点4字节整数对XXXXYYYY的形式。通常，如果单个数据块有100个点，则X和Y的前两个字节将只有几个组合（空间相关性）。但底部字节始终在变化，必须对zlib看起来像随机数据。

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

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

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

- Qwertie

---

数据是一系列记录，通常代表道路，每个记录包含点列表以及其他信息，例如地址范围、ID、速度限制和指向另存储的街道名称记录的指针。这些记录被压缩成尽可能少的比特，尽管这也可能在某些情况下挫败基于字节的zlib。 - Qwertie

还有一些其他数据，其中99%是点数，这就是我知道zlib无法很好地压缩这些点的原因。 - Qwertie

我有一个压缩工具，还没完成，但已经接近了。你可以完全访问(http://www.github.com/aunk/comb)，它是真正压缩的准备工作。如果你能把它做好，我很乐意让你小有名气。我们可以分享我追求的奖励。 - David Pulse

我的程序反转了字节查找，因此聚集的0和1的数量被改变为有限的数量，以便实际压缩程序可以找到并使用这些模式。 - David Pulse

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之前，请尝试自行删除重复数据。您可以做得更好，因为您对数据有额外的了解。

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

- jalf

---

这是一个好主意，我只是希望有一种算法能够自动处理这种类型的数据。我的系统设计并不适合这种重新排列。 - Qwertie

如果您的系统设计不支持这种重新排列，但支持通过zlib运行这些内容，则只需编写自己的过滤器以替代zlib，该过滤器针对您的数据格式进行特定处理。 - Phil Miller

@Novelocrat：这也是个好主意，但我的数据结构虽然是二进制的，但与XML一样通用，因为各种原因，你的想法对我行不通...也许BWT可以有所帮助，但我已经放弃了这个问题，所以我接受这个答案。 - Qwertie

Answer 2

虽然不是针对你的数据，但如果可以的话，我建议你使用7zip而不是zlib。 我曾经看到过使用它时非常好的压缩比率。

http://www.7-zip.org/

- bshields

---

+1 建议（假设可使用源代码形式的 7-zip），但我忽略了它正在运行于 WinCE 平台上，因此必须要快；而 7-zip 可能过于庞大且速度慢。 - Qwertie

Answer 3

通过某种接近度量对点进行排序，使相邻点之间的平均距离较小。然后存储相邻点之间的差异。

如果您设法将点排序，使大多数差异在x和y轴上都是正的，那么效果可能会更好，但我不能确定。

作为zlib的替代方案，一族压缩技术通用编码在概率分布偏向小数时表现良好。它们必须针对有符号数字进行调整（编码abs(x)<<1 + (x < 0 ? 1 : 0)）。

- Marcelo Cantos

---

这些点是有序的。如果我改变它们的顺序，那么我将不得不添加一个索引来重建原始顺序，可能会增加整体大小。包含这些点的记录（代表道路）是无序的，但重新排列它们很麻烦。我怀疑通过分离高字节和低字节可以获得更好的压缩效果，但由于我的数据存储系统非常通用（用于系统中所有记录，无论其性质如何），所以我认为最好避免使用特定目的的代码来污染它。 - Qwertie

此外，我认为将它们在空间上排列并不能对zlib有太大的帮助。就我所知道的压缩算法而言，我不认为它能够识别数字相关性——如果你给它一个字节序列1、2、3、……100，它的压缩效果和随机字节一样糟糕。 - Qwertie

@Qwertie：考虑两个绝对值序列：100、101、102 和 200、201、202。现在将它们视为相对值：0、1、2 和 0、1、2。使用相对值可以让任何基于字典的压缩器将这两个序列合并。 - Steven Sudit

不错的观点，尽管在地理点的情况下，不同对/系列点之间的差异几乎从未完全相同 - 但是确实如此，它们将比原始点更相似。 - Qwertie

它们不必完全相同。因为增量的概率分布严重偏向于小数，哈夫曼树会通过需要更少的位来编码它们来支持这些小数。不过，可以看看我的修改后的答案，提供了另一种选择。 - Marcelo Cantos

Answer 4

没有看到数据及其确切分布，我无法确定最佳方法，但我建议您在每组1-4条记录中以一个字节开始，该字节的8位指示以下内容：

0-1 从上一条记录中借用的ID字节数 2-4 位置记录格式 6-7 使用相同“模式”字节的后续记录数

每个位置记录可以以八种方式之一存储；除了000类型之外的所有类型都使用有符号位移。位码后面的数字是位置记录的大小。

000 - 8 - 两个完整的四字节位置 001 - 3 - 十二位X和Y 010 - 2 - 十位X和六位Y 011 - 2 - 六位X和十位Y 100 - 4 - 两个十六位有符号位移 101 - 3 - 十六位X和8位Y有符号位移 110 - 3 - X为8位有符号位移；Y为16位 111 - 2 - 两个八位有符号位移

模式字节为零将存储所有适用于点的信息，而不参考任何先前的点，使用总共13个字节来存储12个字节的有用信息。其他模式字节将允许根据与先前记录的相似性来压缩记录。如果四个连续记录仅在ID的最后一位上不同，并且X和Y都在前一个记录的+/- 127范围内，或者X在+/- 31范围内，Y在+/- 511范围内，或者X在+/- 511范围内，Y在+/- 31范围内，则所有四个记录可以存储在13个字节中（平均每个记录3.25个字节（空间减少了73%）。

可以使用“贪心”算法进行压缩：检查记录以查看输出中将使用哪个大小的ID和XY，然后获取多达三个记录，直到找到一个记录，该记录无法使用所选大小与先前记录“匹配”，或者可以更小地编写（请注意，例如，如果第一条记录的X和Y位移都等于12，则XY将用两个字节编写，但是在读取以下记录之前，人们不知道要使用哪种两个字节格式中的哪一个）。

在确定你的格式之前，我建议你先将数据运行一遍。也许只需要进行小的调整（例如使用7+9或5+11位格式而不是6+10），就可以更好地压缩许多数据。然而，真正了解情况的唯一方法是查看实际数据的效果。

- supercat

Answer 5

看起来Burrows-Wheeler transform可能对这个问题有用。它有一个奇特的倾向，将重复字节的运行放在一起，这可能使zlib压缩更好。这篇文章建议我应该将BWT与除zlib以外的其他算法结合使用。

直觉上听起来很昂贵，但是查看一些源代码后发现，反向BWT是O(N)，需要对数据进行3次传递和适度的空间开销，可能足够快地在我的目标平台（WinCE）上运行。正向变换大约是O(N log N)或略高，假设使用普通排序算法。

- Qwertie

---

这是我的建议。具体来说，我建议您看一下BZip2，这是我所知道的唯一流行的BWT实现。它有一组压缩器，可能不完全适合您的数据集，但具有相当好的调试和规范化优势。 - Jason

Answer 6

你可能想要将两个列表写入压缩文件：一个 NodeList 和一个 LinkList。每个节点都会有一个 ID、x 和 y 坐标。每个链接都会有一个 FromNode 和 ToNode，以及一系列中间 xy 值的列表。你可以使用带有虚假原点的标题记录，并使节点 xy 值相对于该原点。

如果您的街道遵循城市网格网络，则这将提供最大的好处，通过消除交叉口处的重复坐标。

如果不需要无损压缩，则可以使用截断的增量来表示中间坐标。虽然上面有人提到了增量，但请记住，连接性的丢失可能会比形状的丢失更容易引起问题，如果您使用截断的增量来表示道路的最后一个坐标（通常是交叉口），那么就会发生这种情况。

同样，如果您的道路不在城市网格上，则可能不会带来太多好处。

- Kirk Kuykendall

---

我刚注意到上面的评论中提到了“以及其他信息，如地址范围、ID、速度限制和指向存储在其他地方的街道名称记录的指针”。如果您有很多属性，可以看看是否有线性参考系统LRS可用（例如，roadID，milepost）。这将允许您拥有一个属性记录跨越多个道路段，而不是为每个道路段重复一次。http://en.wikipedia.org/wiki/Linear_Reference_System - Kirk Kuykendall

谢谢，但我只是想了解压缩算法。你所建议的是对数据的完全重新组织，这可能是我最终会考虑的（但我已经有自己的想法）。顺便说一下，想想看，如果重复点是相同数据“块”的一部分，那么重复可能并不是一个大问题，因为zlib应该会注意到重复并将其压缩掉。 - Qwertie

说起来，LRS 最终可能会派上用场...谢谢你的提示！我需要完全重写很多东西，但我们可能有预算;) - Qwertie