算法精粹：经典计算机科学问题的Python实现
上QQ阅读APP看书，第一时间看更新
上一章目录下一章

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

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

数据类型占用的二进制位数要比其内容实际需要的多，只要意识到这一点，就可以产生最简单的数据压缩方案。例如，从底层考虑一下，如果一个永远不会超过65535的无符号整数在内存中被存储为64位无符号整数，其存储效率就很低。对此的替代方案可以是存储为16位无符号整数，这会让该整数实际占用的空间减少75%（64位换成了16位）。如果有数百万个这样的整数的存储效率都如此低下，那么浪费的空间累计可能会达到数兆字节。

为简单起见（当然这是一个合情合理的目标），有时候开发人员在Python里可以不用以二进制位方式来考虑问题。Python没有64位无符号整数类型，也没有16位无符号整数类型。这里只有一种int类型，可以存储任意精度的数值。用函数sys.getsizeof()可以查出Python对象占用的内存字节数。但由于Python对象系统的固有开销，在Python 3.7中无法创建少于28字节（224位）的int类型。每个int类型对象每次可以扩大1个二进制位（本例就会如此操作），但最少也要占用28字节。

注意 如果对二进制有点生疏，请记得每个二进制位就是一个1或0的值。以2为进制读出的一系列1和0就可以表示一个数。按照本节的讲解目标，不需要以2为进制进行任何数学运算，但需要理解某个数据类型的存储位数决定了它可以表示的不同数值的个数。例如，1个二进制位可以表示2个值（0或1），2个二进制位可以表示4个值（00、01、10、11），3个二进制位则可以表示8个值，以此类推。

如果某个类型需要表示的不同值的数量少于存储二进制位可表示值的数量，或许存储效率就能得以提高。不妨考虑一下DNA中组成基因的核苷酸本例受到Robert Sedgewick和Kevin Wayne的《算法（第4版）》（第819页）的启发。。每个核苷酸的值只能是这4种之一：A、C、G或T（更多相关信息将会在第2章中介绍）。如果基因用str类型存储（str可被视作Unicode字符的集合），那么每个核苷酸将由1个字符表示，每个字符通常需要8个二进制位的存储空间。如果采用二进制，则有4种可能值的类型只需要用2个二进制位来存储，00、01、10和11就是可由2个二进制位表示的4种不同值。如果A赋值为00、C赋值为01、G赋值为10、T赋值为11，那么一个核苷酸字符串所需的存储空间可以减少75%（每个核苷酸从8个二进制位减少到2个二进制位）。

因此可以不把核苷酸存储为str类型，而存储为位串（bit string）类型（如图1-5所示）。正如其名，位串就是任意长度的一系列1和0。不幸的是，Python标准库中不包含可处理任意长度位串的现成结构体。代码清单1-10中的代码将把一个由A、C、G和T组成的str转换为位串，然后再转换回str。位串存储在int类型中。因为Python中的int类型可以是任意长度，所以它可以当成任意长度的位串来使用。为了将位串类型转换回str类型，就需要实现Python的特殊方法__str__()。

图1-5 将代表基因的str压缩为每个核苷酸占2位的位串

代码清单1-10 trivial_compression.py

class CompressedGene:
def __init__(self, gene: str) -> None:
        self._compress(gene)

CompressedGene类需要给定一个代表基因中核苷酸的str字符串，内部则将核苷酸序列存储为位串。__init__()方法的主要职责是用适当的数据初始化位串结构体。_init__()将调用_compress()，将给定核苷酸str转换成位串的苦力活实际由_compress()完成。

注意，_compress()是以下划线开头的。Python没有真正的私有方法或变量的概念。所有变量和方法都可以通过反射访问到，Python对它们没有严格的强制私有策略。前导下划线只是一种约定，表示类的外部不应依赖其方法的实现。这一类方法可能会发生变化，应该被视为私有方法。

提示 如果类的方法或实例变量名用两个下划线开头，Python将会对其进行名称混淆（name mangle），通过加入盐值（salt）来改变其在实现时的名称，使其不易被其他类发现。本书用一条下划线表示“私有”变量或方法，但如果真要强调一些私有内容，或许得用两条下划线才合适。要获取有关Python命名的更多信息，参阅PEP 8中的“描述性命名风格”（Descriptive Naming Styles）部分。

