解压zip_VBA解压缩ZIP文件06——Huffman树码表

Huffman树创建出来之后，自然需要用到它的码表，码表的意思就是通过一串bit能够找到叶子节点，然后这串bit对应的就是叶子节点Key，Huffman树每个叶子节点都有一串与之对应的bit，而且因为Huffman树的特殊，某一个短的bit串都不可能会是其他长串的前缀，比如下面这个码表：

bit	Key
00	8
010	0
011	5
100	6
101	7
1100	4
1101	9
1110	17
11110	18
111110	3
111111	16

如果想查看自己创建的Huffman树的码表，只需要写个简单的递归函数打印出来：

Public Sub PrintOut()    RPrintOut root, ""End SubPrivate Function RPrintOut(n As CNode, str As String)    If n.Weight = 2 Then        Debug.Print str, n.Key                Exit Function    Else        RPrintOut n.Left, str & "0"        RPrintOut n.Right, str & "1"    End IfEnd Function

注意我这里用来判断是否是叶子节点的条件If n.Weight = 2 Then，在前面创建的过程介绍过，为了创建方便，每一个初始的节点都设置Weight = 2，然后进行左右子树的扩展，扩展的时候节点的Weight-1，只有叶子节点是没有扩展左右子树的，所以Huffman中只有叶子节点的Weight = 2。

当然这里也可以去判断左右子树是否同时为Nothing。

但我们在解压数据的时候，是从压缩数据流中一个一个bit的去读取的，如果先记录下码表，就需要不停的判断已读出的bit串是否出现在码表中，需要较多的比较次数。

在Huffman树这个结构中，完全是没有那个必要的，需要做的是好好利用Huffman树：

• 1、节点n从根节点开始

• 2、从压缩数据流中读取一个bit，如果是0，n指向n.Left，如果是1，n指向n.Right

• 3、判断n是否是叶子节点，如果是返回n.Key，否则，重复2-3

逻辑其实挺简单的，代码实现：

'找到叶子节点的Key'从bitIndex位置，逐个读取cpByte中的Bit，直到叶子节点Function GetLeafKey(cpByte() As Byte, ByRef bitIndex As Long) As Long    Dim bValue As Long    Dim n As CNode    Set n = root        'HuffmanTree里把叶子节点的Weight设置成了2    Do Until n.Weight = 2        '逐个bit的去h中查找，到达叶子节点为止        bValue = GetBit(cpByte, bitIndex)        bitIndex = bitIndex + 1        '1的时候右        If bValue Then            Set n = n.Right        Else            Set n = n.Left        End If    Loop        GetLeafKey = n.Key        Set n = NothingEnd Function

• 00 ZIP是什么

• 01 实现的功能

• 02 压缩过程

• 03 解压准备工作

• 04 解析ZIP文件结构

• 05 Huffman树