在给定范围内找到最可压缩的向量?

Question

我已经将我正在处理的压缩问题减少到以下内容：

作为输入，您将获得两个浮点值的 n 长度向量：

float64 L1, L2, ..., Ln;
float64 U1, U2, ..., Un;

这样对于所有我

0.0 <= Li <= Ui <= 1.0

(顺便说一下，n 很大：~10^9)

该算法将 L 和 U 作为输入，并使用它们来生成程序。

执行时，生成的程序输出一个 n 长度的向量 X：

float64 X1, X2, ..., Xn;

这样对于所有我：

L1 <= Xi <= Ui

生成的程序可以输出任何符合这些边界的 X。

例如，生成的程序可以简单地将L存储为数组并输出它。 (请注意，这将需要 64n 位空间来存储 L，然后程序需要一点额外的空间来输出它)

目标是生成的程序(包括数据)尽可能小，给定L和U。

例如，假设 L 的每个元素都小于 0.3，U 的每个元素都大于 0.4，生成的程序可能只是：

for i in 1 to n
output 0.35

这将是很小的。

任何人都可以提出一个策略、算法或架构来解决这个问题吗？

Answer 1

这种简单的启发式方法非常快，如果边界允许非常好的压缩，应该提供非常好的压缩：

在所有候选值上准备一个任意(虚拟)二叉搜索树。float64与signed int64s 共享排序顺序，因此您可以任意首选(更接近根)具有更多尾随零的值。

• 对于每对边界
  • 从根源开始。
  • 当当前节点大于两个边界或小于两个边界时，
    • 从树上下来。
  • 将当前节点追加到向量中。

对于上面提到的树，这意味着

• 对于每对边界
  • 在指定范围内查找有效位数尽可能少的(唯一)数字
  。也就是说，找到两个边界不同的第一个位;将其设置为1并将所有后续位设置为0;如果设置为1的位是符号位，请改为将其设置为0。

然后，您可以将其提供给deflateing库进行压缩(并构建自解压存档)。

---

如果您分析数据并构建不同的二叉搜索树，则可能会实现更好的压缩。由于数据集非常大并且以数据流的形式到达，因此可能不可行，但这是一种启发式方法：

• 而输出未完全定义
  • 查找适合最未定范围的任何值：
    • 将所有边界排序在一起：
      • 具有较低值的边界先排序于具有较高值的边界。
      • 下限在具有相同值的上限之前排序。
      • 无法区分的边界组合在一起。
    • 计算开放间隔的运行总数。
    • 选择最大的总数。上限或下限都可以。您甚至可以尝试通过用最少的有效位拆分间隔来做出"明智的选择"。
  • 将此值设置为可以使用它的所有位置的输出。

您可以缓存排序顺序并仅从中删除排序顺序，甚至同时缓存运行总计(或从重新计算运行总计切换到在运行时缓存运行总计)，而不是重新计算排序顺序。这不会改变结果，只会改善运行时间。