阿征DNA

书接上回，做完 BitList 后做哈夫曼树就容易了一些。上结构体：

type HuffTree struct {
	Val         byte
	Weight      int
	Left, Right *HuffTree
}

因为 base64 编码中出现的 asc2 码最大的字符是 z，所以用一个长度为 'z' + 1 的数组作为哈希表统计字符串中各字符出现的频率，然后对数组进行排序。使用了一个实现 sort.Interface 接口的结构体进行排序。

type huffQue struct {
	len  int
	elem []*HuffTree
}

// Len 实现 sort.interface 用于排序
func (q *huffQue) Len() int {
	return len(q.elem)
}

func (q *huffQue) Less(i, j int) bool {
	if q.elem[i] == nil {
		if q.elem[j] == nil {
			return true
		} else {
			return false
		}
	} else if q.elem[j] == nil {
		return true
	}
	return q.elem[i].Weight < q.elem[j].Weight
}

func (q *huffQue) Swap(i, j int) {
	q.elem[i], q.elem[j] = q.elem[j], q.elem[i]
}

再把排序的结果中为空的元素切掉。在排序的过程中为空的元素会被移到数组最后所以直接取前 n 个就行。接下来就是构造哈夫曼树。取前两个元素组合成树，插入队尾，排序，直到只剩最后一个元素，就是树的头节点。

哈夫曼树有了，还需要有 Decode 和 Encode 方法。为了 Eecode 方法我还实现了 SearchCode 方法来查找字符对应的哈夫曼编码。Decode 方法没啥好说的，就遍历了哈夫曼树，遍历到叶子节点就说明找到了一个字符。

接下来就只剩把哈夫曼树序列化了。肯定不能用 JSON 来序列化，因为哈夫曼树要和压缩过的文件一起写到新的文件里面。使用 JSON 序列化的体积太大了。想了一下还是决定用至少 3 个字节来存每一个结点。第一个字节存字符，第二个字节存哈夫曼编码的长度，第三个字节及后面的空间存哈夫曼编码。为啥不存 字符 + 权重 呢，字符 + 权重 总共占 5 个字节，而 65 个字符的 base64 编码形成的哈夫曼树最长只有 7 位。也就是说在这种场景下存 字符 + 哈夫曼编码长度 + 哈夫曼编码 比 字符 + 权重 节省 2 个字节，也就是 40% 的空间。

到了测试阶段，程序员最讨厌的三件事之一（写注释，写测试，写文档）。卧槽出 bug 了，序列化后的哈夫曼编码对不上。于是我进入了漫长的断点调试，过程都没问题，但是结果却出错了。用一个 BitList 存哈夫曼编码，往 BitList 里面 push 一个 0，遍历左子树，再把 0 pop 出来，push 一个 1，遍历右子树，再把 1 pop 出来。如果碰到叶子结点就把 BitList 里的哈夫曼编码输出到字节流里。这个递归流程是没毛病的，问题出在哈夫曼编码不对。最后定位到是 BitList 的 Pop 方法出问题，只是单纯的把长度减 1，没有进行移位操作，而 Push 方法是会把数据往左移 1 位的，就导致了哈夫曼编码的不正确。

修了那个 bug 之后啥 bug 都没有了，我都不敢相信这是真的。

于是开始实现我的最终目的——压缩文件！找来了 251 KB、656 KB、16.4 MB 的三张图片，看看经过转 base64 后又被哈夫曼树压缩的文件是否会比源文件小，实测转换后比原图大了 0.3 % 左右。居然没有变小吗，不过对比 base64 编码的文件确实小了很多。上表格：

感觉 base64 编码里的字符频率分布还是比较均匀的，没有完全发挥哈夫曼编码的长处啊。

2022-07-26