compression - 使用素数压缩

Question

我想我已经找到了一种方法，您可以使用素数进行无损压缩或一遍又一遍地使用其他方法。

在 0-255 范围内有 54 个素数。当我们在字节数组中有素数时，我们可以使用该数的素数索引来存储它，使用 6 位而不是 8 位，对吗？

我们需要为每个字节创建一个映射，我们可以存储我们正在压缩的数字，并将其添加到数据数组中。

起初这似乎有效，但略微增加了文件大小，但将文件减小为可重新压缩的结构，适用于 LZ4 或 Huffman 等算法。

索引 0-53 对应于素数 2-251，但有 6 位未使用的数字。（54-63）。这 10 个数字也可以作为存储 10 个不同非质数的机会，频率最高的 6 位。所以我们要挤更多的数字。如果这个比率超过 50%，我们将能够执行成功的压缩。

此外，这种方法可以创造重新压缩压缩数字的机会。你认为如果我们在 4 或 8 字节数据块而不是一个字节中创建 uint 和 ulong 数据类型的方法，我们可以将压缩数据的映射缩小到更小的大小，对吗？

有 203280221 个小于 2 ^ 32 的素数。这意味着我们可以为每个素数存储 28 位而不是 32 位。

通过查看数据数组中素数的比率，我们可以确定是否可以执行有效的压缩。

我认为这种方法不是一种有效的压缩方法，而是一种可能允许重新压缩压缩文件的数据交换。

我想问你知道我们可以用素数做的其他方法吗？因为获得素数非常容易，尤其是对于 2 ^ 32 以下的数字。我们需要在我们的方法中添加素数方法。

标签： compressionprimes

Answer 1

一种有效且实用的 32 位素数压缩方法是使用简单的 8 位字节存储连续素数之间的减半差异（并在需要时将素数 2 凭空取出）。借助一些索引魔术，这可以提供超快的“解压缩”-即，当需要对素数范围进行迭代时，它是一种理想的表示形式，因为它比普通素数使用更少的内存。

2^32 以下的 203,280,220 个奇数素数需要相应的字节数，即略小于 194 MB。字节大小减半差异的可用性扩展到 304,599,508,537（大约 2^38），但从那时起，有必要发明一种编码偶尔大于 510 的间隙的方案。但是，当存储间隙索引而不是减半间隙宽度时，则计划几乎可以永远持续下去（参见Prime 差距文章 @ Wikipedia）。

可以使用通常的 zlib-stile 压缩或类似方法进一步压缩这些连续差异块，在这种情况下，您将获得比压缩仅打包赔率位图或 mod 30 轮更好的压缩。这可以用作紧凑的磁盘表示。

但是请注意，mod 30 轮仅占用 136 MB，并且可以直接索引 - 就像满足素数查询一样。提取（解码）素数范围比使用 delta 编码的素数要慢很多，但仍然比重新筛选素数要快。因此，使用 mod 30 轮存储素数是“压缩”素数​​的最有效方法之一，以保持它们直接可用/可用。

混合形式也可以非常成功。例如，在从 mod 30 轮解码质数时，您可以将它们直接以 delta 编码形式存储，而无需将它们具体化为数字向量。这可以被视为一种重新压缩的形式。mod 30 轮将是磁盘和主内存格式，增量编码将是某些查询结果的交换格式。

Delta 编码和轮式存储共享一个重要的优势：它们的存储需求基本上与表示的素数的大小无关。相比之下，如果将素数存储为数字，则存储需求会以对数方式增加。即 64 位素数占用的空间是 16 位素数的四倍。

可以在 Wikipedia 文章Wheel factorization中找到对主轮的解释。

下表显示了在向轮子中添加越来越多的素数时所获得的空间减少，无论是相对于无轮表示（'ratio'）还是相对于前面的步骤（'delta'）。'spokes' 列给出了每个车轮旋转时潜在的主轴承辐条（残差）的数量，这让您了解优化的、完全展开的实施的复杂性，就像 Kim Walisch 的primesieve 一样。如您所见，收益正在迅速减少，而复杂性却在爆炸式增长。

Wheel mod 2 - 也就是仅赔率的筛子 - 很重要，因为它可以为您提供大部分的收益，而几乎没有代码复杂性的成本。在操作仅赔率的筛子时，几乎不费吹灰之力就可以通过花招（索引技巧）获得 mod 3 轮的大部分速度优势。wheel mod 30 很重要，因为它在代码复杂性和加速之间提供了良好的平衡，这使其成为优化实现的理想目标。高达 mod 30030 的车轮已在实际实施中使用，但与 mod 30 车轮相比的增益实际上可以忽略不计，而增加的复杂性和性能损失则不然。在特殊项目的背景下，在大学校园中甚至可以看到更高阶的轮子。

Kim Walisch 的筛子程序是您在网上任何地方都能找到的最快的原因之一是，他实现了 mod 30 轮的 8 个可能的跨步序列中每一个的展开版本，每个 8 个都有特定的循环入口点每个序列的可能阶段。所有这些都是在唯一一种语言 (C/C++) 中，您可以获得真正名副其实的优化编译器。

对 wheel mod 210 的 48 个残基执行相同操作将意味着代码量增加 36 倍（！），而位图大小的减少可以忽略不计。但是，如果您有几个月的空闲时间可以燃烧，那么 mod 210 和 mod 2310 可能是代码生成器（C/C++ 代码或 .NET IL）的有希望的目标。