表示稀疏整数集？

Question

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

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

Answer 1

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

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

Answer 2

如果您只需要插入，删除和测试成员资格，那么散列表应该很适合您。你可以找到一些散列函数来散列32位整数here。

Answer 3

如果你想要的结构比数据集小，你应该看看某种树排列。使每个级别的4位树键从高位开始关闭2位，并且可能压缩得相当好（如果指针具有任何空间局部性）。这个技巧将足够紧凑地编码（索引到节点数组中？一个数组映射树？）。

Answer 4

一个非常紧凑的数据结构可能是bloom过滤器，也许是一个计数bloom过滤器来支持删除。

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

布隆过滤器，通过伯顿布鲁姆于1970年构思，是用于测试一个元素是否是一组的成员的空间效率的概率数据结构。假阳性是可能的，但是假阴性不是。可以将元素添加到集合中，但不能删除（尽管可以使用计数过滤器来解决此问题）