下面介绍如何真正地执行压缩操作，具体代码如代码清单1-11所示。

代码清单1-11 trivial_compression.py（续）

def _compress(self, gene: str) -> None:
    self.bit_string: int = 1# start with sentinel
for nucleotide in gene.upper():
        self.bit_string <<= 2# shift left two bits
if nucleotide == "A":# change last two bits to 00
            self.bit_string |= 0b00
elif nucleotide == "C":# change last two bits to 01
            self.bit_string |= 0b01
elif nucleotide == "G":# change last two bits to 10
            self.bit_string |= 0b10
elif nucleotide == "T":# change last two bits to 11
            self.bit_string |= 0b11
else:
    raise ValueError("Invalid Nucleotide:{}".format(nucleotide))

_compress()方法将会遍历核苷酸str中的每一个字符。遇到A就把00加入位串，遇到C则加入01，依次类推。请记住，每个核苷酸需要两个二进制位，因此在加入新的核苷酸之前，要把位串向左移两位（self.bit_string<<= 2）。

添加每个核苷酸都是用“或”（|）操作进行的。当左移操作完成后，位串的右侧会加入两个0。在位运算过程中，0与其他任何值执行“或”操作（如self.bit_string | = 0b10）的结果都是把0替换为该值。换句话说，就是在位串的右侧不断加入两个新的二进制位。加入的两个位的值将视核苷酸的类型而定。

下面来实现解压方法和调用它的特殊方法__str__()，如代码清单1-12所示。

代码清单1-12 trivial_compression.py（续）

def decompress(self) -> str:
    gene: str = ""
for i in range(0, self.bit_string.bit_length() - 1, 2):# -1 to exclude sentinel
        bits: int = self.bit_string >> I & 0b11# get just 2 relevant bits
if bits == 0b00:  # A
            gene += "A"
elif bits == 0b01:# C
            gene += "C"
elif bits == 0b10:# G
            gene += "G"
elif bits == 0b11:  # T
            gene += "T"
else:
     raise ValueError("Invalid bits:{}".format(bits))
return gene[::-1]  # [::-1] reverses string by slicing backward
def __str__(self) -> str:# string representation for pretty printing
return self.decompress()

decompress()方法每次将从位串中读取两个位，再用这两个位确定要加入基因的str尾部的字符。与压缩时的读取顺序不同，解压时位的读取是自后向前进行的（从右到左而不是从左到右），因此最终的str要做一次反转（用切片表示法进行反转[::-1]）。最后请留意一下，int类型的bit_length()方法给decompress()的开发带来了很大便利。下面来试试效果吧。具体代码如代码清单1-13所示。

代码清单1-13 trivial_compression.py（续）

if __name__ == "__main__":
from sys import getsizeof
    original: str = "TAGGGATTAACCGTTATATATATATAGCCATGGATCGATTATATAGGGATTAACCGTTATA  
TATATATAGCCATGGATCGATTATA" * 100
    print("original is {} bytes".format(getsizeof(original)))
    compressed: CompressedGene = CompressedGene(original)# compress
    print("compressed is {} bytes".format(getsizeof(compressed.bit_string)))
    print(compressed)# decompress
    print("original and decompressed are the same: {}".format(original == 
     compressed.decompress()))

利用sys.getsizeof()方法，输出结果时就能显示出来，通过该压缩方案确实节省了基因数据大约75%的内存开销。具体代码如代码清单1-14所示。

代码清单1-14 trivial_compression.py的输出结果

original is 8649 bytes
compressed is 2320 bytes
TAGGGATTAACC…
original and decompressed are the same: True

注意 在CompressedGene类中，为了判断压缩方法和解压方法中的一系列条件，大量采用了if语句。因为Python没有switch语句，所以这种情况有点儿普遍。在Python中有时还会出现一种情况，就是高度依靠字典对象来代替大量的if语句，以便对一系列的条件做出处理。不妨想象一下，可以用字典对象来找出每个核苷酸对应的二进制位形式。有时字典方案的可读性会更好，但可能会带来一定的性能开销。尽管查找字典在技术上的复杂度为O (1)，但运行哈希函数存在开销，这有时会意味着字典的性能还不如一串if。是否采用字典，取决于具体的if语句做判断时需要进行什么计算。如果在关键代码段中要在多个if和查找字典中做出取舍，或许该分别对这两种方法运行一次性能测试。

上一章目录下一章