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

xyj

发布于 2020-07-28 14:26:47

74200

代码可运行

运行总次数：0

代码可运行

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

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-07-26，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法