c++ - 二维点集的压缩 - 想法？

Question

我有一组存储在数组中的二维点。 我需要尽可能多地压缩它。最好是快速，但不要破坏交易，压缩率是目标。规则是:

• 一个点=一个32位的结构，存储为(x,y)，每个坐标2个字节
• 坐标 = 8 位整数部分和 8 位小数部分的“ float ”

特殊属性:

• 我可能会根据需要更改点的顺序
• 我按照 x 和 y 的整数部分的顺序给出了点，也许我可以利用它，但从我所看到的来看，小数部分几乎是随机的
• 我收到的数组是连续的(从内存的角度来看)

到目前为止我研究过的内容:

• 将它们视为普通整数(32 位)，对它们进行排序(顺序由我选择)，然后将其压缩为 this question。 .
• 将我的数组视为一个普通的 char 字符串，然后应用 a Burrows-Wheeler transform (BWT) 与 run-length encoding , 或 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 处的粒子。如您所见，数据有些有序，但小数部分完全困惑。

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

我没有尝试使用霍夫曼编码。 FSE是一种类似于算术编码的方法。方法名称后的数字显示配置参数:对于 Elias 编码 - 有多少位用于编码每个数字的位长，对于 Golomb 编码 - 有多少最低有效位未压缩，对于 FSE - 有多少最高有效位被压缩(连同位长).

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