代码之家 › 专栏 › 技术社区 › Laughcheeta1

Java BitSet.size()没有返回我在构造函数中给出的大小

bitset bit java

Laughcheeta1 · 技术社区 · 3 年前

我有以下代码:

 private BitSet arrayListToBitSet(ArrayList<Boolean> code) {
                // The problem is here, the bitset automatically is created using 64 bits even tho we are clearly 
                    // giving it a max size in constructor, and in the test we are running,
                    // we are only using 9 bits, leading to the rest of the bits being automatically 0, so we need to
                    // search for a way that the size of the bitset is exactly the size of the array list "code"
                int x = code.size(); // With the test I'm running, x = 9;
                BitSet bitset = new BitSet(x);
                System.out.println(bitset.size());
        
                for (int i = 0; i < x; i++)
                {
                    bitset.set(i, code.get(i));
                }
        
                return bitset;
        }

控制台上的System.out.println()显示64,尽管它应该只显示9。

即使我把9硬编码到BitSet的构造函数中,它仍然返回比特集的大小是64。当我正在制作一个压缩.txt文件的程序时,使用布尔值的BitSets整数对我来说至关重要,或者如果有人知道在java中操作单个位的另一种方法,这也会很有帮助。

在BitSet.size()的文档中,只说了以下内容

public int size()
Returns the number of bits of space actually in use by this BitSet to represent bit values. The maximum element in the set is the size - 1st element.
Returns:
the number of bits currently in this bit set

文档。神谕

这对我的问题没有多大帮助。有人知道发生这种情况的原因吗?以及如何修复?非常感谢。

更多上下文: 我正在做的是实现huffman算法,将给定的.txt文件压缩到一个名为“CompressedFile”的新类中,该类将存储在pc内存中。

在上面的方法之前,我们对文本中的字符进行计数,并将它们保存到哈希图中,然后使用这个哈希图创建霍夫曼树,一旦我们有了霍夫曼树,我们就用它来为文本中的每个字符进行霍夫曼编码,给定字符的每个代码都保存在具有以下值对的另一个哈希图中:

(char,ArrayList),由于BitSet的问题,该代码目前是布尔值的ArrayList。

一旦我们有了这个,我们就把这个HashMap交给另一个创建“encodedText”的函数,这是一个存储tex编码版本的ArrayList,我们通过遍历.txt中的每个字符,并将该字符的编码值添加到“encode_Text”变量中来实现这一点(记住,一个字符的编码值也保存为HashMap中的ArrayList)。

一旦我们有了完整的霍夫曼代码,也就是这个arrayListToBitSet方法发挥作用的地方,它将ArrayList版本中的encodedText转换为BitSet版本,也就是将存储在CompressedText类中的版本。

我们用于测试的.txt文件如下:“aaabc”

在获得霍夫曼树并获得每个字符编码版本后,值对如下所示(我将使用0和1,以免写True和False):

(a,0) (b,11) (c,10)

因此,文本的encodedVersion将如下所示: 000111110

当这个ArrayList转换为BitSet时,输出(我将BitSet打印到控制台)如下所示: 0001111100000000000…(另42个ceros)。。。00

所以前9个比特是正确的,但后面的53个比特不应该在那里,并且是cero。如果我把它留成这样,这就是解码后的文本的样子:

aabbcaaaaaaaaaaa。。。

与原作大不相同。解决此问题的一种方法是在CompressFile类中包含编码消息的正确大小,因此当我解压缩它时,我只检查确切的位数,但我想知道是否有一种方法不必在类中保存这个整数(这将为我节省8个字节,在总体方案中不会太多,变成8个字符,但目的是使用尽可能少的内存)。尽管如此,如果没有其他方法,我还是会将原始大小放入CompressedFile类中。

提前感谢您的帮助:)

4 回复 | 直到 3 年前

Sweeper 3 年前

注意构造函数的 documentation 说:

创建初始大小足够大的位集,以显式表示索引在范围内的位 0 通过 nbits-1 。

短语“足够大”是这里的关键。此构造函数不应创建 确切地 你指定的尺寸-只是 足够大 以存储您指定的位数。

还要注意课堂文档中的这一段:

