Jak*_*ube 3 java compression arrays performance
我有一个大数组（~400.000.000 个条目），其中的整数为 {0, 1, ..., 8}。所以我每个条目需要 4 位。大约 200 MB。
目前我使用字节数组并在每个条目中保存 2 个数字。
我想知道，如果有一个好的方法，来压缩这个数组。我做了一个快速的研究，找到了像 Huffmann 或 LZW 这样的算法。但这些算法都是为了压缩数据，将压缩后的数据发送给某人并解压。
我只想有一个表，内存空间较少，这样我就可以将它加载到 RAM 中。200MB 的桌子很容易装下，但我正在考虑更大的桌子。
重要的是，我仍然能够确定某些位置的值。
有小费吗？
更多信息：我只是做了一些实验，结果发现平均 2.14 个连续数字具有相同的值。有 1 个零，154 个一，10373 个二，385990 个三，8146188 个四，85008968 个五，265638366 个六，70791576 个七和 80 个八。所以超过一半的数字是6s。
我只需要一个快速的 getValue(idx) 函数，setValue(idx, value) 并不重要。
这取决于您的数据的外观。是否有重复的条目，或者它们只是缓慢变化，还是什么？
如果是这样，您可以尝试压缩数据块并在需要时解压缩。块越大，可以节省的内存越多，速度越差。恕我直言，没什么好交易。您还可以将压缩和解压缩的数据保存在内存中。
否则，即在没有规律的情况下，log(9) / log(2) = 3.17每个条目至少需要位，并且没有什么可以改进它。
您可以通过将 5 个数字打包到一个short. As 9**5 = 59049 < 65536 = 2**16，它几乎完美契合。你需要3.2每个数字位，没有大的胜利。通过这个公式给出五个数字的包装
a + 9 * (b + 9 * (c + 9 * (d + 9 * e)))
并且通过预先计算的表解包是微不足道的。
更多信息：我只是做了一些实验，结果发现平均 2.14 个连续数字具有相同的值。有 1 个零，154 个一，10373 个二，385990 个三，8146188 个四，85008968 个五，265638366 个六，70791576 个七和 80 个八。所以超过一半的数字是6s。
平均有大约 2.14 个连续数字相同的事实可能会导致一些压缩，但在这种情况下，它什么也没说。几乎只有 5 和 6，因此似乎暗示遇到两个相等的连续数字。
鉴于这个事实，你可以忘记我上面的优化。实际上只有 8 个值，因为您可以单独处理单个零。所以每个值只需要 3 位，零只需要一个索引。
您甚至可以HashMap为低于 4 或高于 7 的所有值创建一个，在那里存储 1+154+10373+385990+80 个条目并且每个值仅使用 2 位。但这仍然远非理想。
假设没有规律，每个值需要 1.44 位，因为这是entropy。您可以遍历所有 5 元组，计算它们的直方图，并使用 1 个字节对 255 个最常见的元组进行编码。所有剩余的元组将映射到第 256 个值，告诉您必须在 a 中HashMap查找稀有元组值。
我很好奇它是否可以工作。将 5 个数字打包为一个字节需要 85996340 个字节。有将近 500 万个元组不适合，所以我的想法是为它们使用哈希映射。假设重新散列而不是链接它可能保持 50% 已满是有意义的，所以我们需要 1000 万个条目。假设TIntShortHashMap（将索引映射到元组）每个条目占用 6 个字节，导致 60 MB。太糟糕了。
仅将 4 个数字打包成一个字节会消耗 107495425 个字节并留下 159531 个不适合的元组。这看起来更好，但是，我相信更密集的包装可以改进很多。
这个小程序产生的结果：
*** 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.