1.2 简单的压缩算法

无论是在虚拟世界还是现实环境，节省空间都十分重要。空间占用越少，利用率就越高，也会更节省成本。如果所租的公寓大小超过了家中人和物品所需要的空间，就可以“缩”到更便宜的小公寓去。如果数据按字节付费的方式存储在服务器上，那么压缩一下数据就可以降低存储成本。压缩就是读取数据并对其进行编码（修改格式）的操作，以便减少数据占用的空间。解压缩则是反向的过程，即将数据恢复到原始格式。

既然压缩数据的存储效率更高，那么为什么不把所有数据全都压缩了呢？这是因为需要对时间和空间进行权衡。压缩一段数据并将其解压回原始格式需要耗费一定的时间。因此，只有在对数据大小的要求优先于数据传输速度的情况下，数据压缩才有意义。想想正在通过互联网传输的大文件。压缩它们是有道理的，因为传输文件所需的时间比收到后解压缩文件所需的时间更长。此外，压缩文件以将其存储在原始服务器上所花费的时间只需计算一次。

如果能够意识到数据类型占用的二进制位数要比其内容实际需要的多，就可以想到一个最简单的数据压缩方案。例如，从底层考虑，如果一个永远不会超过32767的有符号整数在内存中存储为64位的long类型，其存储效率就很低。所以它可以存储为16位的short类型。将64位换为16位可以让该整数实际占用的空间减少75%。如果数以百万计的此类数字被低效存储，则可能会浪费多达数兆字节的空间。

在Java编程中，有时为了简单起见，开发人员无法按位思考。绝大多数Java代码都使用32位int类型来存储整数。对于绝大多数应用程序来说，这确实没有错。但是，如果要存储数百万个整数，或者需要特定精度的整数，那么可能需要考虑适合它们的类型是什么。

如果某个类型可以表示的数字数量少于用来存储它的位数可以表示的值的数量，或许存储效率就能得以提高。可以试想一下DNA中组成基因的核苷酸。每个核苷酸只能是以下4个值之一：A、C、G或T。如果将基因存储为Java字符串（可以将其视为Unicode字符的集合），则每个核苷酸将由一个字符表示，在Java中通常需要16位的存储空间（Java默认使用UTF-16编码）。二进制只需要2位来存储这种具有4个值的类型，00、01、10和11就是可以用2位表示的4个不同值。如果用00表示A，01表示C，10表示G，11表示T，那么一个核苷酸字符串所需的存储空间可以减少87.5%（每个核苷酸从16位减少到2位）。

我们可以将核苷酸存储为位串类型，而不是String（见图1.5）。正如其名，位串就是由1和0组成的任意长度的序列。幸运的是，Java标准库包含一个现成的结构，可用于处理任意长度的位串，称为BitSet。下面的代码将把A、C、G和T组成的String转换为位串，然后再转换回String。位串通过compress()方法存储在BitSet中。还需要实现一个decompress()方法来将位串转换回String类型。

CompressedGene构造函数参数中的String表示基因中的核苷酸，并在该类型内部将核苷酸序列存储为BitSet。构造函数的主要职责是使用适当的数据初始化BitSet。构造函数调用compress()来完成将给定的核苷酸字符串转换为BitSet的琐碎工作。

接下来看看压缩是如何执行的。

compress()方法会遍历核苷酸String中的每个字符。当遇到A时，就把00添加到位串。当遇到C时，就添加01，以此类推。在BitSet类中，布尔值true和false分别表示1和0。

添加每个核苷酸时，需要调用两次set()方法。也就是说，会不断地在位串的末尾添加两个新位。添加的两个位的值由核苷酸的类型决定。

最后来实现解压缩方法。

decompress()每次从位串中读取两位，再用这两位确定要将哪个字符添加到使用StringBuilder构建的基因String末尾。这两位组合在一起得到变量lastBits。lastBits是通过将第一位左移一位，然后将结果与第二位进行“或”运算（运算符为|）得到的。当一个值被向左移动时，使用<<运算符，出现的空位用0来填充。或运算表示“如果这些位中的任何一位为1，则结果为1。”因此，将secondBit与0进行“或”运算，结果始终是secondBit的值。让我们检验一下。

在main()方法中执行压缩和解压缩操作。使用equalsIgnoreCase()检查最终结果是否与原始String相同。