比特阵列有哪些替代方案？

Question

我有一个信息检索应用程序,它创建大小为10万位的位数组.数组中"set"位的数量变化很大,从所有清除到全部设置.目前,我正在使用直接位数组(java.util.BitSet),因此我的每个位数组都需要几兆字节.

我的计划是查看前N位的基数,然后决定使用哪些数据结构用于余数.显然,对于非常稀疏的位阵列,一些数据结构更好,而当大约一半的位被设置时,其他数据结构更好(当大多数位被设置时,我可以使用否定将其视为稀疏的零集合).

• 什么结构可能在每个极端都很好？
• 中间有没有？

以下是一些约束或提示:

1. 这些位仅按索引顺序设置一次.
2. 我需要100%的准确度,所以像Bloom过滤器这样的东西还不够好.
3. 在构建集之后,我需要能够有效地迭代"set"位.
4. 这些位是随机分布的,因此运行长度编码算法不可能比简单的位索引列表好得多.
5. 我正在尝试优化内存利用率,但速度仍然有一些重量.

使用开源Java实现的东西是有帮助的,但不是绝对必要的.我对基本面更感兴趣.

Answer 1

除非数据是真正随机的,并具有对称的1/0分布,然后这简单地变成无损数据压缩问题,并且非常类似于用于黑白(即:二进制)FAX图像的CCITT Group 3压缩.CCITT Group 3使用霍夫曼编码方案.在传真的情况下,他们使用一组固定的霍夫曼码,但对于给定的数据集,您可以为每个数据集生成一组特定的代码,以提高实现的压缩比.只要您只需按顺序访问位,就像您暗示的那样,这将是一种非常有效的方法.随机访问会产生一些额外的挑战,但您可能会生成一个二进制搜索树索引到数组中的各种偏移点,这将允许您接近所需的位置,然后从那里进入.

注意:即使数据是随机的,霍夫曼方案仍然可以正常工作,只要1/0分布不是完全均匀的.也就是说,分布越不均匀,压缩比越好.

最后,如果比特是真正随机的,均匀分布,那么,根据克劳德·香农先生的说法,你无法使用任何方案压缩任何大量的数据.