algorithm - 表示稀疏整数集？

Question

以紧凑和快速的方式表示稀疏整数集（真正的 C 内存地址）的好方法是什么。我已经知道诸如位向量和游程编码之类的显而易见的事情。但我想要比每个集合元素一个单词更紧凑的东西。我需要添加和删除元素并测试成员资格。我不需要其他集合操作，比如联合。

多年前我读过一个这样的图书馆，但后来忘记了它的名字。我认为它是由惠普作为开源发布的，并且有一个女人的名字。

Answer 1

您指的是一个 judy 数组。这是一个惠普项目。我认为它们在 ruby​​ 中使用并且在 c 中可用。非常有趣的数据结构。利用分配（至少）字对齐的事实，具有用于密集和稀疏范围的单独结构。

http://judy.sourceforge.net/index.html

Answer 2

一个非常紧凑的数据结构将是一个布隆过滤器，也许是一个支持删除的计数布隆过滤器。

http://en.wikipedia.org/wiki/Bloom_filter

Bloom 过滤器由 Burton H. Bloom 在 1970 年构思，是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。假阳性是可能的，但假阴性是不可能的。元素可以添加到集合中，但不能删除（尽管这可以通过计数过滤器解决）

Answer 3

如果您只需要插入、删除和测试成员资格，那么哈希表应该很适合您。您可以在此处找到一些用于散列 32 位整数的良好散列函数。

Answer 4

如果您希望结构小于数据集，则可能应该查看某种树形排列。使 4 路的每个级别的树键从高端开始的 2 位开始，它可能会很好地压缩（如果指针具有任何程度的空间局部性）。诀窍是将其编码得足够紧凑（索引到节点数组？数组映射树？）。