数据结构(五):哈夫曼树(Huffman Tree)

哈夫曼树

哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,所以也称之为最优二叉树。

节点的带权路径长指的是叶子节点的权值与路径长的乘积,树的带权路径长即为树中所有叶子节点的带权路径长度之和。由此可知,若叶子节点的权值都是已知的,则二叉树的构造过程中,使得权值越大的叶子节点路径越小,则整棵树的带权路径长最小。

编码与解码

数据在计算机上是以二进制表达的,即计算机只识别二进制序列,所以所有字符内容都需要完成与二进制的转换,才能在计算机中存储和呈现为我们看到的内容。并且这种转换方式必须是一致的,即字符内容若以方式

转换为二进制序列,则二进制序列同样需要以方式

转换为字符内容,否则会产生所谓的乱码现象。这种字符到二进制的转换即为编码,二进制到字符的转换即为解码,编码和解码需要使用相同的映射规则,才不会产生乱码。

哈夫曼编码

构造哈夫曼树的目的是为了完成哈夫曼编码,哈夫曼编码是一种变长、极少多余编码方案。相对于等长编码,将文件中每个字符转换为固定个数的二进制位,变长编码根据字符使用频率的高低,使用了不同长度的二进制位与不同字符进行映射,使得频率高的字符对应的二进制位较短,频率低的字符对应的二进制位较长。使得源文件利用哈夫曼编码后的二进制序列大小,相对于原编码方案能够有较大缩小,如此即完成了文件的压缩。

哈夫曼编码能够用于实现文件的无损压缩,自然保证了文件解压缩过程的正确性,即二进制序列向字符的映射过程不会发生错乱。解码过程的正确性通过哈夫曼树的结构可以得到证明,以哈夫曼树中的每个叶子节点作为一个字符,则从根节点到每个叶子的路径都是唯一的,即不存在一个叶子节点的路径是另一个叶子节点的路径前缀。满足该特性的编码称之为前缀编码,所以哈夫曼编码中能够实现二进制到字符的正确映射。

哈夫曼树的构造

哈夫曼树是一棵满二叉树,树中只有两种类型的节点,即叶子节点和度为 2 的节点,所以树中任意节点的左子树和右子树同时存在。构建步骤如下:

  1. 对字符集合按照字符频率进行升序排序,并构建一颗空树;
  2. 遍历字符集合,将每一个字符添加到树中,添加规则为: 【1】若树为空,则作为根节点; 【2】若字符频率不大于根节点频率,则字符作为根节点的左兄弟,形成一个新的根节点,频率值为左、右子节点之和; 【3】若字符频率大于根节点频率,则字符作为根节点的右兄弟,形成一个新的根节点,频率值为左右子节点之和。
构造示例

这里自然不可能以所有字符集作示例,假设字符集范围为

~

字符集合为:

对应的频率为:

step 1:

对字符集合按照频率进行排序,这里使用插入排序算法进行排序。

算法示例:

# synchronise sort the valueArr and contentArr
def insertionSort(valueArr, contentArr):
    for i in range(1, len(valueArr)):  # iteration times
        tmpValue = valueArr[i]
        tmpContent = contentArr[i]
        while i > 0 and tmpValue < valueArr[i - 1]:
            valueArr[i] = valueArr[i - 1]
            contentArr[i] = contentArr[i - 1]
            i = i - 1
        valueArr[i] = tmpValue
        contentArr[i] = tmpContent

排序后字符集合和对应的频率为:

step 2:

遍历将集合中元素添加到树中,其中定义如下:

树节点定义为:

# tree node definition
class Node(object):
    def __init__(self, value, content=None, lchild=None, rchild=None):
        self.lchild = lchild
        self.rchild = rchild
        self.value = value
        self.content = content

树定义为:

