二维点集的压缩-有什么思路？

Question

我有一组存储在数组中的二维点。我需要尽可能地压缩它。最好是快速压缩，但不是必须的，压缩率是目标。规则如下：

- 一个点 = 一个32位结构体，存储为(x,y)，每个坐标2字节。 - 一个坐标 = 一个"float"，有8位整数部分和8位小数部分。

特殊属性：

- 我可以根据需要更改点的顺序。 - 我按照它们的x和y的整数部分的顺序给出点，也许我可以利用这一点，但从我看到的情况来看，小数部分几乎是随机的。 - 我收到的数组是连续的（从内存的角度来看）。

我目前的研究：

• 将它们视为普通整数（32位），对它们进行排序（顺序由我选择），然后像this question中那样进行压缩。
• 将我的数组视为普通字符字符串，然后应用Burrows-Wheeler变换（BWT）与run-length编码或Huffman。
• 将我的数组视为普通二进制数据，然后应用LZW。

我只能实现Huffman和BWT，但它们都没有给我一个好的压缩比率（或使用我的数据集的主要属性）。今天我将尝试第一种选项。

我很确定有更好的想法。你有吗？你是否遇到过类似的情况并实现了一些非常好的东西？

数据集示例，以十六进制表示：

00 0A 00 77 00 55 00 80 00 2B 00 B9 00 7A 00 5B 
00 F6 00 76 00 B4 00 25 00 47 00 D3 00 F6 00 7D
...
01 05 00 A9 01 B8 00 10 01 4F 00 6A 01 E6 00 DF
01 1F 00 F0 01 BE 00 C3 01 6C 00 87 01 CE 00 44
...
...
15 06 03 F4 15 1E 03 29 15 35 03 10 15 B9 03 22
15 67 03 73 15 EF 03 5C 15 29 03 B8 15 4C 03 2F
...

例如，粒子15 67 03 73（最后一行）表示位于x = 15和67/256，y = 3和73/256的粒子。正如您所看到的，数据有些有序，但小数部分却是完全混乱的。

- webuster

---

“float”实际上是“fixed”。不管怎样，你的数据集是什么样子的？ - harold

是的，这是一种固定小数。对我来说，小数部分看起来很随机，但整数部分是有序的（首先按x排序，然后按y排序）。我在问题中添加了一个示例。 - webuster

除非您了解分布情况，否则最佳算法是对多重集进行排名和取消排名。 - David Eisenstat

那就是重点，没错... - webuster

你可以尝试交错x和y位，排序，进行delta编码。（我可能会尝试xyyxxyyxxyyxxyyxxyyxxyyxxyyxxyyx。） - greybeard

Answer 1

首选项是OP提供的更合适。但可以进一步改进。

1. 将坐标重新解释为16位整数。
2. 将点位置转换为沿希尔伯特曲线（或任何其他空间填充曲线）的距离。
3. 对距离进行排序，然后应用增量编码（计算相邻距离的差异）。
4. 根据压缩/速度偏好，（a）使用类似Elias或Golomb编码（最快），（b）使用Huffman编码，或（c）使用类似算术编码（最佳压缩率）的内容。

如果点分布中存在某种模式，则可以尝试更高级的压缩器来执行第4步：LZ*、BWT或PPM。

---

这是步骤4中使用的方法的实验比较结果。假设最坏情况：点在00.00 .. FF.FF范围内随机均匀分布（因此唯一的压缩可能性是失去有关它们排序的信息）。所有结果都是针对250000个点计算的：

method        compressed size
------        ---------------
Uncompressed: 1000000
Elias4:        522989
Elias3:        495371
Elias2:        505376
Golomb12:      479802
Golomb13:      472238
Golomb14:      479431
Golomb15:      501422
FSE1:          455367
FSE2:          454120
FSE3:          453862

我没有尝试过Huffman编码。FSE是一种类似于算术编码的方法。方法名称后的数字显示配置参数：对于Elias编码-用于编码每个数字的位长度的位数，对于Golomb编码-保留多少最低有效位未压缩，对于FSE-压缩多少最高有效位（以及位长度）。

所有结果都由此来源生成：http://ideone.com/ulmPzO

- Evgeny Kluev

---

你能详细解释一下希尔伯特曲线吗？ - webuster

希尔伯特曲线将您的点从2D空间映射到1D，同时保留局部性（这意味着步骤3后的距离增量往往较小，因此可以更好地压缩）。在我看来，希尔伯特曲线比其他填充曲线稍微更好地保留了局部性，尽管与其他曲线相比，它需要稍微更复杂的实现（salva提出的想法与Z曲线相同，其具有最简单的实现）。 - Evgeny Kluev

在将坐标映射到希尔伯特曲线之前，您可以从将点占用的区域（除了可能的一些异常值）映射到希尔伯特曲线所占用的正方形区域开始。这意味着可能需要将两个坐标都放大，以使高度/宽度扩展到下一个二次幂。将坐标映射到距离和反向映射的算法是众所周知的，您可以在wikipedia上找到它们。 - Evgeny Kluev

如果您的点是随机均匀分布的，希尔伯特曲线以及Z曲线或其他填充空间的曲线都无法提供帮助。在这种情况下，我更喜欢以更简单的方式将点映射到1D：d=x+y*w，其中w是点区域的宽度。 - Evgeny Kluev

Answer 2

将表示每个点的X和Y坐标的位交错，排序并压缩。

例如，如果您有由两个16位数字表示的点(X, Y)

(X₁₅X₁₄X₁₃X₁₂X₁₁X₁₀X₉X₈X₇X₆X₅X₄X₃X₂X₁X₀, Y₁₅Y₁₄Y₁₃Y₁₂Y₁₁Y₁₀Y₉Y₈Y₇Y₆Y₅Y₄Y₃Y₂Y₁Y₀)

将其转换为以下32位数字：

X₁₅Y₁₅X₁₄Y₁₄X₁₃Y₁₃X₁₂Y₁₂X₁₁Y₁₁X₁₀Y₁₀X₉Y₉X₈Y₈X₇Y₇X₆Y₆X₅Y₅X₄Y₄X₃Y₃X₂Y₂X₁Y₁X₀Y₀ 这将利用数据中可能出现的任何聚类，因为在排序列表上，接近物理位置的点将出现在附近位置，并且它们的表示共享头位。 更新: 目的是让附近的点在附近位置排序。如果混合X和Y位，你会得到这个结果，在长序列的32位整数中，头部位相同。如果你进行增量计算，你将获得比仅按X排序然后按Y排序（或反之亦然）更小的值。

问题是，你可以将其视为k-d树，每个位划分空间（左/右或上/下）。对于前几层，你可以压缩它们，只需说明一侧有多少元素，直到你到达只有一些元素的极点，这些元素可以通过明确说明剩余的几位来表示。为了获得最佳压缩效果，你将需要使用算术编码。

- salva

---

那么你的意思是用交错位重写点，再用游程长度编码进行排序和压缩？这样做比不用交错位更好在哪里呢？ - webuster