我有一个大数组(~400.000.000 个条目)，整数为 {0, 1, ..., 8}。 所以我需要每个条目 4 位。大约 200 MB。
目前我使用字节数组并在每个条目中保存 2 个数字。
不知道有没有什么好的方法，可以压缩这个数组。我进行了快速研究，发现了像 Huffmann 或 LZW 这样的算法。但是这些算法都是为了压缩数据，将压缩后的数据发送给某人并解压。
我只想有一个表，内存空间更少，所以我可以将它加载到 RAM 中。 200MB 的 table 很容易装下，但我正在考虑更大的 table 。
重要的是，我仍然能够确定某些位置的值。
有什么建议吗？
更多信息: 我只是做了一点实验，结果表明平均有 2.14 个连续数字具有相同的值。 有 1 个零，154 个一，10373 个二，385990 个三，8146188 个四，85008968 个五，265638366 个六，70791576 个七和 80 个八。 所以超过一半的数字是 6。
我只需要一个快速的 getValue(idx) 函数，setValue(idx, value) 并不重要。
最佳答案
这取决于您的数据的外观。是否有重复的条目，或者它们只是缓慢变化，还是什么？
如果是这样，您可以尝试压缩数据 block 并在需要时解压缩。 block 越大，可以节省的内存就越多，速度就越差。恕我直言，没什么好交易的。您还可以将压缩和解压缩的数据保存在内存中。
否则，即在没有规律的情况下，您至少需要 log(9) / log(2) = 3.17每个条目的位，没有什么可以改进它。
通过将 5 个数字打包到一个 short 中，您可以非常接近这个值.作为9**5 = 59049 < 65536 = 2**16 ，它几乎完美契合。你需要 3.2每个数字的位数，没有大赢家。通过这个公式给出了五个数字的打包
a + 9 * (b + 9 * (c + 9 * (d + 9 * e)))
并且通过预先计算的表可以轻松解包。
问题更新后更新
Further information: I just did a little experimenting, and it turns out, that on average 2.14 consecutive numbers have the same value. There are 1 zero, 154 ones, 10373 twos, 385990 threes, 8146188 fours, 85008968 fives, 265638366 sixes, 70791576 sevens and 80 eights. So more than half of the numbers are 6s.
平均有 2.14 个连续数字相同的事实可能会导致一些压缩，但在这种情况下它什么也没告诉我们。几乎只有五和六，所以似乎暗示遇到两个相等的连续数字。
鉴于这个事实，你可以忘记我上面的优化。实际上只有 8 个值，因为您可以单独处理单个零。因此，您只需要每个值 3 位和一个零索引。
您甚至可以创建 HashMap对于所有低于四或高于七的值，存储 1+154+10373+385990+80 个条目，每个值仅使用 2 位。但这仍然远非理想。
假设没有规律，每个值需要 1.44 位，因为这是 entropy .您可以遍历所有 5 元组，计算它们的直方图，并使用 1 个字节对 255 个最常见的元组进行编码。所有剩余的元组将映射到第 256 个值，告诉您必须查看 HashMap。对于罕见的元组值。
一些评价
我很好奇它是否可行。 5个数打包成一个字节需要85996340字节。有将近 500 万个元组不适合，所以我的想法是为它们使用 HashMap 。假设重新散列而不是链接它是有意义的，以保持它可能充满 50%，所以我们需要 1000 万个条目。假设 TIntShortHashMap (将索引映射到元组)每个条目占用 6 个字节，导致 60 MB。太糟糕了。
仅将 4 个数字打包到一个字节中会消耗 107495425 个字节并留下 159531 个不适合的元组。这看起来更好，但是，我确信更密集的包装可以改进很多。
这个小 program 产生的结果:
*** Packing 5 numbers in a byte. ***
Normal packed size: 85996340.
Number of tuples in need of special handling: 4813535.
*** Packing 4 numbers in a byte. ***
Normal packed size: 107495425.
Number of tuples in need of special handling: 159531.
关于java - 压缩数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23912035/