# tree definition
class Tree(object):
    def __init__(self, root=None):
        self.root = root
        self.codeMap = {}

    # merge two nodes and return one root node
    def acceptNewNode(self, value, content):
        if not self.root:
            self.root = Node(value, content)
        else:
            newNode = Node(value, content)
            newRoot = Node(self.root.value + value)
            lchild, rchild = (self.root, newNode) if self.root.value < value else (newNode, self.root)
            newRoot.lchild, newRoot.rchild = lchild, rchild
            self.root = newRoot

树结构中定义的

方法,用于向树中添加新字符,其中

表示新字符的频率,

表示字符体。

第一个元素

,频率为

第二个元素

,频率为

第三个元素

,频率为

... ... ...

第十个元素

,频率为

哈夫曼树编解码

哈夫曼树构造完成之后,以

表示左分支,

表示右分支,则树中每个字符都有唯一的二进制映射。这里借用哈希表结构,将字符与对应的二进制序列存储为键值对,来演示编码过程;利用二进制序列在二叉树中查找具体的字符,来演示解码过程。

构造哈希表

首先根据哈夫曼树,生成哈希表,有点类似于前序遍历:

# initialize the huffman tree code map
def initializeCodeMap(node, byteArr, codeMap):
    if node.lchild:
        byteArr.append('0')
        initializeCodeMap(node.lchild, byteArr, codeMap)
        byteArr.append('1')
        initializeCodeMap(node.rchild, byteArr, codeMap)
        byteArr.pop() if len(byteArr) > 0 else None  # in case only the root node left
    else:
        codeMap[node.content] = ''.join(byteArr)
        byteArr.pop()

代码中以

作为存储键值对的哈希表, 以

存储二进制路径信息。因为哈夫曼树是满二叉树,节点的左子树存在则右子树同时存在,所以判断左子树是否存在即可判断是否为叶子节点。每个左叶子节点访问结束则记录键值对到

中,并将路径

回退到父节点,开始访问右子树;每个右叶子节点访问结束则记录键值对到

中,并将路径

回退到父节点的父节点,访问其右子树。

编码与解码

构造完成哈希表后,编码

过程只需要根据字符取二进制序列即可。解码

过程就是根据二进制序列,不断在二叉树中查找字符而已,找到字符后则从根节点继续查找下一个字符。

编码与解码函数体实现如下:

# tree definition
class Tree(object):

    # encode
    def encode(self, chars):
        bytes = ''
        for i in chars:  # get the mapped bytes
            bytes += self.codeMap.get(i.upper(), '###')
        return bytes

    # decode
    def decode(self, bytes):
        chars = ''
        tmpNode = self.root
        for i in bytes:
            if i == '0':
                tmpNode = tmpNode.lchild
            elif i == '1':
                tmpNode = tmpNode.rchild
            if not tmpNode.lchild:
                chars += tmpNode.content
                tmpNode = self.root
        return chars

代码附录

完整代码如下:

# tree node definition
class Node(object):
    def __init__(self, value, content=None, lchild=None, rchild=None):
        self.lchild = lchild
        self.rchild = rchild
        self.value = value
        self.content = content

# tree definition
class Tree(object):
    def __init__(self, root=None):
        self.root = root
        self.codeMap = {}

    # initialize the huffman tree code map
    def initializeCodeMap(self):
        initializeCodeMap(self.root, [], self.codeMap)

    # encode
    def encode(self, chars):
        bytes = ''
        for i in chars:  # get the mapped bytes
            bytes += self.codeMap.get(i.upper(), '###')
        return bytes

    # decode
    def decode(self, bytes):
        chars = ''
        tmpNode = self.root
        for i in bytes:
            if i == '0':
                tmpNode = tmpNode.lchild
            elif i == '1':
                tmpNode = tmpNode.rchild
            if not tmpNode.lchild:
                chars += tmpNode.content
                tmpNode = self.root
        return chars

    # merge two nodes and return one root node
    def acceptNewNode(self, value, content):
        if not self.root:
            self.root = Node(value, content)
        else:
            newNode = Node(value, content)
            newRoot = Node(self.root.value + value)
            lchild, rchild = (self.root, newNode) if self.root.value < value else (newNode, self.root)
            newRoot.lchild, newRoot.rchild = lchild, rchild
            self.root = newRoot