每个比特集都有一个当前大小,即比特集当前使用的空间比特数。请注意,大小与位集的实现有关,因此它可能会随着实现而变化。

BitSet ,至少在OpenJDK中,是通过使用 long[] 。这就解释了为什么你会看到64。要创建一个“足够大”以存储9个比特的比特集,它至少可以分配一个 长[] 长度为1。单个 long 是64位。

我不认为是偶数 可能的 在JVM中实现一个可以存储 确切地 9位。即使您使用 boolean[] 支持它,每个 boolean 仍然是一个字节(您可能已经知道了)。

因此,拥有额外的cero可能会导致在文件的解压缩版本中添加更多的字符

如果是这种情况,您可以查看 length 的 位集合 。它给出了位集中有多少位,减去前导的零位。

user555045 3 年前

解决此问题的一种方法是在CompressFile类中包含编码消息的正确大小,因此当我解压缩它时,我只检查确切的位数

您至少需要以下其中一项:

未压缩文件中的字符数,无论如何都很好。
一种“结束”符号,不与任何字符对应,但发出停止解码的信号。
编码比特的确切数量,但使用它更麻烦。

编码比特的数量可能不会完全填满字节数(也不会像 long s) ,所以结尾可能会有一些额外的比特,它们不会编码任何内容,但它们可能会意外地看起来像有效的霍夫曼代码。所以你需要某物告诉你在哪里停下来。

a. BitSet 不记得它的“确切长度” length 方法忽略前导零,即使它们是部分数据,但 位集合 加上一个额外的整数( 长的 如果你愿意)可以工作。或者,正如Johannes Kuhn所提到的,你可以预先准备一个不属于实际数据的额外集合位 长 将工作(当然,记得在解压过程中忽略多余的部分)。

一旦我们有了这个,我们就把这个HashMap交给另一个创建“encodedText”的函数,这是一个存储tex编码版本的ArrayList,我们通过遍历.txt中的每个字符,并将该字符的编码值添加到“encode_Text”变量中来实现这一点(记住,一个字符的编码值也保存为HashMap中的ArrayList)。

您应该避免至少创建表示整个压缩数据的大型ArrayList,因为它将比它所表示的实际数据大得多(它使用一个 Boolean 毕竟每比特)。

如果您将位填充到字节/整数/a中 位集合 虽然将字符转换为其编码值,不再有“临时扩展”。

推杆 ArrayList<Boolean> 和 位集合 暂且不谈,如果您将代码表示为整数对,使用一个整数表示代码的长度,另一个整数存储代码的位,则可以有效地对数据进行编码,而无需进行任何逐位迭代。这将代码的长度限制为最多32(如果使用,则为64 长的 ),但高效的基于表的解码也需要限制,而且良好的压缩不需要很长的代码,32的限制已经足够了方法在收益递减的情况下,小得多的限制在实践中很常见(例如16),你会从转换到 ANS 正如几种现代压缩格式所具有的那样。

Reilas 3 年前

为了快速回答您的第一个问题 BitSet 正在创建一个大于您请求的数量的集合,这是因为没有明确的方法来表示1位内存。
以这种速度,即使是 boolean 占用了1个字节的空间,尽管可以说只需要1个比特。
所以,看起来 位集合 正在使用 long 以存储值。

如果这与您所需的逻辑太偏离,您可以尝试创建自己的类,并根据需要实现过程。

这取决于您打算如何使用这些钻头。

你提到了以下内容。

我正在制作一个压缩.txt文件的程序,使用布尔值的BitSets对我来说至关重要,如果有人知道在java中操作单个位的另一种方法,这也会很有帮助。

位集合 本质上就是你想要的课程。

Laughcheeta1 3 年前

正如我在这个问题的上下文中所暗示的,我决定使用一个额外的int变量来跟踪我正在使用的比特数量,因为没有其他方法不影响霍夫曼算法来解决这个问题。

请注意,这是一个仅适用于此特定情况的解决方案,它不是解决BitSet.size()方法不返回数组实际大小的问题的方法。由于没有解决这个问题的方法,请慢慢阅读帖子上的评论,特别是因为它们对BitSets的工作原理做出了令人敬畏的解释,并可能对您的情况有所帮助。