3

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

输入两个 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

这将是微小的。

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

4

1 回答 1

2

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

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

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

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

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

然后你可以将它提供给一个deflateing 库进行压缩（并构建一个自解压存档）。

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

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

除了重新计算排序顺序，您可以缓存排序顺序并仅从中删除，甚至还缓存运行总计（或从重新计算运行总计切换到在运行时缓存运行总计）。这不会改变结果，只会提高运行时间。

于 2012-11-30T08:27:59.630 回答