06-优化列表压缩算法

5.5　优化列表压缩算法

假设有一些数据需要压缩，并假设数据项组成了一个列表，我们不关注数据项的顺序，只要数据项完整就可以。数据项以什么样的顺序排列能将压缩比最大化呢？你知道数据项的排列顺序会影响大多数压缩算法的压缩比吗？

答案将取决于所使用的压缩算法。本示例将以标准设置用 zlib 模块中的 compress() 函数进行压缩。代码清单5-13完整展示了对于12个人名的列表的解法。如果不运行遗传算法，而只是按照12个人名的初始顺序对它们运行 compress() ，则生成的压缩数据将有165字节。

代码清单5-13　list_compression.py

from __future__ import annotations
from typing import Tuple, List, Any
from chromosome import Chromosome
from genetic_algorithm import GeneticAlgorithm
from random import shuffle, sample
from copy import deepcopy
from zlib import compress
from sys import getsizeof
from pickle import dumps
# 165 bytes compressed
PEOPLE: List[str] = ["Michael", "Sarah", "Joshua", "Narine", "David", "Sajid", "Melanie",
     "Daniel", "Wei", "Dean", "Brian", "Murat", "Lisa"] 
class ListCompression(Chromosome):
    def __init__(self, lst: List[Any]) -> None:
        self.lst: List[Any] = lst
    @property
    def bytes_compressed(self) -> int:
        return getsizeof(compress(dumps(self.lst)))
    def fitness(self) -> float:
        return 1 / self.bytes_compressed
    @classmethod
    def random_instance(cls) -> ListCompression:
        mylst: List[str] = deepcopy(PEOPLE)
        shuffle(mylst)
        return ListCompression(mylst)
    def crossover(self, other: ListCompression) -> Tuple[ListCompression, ListCompression]:
        child1: ListCompression = deepcopy(self)
        child2: ListCompression = deepcopy(other)
        idx1, idx2 = sample(range(len(self.lst)), k=2)
        l1, l2 = child1.lst[idx1], child2.lst[idx2]
        child1.lst[child1.lst.index(l2)], child1.lst[idx2] = child1.lst[idx2], l2
        child2.lst[child2.lst.index(l1)], child2.lst[idx1] = child2.lst[idx1], l1
        return child1, child2
    def mutate(self) -> None: # swap two locations
        idx1, idx2 = sample(range(len(self.lst)), k=2)
        self.lst[idx1], self.lst[idx2] = self.lst[idx2], self.lst[idx1]
    def __str__(self) -> str:
        return f"Order: {self.lst} Bytes: {self.bytes_compressed}"
if __name__ == "__main__":
    initial_population: List[ListCompression] = [ListCompression.random_instance()
     for _ in range(1000)]
    ga: GeneticAlgorithm[ListCompression] = GeneticAlgorithm(initial_population=
     initial_population, threshold=1.0, max_generations = 1000, mutation_chance =
     0.2, crossover_chance = 0.7, selection_type=GeneticAlgorithm.SelectionType.TOURNAMENT)
    result: ListCompression = ga.run()
    print(result)

注意，代码清单5-13中的代码与5.4节中SEND+MORE=MONEY问题的实现代码非常相似。 crossover() 函数和 mutate() 函数基本相同。在这两个问题的求解方案中，都会以数据项列表为参数，不断对列表进行重排并测试。可以为两个问题的求解方案编写一个通用的超类，使其适用于多种不同的问题。任何可以用数据项列表来表示且需要找到数据项的最优顺序的问题，都可以用同样的方案进行求解。对于子类唯一需要定制的就是各自的适应度函数。

list_compression.py可能需要很长时间才能运行完毕。因为与之前的两个问题不同，我们事先不知道“正确”答案的构成，所以没有真正的阈值作为运行方向。这里任意设置代的数量和每代的个体数，以期能获得最佳答案。重新排列12个人名将让压缩生成的最少字节数是多少？坦率地说，答案是未知的。本人用上述配置完成的最好的一次运行，是在546代之后，遗传算法为12个人名找到了一种顺序，可以压缩生成159字节。

这只比原始顺序节省了6字节（约节省4%）。有人可能会说4%无关紧要，但如果这是一个庞大得多的列表，且要在网络上传输多次，就很有意义了。想象一下，如果是一个最终要在互联网上传输10 000 000次的1 MB大小的列表。如果遗传算法可以优化列表的顺序，使得在压缩时能节省4%的空间，则每次传输可节省约40 KB，最终总共可节省400 GB的带宽。虽然这个数量并不算大，但是或许足以说明为了找到接近最优的压缩顺序而运行一次本算法是划算的。

请考虑一点，其实我们不知道是否已找到12个人名的最佳顺序，更不用说假定的1 MB大小的列表了。怎样才能知道我们是否达到目标了呢？除非对压缩算法有深入的了解，否则就得试着把每种顺序的列表都压缩一遍。这对于仅有12个数据项的列表就很难实现，因为有479 001 600（12!，“!”表示阶乘）种可能的顺序。即便不知道最终得到的是否真的是最优解，采用尽力接近最优的遗传算法也是比较可行的方案。