如何压缩严格递增的 Long 序列

Question

压缩（已排序）单调递增长整型序列的最佳方法是什么？

序列的特点：

• 所有值都是唯一的（不重复）
• 序列长度的范围可以从非常小（3 个数字）到极大（100k 个数字）
• 数字通常非常接近（几乎连续），但随后突然大幅跳跃 例如1、2、3、1000、1001、1002、15001、15002
• 序列不是有限的，应该有一个插入操作来将新数字添加到序列中，该序列也应该被压缩

目标：

• 将序列压缩得尽可能小

我尝试过什么：

• 对于接近的数字来说，Delta 编码似乎是个好主意。但是，我不知道如何打包这些增量值的位。
• 计算增量，然后对增量数组进行霍夫曼编码。我认为这不会提供最佳的压缩，Java 中的字符需要 2 个字节，而且我还必须存储哈夫曼树
• SIMD操作：尝试阅读lemire关于SIMD压缩的文章，但发现很难在Java中理解和实现
• 游程长度编码不起作用，因为所有数字都是唯一的

Answer 1

Delta 编码是一个好的开始。然后使用可变长度整数对增量进行编码。然后使用标准无损压缩器。