# initialize the huffman tree code map
def initializeCodeMap(node, byteArr, codeMap):
    if node.lchild:
        byteArr.append('0')
        initializeCodeMap(node.lchild, byteArr, codeMap)
        byteArr.append('1')
        initializeCodeMap(node.rchild, byteArr, codeMap)
        byteArr.pop() if len(byteArr) > 0 else None  # in case only the root node left
    else:
        codeMap[node.content] = ''.join(byteArr)
        byteArr.pop()

# construct the huffman tree
def createHuffmanTree(valueArr, contentArr):
    insertionSort(valueArr, contentArr)  # synchronise sort the valueArr and contentArr
    hfTree = Tree()
    for i in range(len(valueArr)):  # construct the huffman tree
        hfTree.acceptNewNode(valueArr[i], contentArr[i])
    hfTree.initializeCodeMap() # initialize the huffman tree code map
    return hfTree

# synchronise sort the valueArr and contentArr
def insertionSort(valueArr, contentArr):
    for i in range(1, len(valueArr)):  # iteration times
        tmpValue = valueArr[i]
        tmpContent = contentArr[i]
        while i > 0 and tmpValue < valueArr[i - 1]:
            valueArr[i] = valueArr[i - 1]
            contentArr[i] = contentArr[i - 1]
            i = i - 1
        valueArr[i] = tmpValue
        contentArr[i] = tmpContent

演示示例如下:

if __name__ == '__main__':
    valueArr = [5, 3, 4, 0, 2, 1, 8, 6, 9, 7]
    contentArr = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
    huTree = createHuffmanTree(valueArr, contentArr)
    chars = 'hIebAhcHdfGc'
    bytes = huTree.encode(chars)
    print(chars.lower(),'encode =',bytes)
    
    chars = huTree.decode(bytes)
    print(bytes,'decode =',chars.lower())

示例输出为:

hiebahchdfgc encode = 11100111111111111110111101110111110111011111110011111110110111110
11100111111111111110111101110111110111011111110011111110110111110 decode = hiebahchdfgc

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老马说编程

(49) 剖析LinkedHashMap / 计算机程序的思维逻辑

之前我们介绍了Map接口的两个实现类HashMap和TreeMap,本节来介绍另一个实现类LinkedHashMap。它是HashMap的子类,但可以保持元素按...

2046
来自专栏你不就像风一样

Java核心数据结构(List,Map,Set)使用技巧与优化

JDK提供了一组主要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继承自 java.util.Collection 接口,并位于 java...

3143
来自专栏Linyb极客之路

Java开发者易犯错误Top10

Arrays.asList()将返回一个数组内部是私有静态类的ArrayList,这不是java.util.ArrayList类,java.util.Array...

1214
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高二十】集合指定初始容量&asList缺陷&subList缺陷

【Java提高二十】集合指定初始容量 &asList缺陷&subList缺陷 集合指定初始容量 集合是我们在Java编程中使用非常广泛的,它就像大海,海纳百川,...

3817
来自专栏desperate633

LeetCode 17. Letter Combinations of a Phone Number题目分析代码

以上的答案是按照词典编撰顺序进行输出的,不过,在做本题时,你也可以任意选择你喜欢的输出顺序。

761
来自专栏专注 Java 基础分享

堆结构的优秀实现类----PriorityQueue优先队列

     之前的文章中,我们有介绍过动态数组ArrayList,双向队列LinkedList,键值对集合HashMap,树集TreeMap。他们都各自有各自的优...

2466
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

1763
来自专栏Android机动车

Java 基础(四)——集合源码解析 List

前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。

864
来自专栏数据魔术师

数据结构-线性表|顺序表|链表(下)

1 1 1 哈喽。各位小伙伴好久不见,热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐! 继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱...

2907
来自专栏Java3y

Java集合总结【面试题+脑图】,将知识点一网打尽!

2755

扫码关注云+社区

领取腾讯云代金券