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 Sub
Private 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 If
End 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 = Nothing
End Function举报
腾讯云开发者
