compression - 压缩一组大整数

Question

我有一组整数，我希望有最紧凑的表示。
我有以下限制/功能:

它被设置，或者换句话说，一个唯一整数的列表，其中的顺序无关紧要

集合 L 的大小相对较小(通常为 1000 个元素)

整数遵循 0 和 N-1 之间的均匀分布，其中 N 相对较大(比如 2^32)

对压缩集元素的访问是随机的，但如果解压过程不是那么快也没关系

压缩应该是无损的，显然

我尝试了一些事情，但我对结果并不满意，而且我以某种方式确信存在更好的解决方案:

增量编码(排序，然后编码差异)，或者也排序，然后编码第 i 个元素和 i*N/L 之间的差异。两者都给出了合理的结果，但不是很好，可能是因为 N 和 L 的典型大小。霍夫曼编码增量没有帮助，因为它们通常很大。

递归范围缩减 ( http://ygdes.com/ddj-3r/ddj-3r_compact.html )。这看起来很聪明，但在指数递减的整数上效果最好，这里绝对不是这种情况。

这里关于 stackoverflow 的一些讨论是相似的，但并不完全等同于我的问题( C Library for compressing sequential positive integers 、 Compress sorted integers )

我很高兴听到您的任何想法。提前致谢!

更新:

事实证明，增量编码似乎近似于最佳解决方案。对于集合中元素的其他其他分布，这可能不同。

Answer 1

你可以通过数数来了解你能做的最好的事情。 (我希望 stackoverflow 允许像 math.stackexchange 这样的 TeX 方程。无论如何......)

ceiling(log(Combination(2^32,1000)) / (8 * log(2))) = 2934

因此，如果如您所说，选择是均匀分布的，那么对于该特定情况，您希望平均的最佳压缩为 2934 字节。最佳比例是 4000 字节未编码表示的 73.35%。
Combination(2^32,1000)只是压缩算法的可能输入的总数。如果这些是均匀分布的，那么最佳编码是一个巨大的整数，它通过索引标识每个可能的输入。每个巨大的整数值唯一标识一个输入。想象一下在一个巨大的表中按索引查找输入。 ceiling(log(Combination(2^32,1000)) / log(2))是该索引整数需要多少位。

更新:

我找到了一种使用现成压缩工具接近理论最佳值的方法。我排序，应用增量编码，并从中减去一个(因为连续不同元素之间的增量至少是一个)。然后诀窍是我写出所有的高字节，然后是下一个最重要的字节，等等。 deltas 的高字节减去 1 往往为零，因此将许多零组合在一起，这是标准压缩实用程序所喜欢的.此外，下一组字节往往偏向于低值。

对于示例(来自 0..2^32-1 的 1000 个统一且不同的样本)，通过 gzip -9 运行时，我平均得到 3110 个字节。 , 和 3098 字节到 xz -9 (xz 使用与 7zip 相同的压缩 LZMA)。这些非常接近理论最佳平均值 2934。此外，gzip 的开销为 18 字节，而 xz 的开销为 24 字节，无论是头部还是尾部。因此，与理论最佳值进行更公平的比较是 gzip -9 为 3092和 3074 为 xz -9 .比理论最佳值大约 5%。

更新 2:

我实现了排列的直接编码，平均达到了 2974 字节，仅比理论最佳值多出 1% 多一点。我用了 GNU multiple precision arithmetic library将每个排列的索引编码为一个巨大的整数。编码和解码的实际代码如下所示。我为 mpz_* 添加了评论从名称上看它们正在执行的算术运算可能并不明显的函数。

/* Recursively code the members in set[] between low and high (low and high
   themselves have already been coded).  First code the middle member 'mid'.
   Then recursively code the members between low and mid, and then between mid
   and high. */
local void combination_encode_between(mpz_t pack, mpz_t base,
                                      const unsigned long *set,
                                      int low, int high)
{
    int mid;

    /* compute the middle position -- if there is nothing between low and high,
       then return immediately (also in that case, verify that set[] is sorted
       in ascending order) */
    mid = (low + high) >> 1;
    if (mid == low) {
        assert(set[low] < set[high]);
        return;
    }

    /* code set[mid] into pack, and update base with the number of possible
       set[mid] values between set[low] and set[high] for the next coded
       member */
        /* pack += base * (set[mid] - set[low] - 1) */
    mpz_addmul_ui(pack, base, set[mid] - set[low] - 1);
        /* base *= set[high] - set[low] - 1 */
    mpz_mul_ui(base, base, set[high] - set[low] - 1);

    /* code the rest between low and high */
    combination_encode_between(pack, base, set, low, mid);
    combination_encode_between(pack, base, set, mid, high);
}

/* Encode the set of integers set[0..num-1], where each element is a unique
   integer in the range 0..max.  No value appears more than once in set[]
   (hence the name "set").  The elements of set[] must be sorted in ascending
   order. */
local void combination_encode(mpz_t pack, const unsigned long *set, int num,
                              unsigned long max)
{
    mpz_t base;

    /* handle degenerate cases and verify last member <= max -- code set[0]
       into pack as simply itself and set base to the number of possible set[0]
       values for coding the next member */
    if (num < 1) {
            /* pack = 0 */
        mpz_set_ui(pack, 0);
        return;
    }
        /* pack = set[0] */
    mpz_set_ui(pack, set[0]);
    if (num < 2) {
        assert(set[0] <= max);
        return;
    }
    assert(set[num - 1] <= max);
        /* base = max - num + 2 */
    mpz_init_set_ui(base, max - num + 2);

    /* code the last member of the set and update base with the number of
       possible last member values */
        /* pack += base * (set[num - 1] - set[0] - 1) */
    mpz_addmul_ui(pack, base, set[num - 1] - set[0] - 1);
        /* base *= max - set[0] */
    mpz_mul_ui(base, base, max - set[0]);

    /* encode the members between 0 and num - 1 */
    combination_encode_between(pack, base, set, 0, num - 1);
    mpz_clear(base);
}

/* Recursively decode the members in set[] between low and high (low and high
   themselves have already been decoded).  First decode the middle member
   'mid'. Then recursively decode the members between low and mid, and then
   between mid and high. */
local void combination_decode_between(mpz_t unpack, unsigned long *set,
                                      int low, int high)
{
    int mid;
    unsigned long rem;

    /* compute the middle position -- if there is nothing between low and high,
       then return immediately */
    mid = (low + high) >> 1;
    if (mid == low)
        return;

    /* extract set[mid] as the remainder of dividing unpack by the number of
       possible set[mid] values, update unpack with the quotient */
        /* div = set[high] - set[low] - 1, rem = unpack % div, unpack /= div */
    rem = mpz_fdiv_q_ui(unpack, unpack, set[high] - set[low] - 1);
    set[mid] = set[low] + 1 + rem;

    /* decode the rest between low and high */
    combination_decode_between(unpack, set, low, mid);
    combination_decode_between(unpack, set, mid, high);
}

/* Decode from pack the set of integers encoded by combination_encode(),
   putting the result in set[0..num-1].  max must be the same value used when
   encoding. */
local void combination_decode(const mpz_t pack, unsigned long *set, int num,
                              unsigned long max)
{
    mpz_t unpack;
    unsigned long rem;

    /* handle degnerate cases, returning the value of pack as the only element
       for num == 1 */
    if (num < 1)
        return;
    if (num < 2) {
            /* set[0] = (unsigned long)pack */
        set[0] = mpz_get_ui(pack);
        return;
    }

    /* extract set[0] as the remainder after dividing pack by the number of
       possible set[0] values, set unpack to the quotient */
    mpz_init(unpack);
        /* div = max - num + 2, set[0] = pack % div, unpack = pack / div */
    set[0] = mpz_fdiv_q_ui(unpack, pack, max - num + 2);

    /* extract the last member as the remainder after dividing by the number
       of possible values, taking into account the first member -- update
       unpack with the quotient */
        /* rem = unpack % max - set[0], unpack /= max - set[0] */
    rem = mpz_fdiv_q_ui(unpack, unpack, max - set[0]);
    set[num - 1] = set[0] + 1 + rem;

    /* decode the members between 0 and num - 1 */
    combination_decode_between(unpack, set, 0, num - 1);
    mpz_clear(unpack);
}

有 mpz_*函数用于将数字写入文件并读取它，或将数字导出到内存中的指定格式，然后将其导入回来。