用短的编码表示出现频率高的字符,用长的编码来表示出现频率低的字符
,因此首先要做的就是统计字符的出现频率,然后根据统计的频率来构建 Huffman 树(又叫最优二叉树)。如果计算机使用三进制,而不是二进制,那么 huffman 树就应该是一个三叉树。
选取两个权值最小的节点
,并添加一个权值为 5+9=14 的节点,作为他们的父节点。并更新最小堆
,现在最小堆包含 5 个节点,其中 4 个树还是原来的节点,权值为 5 和 9 的节点合并为一个。AAAAABBBBCCC
整体看成一个子序列,这样编码的长度就有所编码。究竟使用哪种方法,取决于压缩的时间和压缩的比例等。 更复杂的情况还有很多,这里不做扩展。这也是我们图片倾向于纯色的时候,压缩会有很好的效果