如何制作排序的长压缩数据结构？

Question

如何创建一个压缩长整型排序数组的集合数据结构？

目标：

必须支持以下操作：

• 插入新号码
• 删除某个值
• 与另一组相交
• 另一组的并集
• 序列应该消耗尽可能少的内存

序列的特点：

• 源自倒排索引的倒排列表
• 所有号码都是唯一的（不重复）
• 64 位长整型
• 序列的原始输入长度范围可以从非常小（3 个数字）到极大（100k 个数字）
• 数字通常非常接近（几乎连续），但随后突然大幅跳跃 例如1、2、3、1000、1001、1002、15001、15002

我的想法：

• 创建基于红黑的集合数据结构，支持插入/删除/相交/并集
• 数字将表示为树中的节点。但这会比原来的数组消耗更多的空间！我将如何压缩它们并在需要时允许插入（压缩）和删除（从压缩序列中删除）

Answer 1

这些数字通常非常接近（几乎连续），但是 然后突然大跳

我会尝试一个简单的位图（按位置，1 表示它在集合中，0 表示不在集合中），其中 0 位游程长度压缩的长序列。这将能够非常快速地设置和取消设置位，以及使用位运算进行交集和并集。