Python描述数据结构之哈夫曼树篇

时间:2020-9-7 作者:admin


前言

  本篇章主要介绍哈夫曼树及哈夫曼编码,包括哈夫曼树的一些基本概念、构造、代码实现以及哈夫曼编码,并用Python实现。

1. 基本概念

  哈夫曼树

(Huffman(Huffman

Tree)Tree)

,又称为最优二叉树,指的是带权路径长度最小的二叉树。树的带权路径常记作:

WPL=k=1nwklkWPL=\sum _{k=1} ^ {n} w_kl_k

  其中,

nn

为树中叶子结点的数目,

wkw_k

为第

kk

个叶子结点的权值,

lkl_k

为第

kk

个叶子结点与根结点的路径长度。

  带权路径长度是带权结点和根结点之间的路径长度与该结点的权值的乘积。有关带权结点、路径长度的概念请参阅这篇博客

  对于含有

nn

个叶子结点的哈夫曼树,其共有

2n12n-1

个结点。因为在构造哈夫曼树的过程中,每次都是以两颗二叉树为子树创建一棵新的二叉树,因此哈夫曼树中不存在度为1的结点,即

n1=0n_1=0

,由二叉树的性质可知,叶子结点数目

n0=n2+1n_0=n_2+1

,所以

n2=n01n_2=n_0-1

,总结点数目为

n=n0+n1+n2=n+n1=2n1n=n_0+n_1+n_2=n+n-1=2n-1

2. 构造过程及实现

  给定

nn

棵仅含根结点的二叉树

T1,T2,,TnT_1,T_2,\dots,T_n

,它们的权值分别为

w1,w2,,wnw_1,w_2,\dots,w_n

,将它们放入到一个集合

FF

中,即

F={T1,T2,,Tn}F=\{T_1,T_2,\dots,T_n\}

;然后在集合

FF

中选取两棵权值最小的根结点构造一棵新的二叉树,使新二叉树的根结点的权值等于其左、右子树根结点的权值之和;再然后将选中的那两个结点从集合

FF

中删除,将新的二叉树添加到

FF

中;继续重复上述操作,直至集合

FF

中只剩一棵二叉树为止。
  比如

F={(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)}F=\{(A,3),(B,7),(C,2),(D,11),(E,13),(F,15),(G,9)\}

,它构造出来的哈夫曼树就是下面这棵二叉树:

Python描述数据结构之哈夫曼树篇

  代码实现:

class HuffmanTreeNode(object):
    def __init__(self):
        self.data = '#'
        self.weight = -1
        self.parent = None
        self.lchild = None
        self.rchild = None


class HuffmanTree(object):
    def __init__(self, data_list):
        self.nodes = []
        # 按权重从大到小进行排列
        for val in data_list:
            newnode = HuffmanTreeNode()
            newnode.data = val[0]
            newnode.weight = val[1]
            self.nodes.append(newnode)
        self.nodes = sorted(self.nodes, key=lambda node: node.weight, reverse=True)
        print([(node.data, node.weight) for node in self.nodes])

    def CreateHuffmanTree(self):
        # 这里注意区分
        # TreeNode = self.nodes[:]  变量TreeNode, 这个相当于深拷贝, TreeNode变化不影响nodes
        # TreeNode = self.nodes     指针TreeNode与nodes共享一个地址, 相当于浅拷贝, TreeNode变化会影响nodes
        TreeNode = self.nodes[:]
        if len(TreeNode) > 0:
            while len(TreeNode) > 1:
                letfTreeNode = TreeNode.pop()
                rightTreeNode = TreeNode.pop()
                newNode = HuffmanTreeNode()
                newNode.lchild = letfTreeNode
                newNode.rchild = rightTreeNode
                newNode.weight = letfTreeNode.weight + rightTreeNode.weight
                letfTreeNode.parent = newNode
                rightTreeNode.parent = newNode
                self.InsertTreeNode(TreeNode, newNode)
            return TreeNode[0]

    def InsertTreeNode(self, TreeNode, newNode):
        length = len(TreeNode)
        if length > 0:
            temp = length - 1
            while temp >= 0:
                if newNode.weight < TreeNode[temp].weight:
                    TreeNode.insert(temp+1, newNode)
                    return True
                temp -= 1
        TreeNode.insert(0, newNode)

3. 哈夫曼编码

  在数据通信时,假如我们要发送

ABCDEFG“ABCDEFG”

这一串信息,我们并不会直接以这种形式进行发送,而是将其编码成计算机能够识别的二进制形式。根据编码类型可将其分为固定长度编码和可变长度编码,顾名思义,固定长度编码就是编码后的字符长度都相同,可变长度编码就是编码后的字符长度不相同。这两种类型有什么区别呢?我们来举例说明一下:

AA

BB

CC

DD

EE

FF

GG

固定长度编码

000000

001001

010010

011011

100100

101101

110110

可变长度编码

00

11

0101

1010

1111

101101

110110

  

ABCDEFG“ABCDEFG”

这条信息使用固定长度编码后的长度为21,使用可变长度编码后的长度为14,报文变短,报文的传输效率会相应的提高。但如果传送的字符为

BD“BD”

,按可变长度编码后的报文为

111“111”

,但是在译码是就会出现

BBB,BD,DB“BBB”,“BD”,“DB”

多种结果,因此采用可变长度编码时需要注意任一字符不能是其他字符的前缀,符合这样的可变长度编码称为前缀编码。
  报文最短可以引申到二叉树路径最短,即构造前缀编码的实质就是构造一棵哈夫曼树,通过这种形式获得的二进制编码称为哈夫曼编码。这里的权值就是报文中字符出现的概率,出现概率越高的字符我们用越短的字符表示。
  以下表中的字符及其出现的概率为例来实现哈夫曼编码:

字符

AA

BB

CC

DD

EE

FF

GG

HH

出现概率

0.010.01

0.430.43

0.150.15

0.020.02

0.030.03

0.210.21

0.070.07

0.08
哈夫曼编码

101010101010

00

110110

101011101011

1010010100

111111

10111011

100

Python描述数据结构之哈夫曼树篇
  代码实现就是在哈夫曼树的基础上加一个编码的函数:

    def HuffmanEncode(self, Root):
        TreeNode = self.nodes[:]
        code_result = []
        for index in range(len(TreeNode)):
            temp = TreeNode[index]
            code_leaf = [temp.data]
            code = ''
            while temp is not Root:
                if temp.parent.lchild is temp:
                    # 左分支
                    code = '0' + code
                else:
                    # 右分支
                    code = '1' + code
                temp = temp.parent
            code_leaf.append(code)
            code_result.append(code_leaf)
        return code_result

  测试结果如下:

if __name__ == '__main__':
    tree_obj = HuffmanTree([('A', 0.01), ('B', 0.43), ('C', 0.15), ('D', 0.02), ('E', 0.03), ('F', 0.21), ('G', 0.07), ('H', 0.08)])
    huf_tree = tree_obj.CreateHuffmanTree()
    huf_code = tree_obj.HuffmanEncode(huf_tree)
    for index in range(len(huf_code)):
        print('{0}: {1}'.format(huf_code[index][0], huf_code[index][1]))

Python描述数据结构之哈夫曼树篇

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。