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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

登天蚂蚁 2018-08-31 21:34:00 浏览393
展开阅读全文
img_eb877de873994b4b3013ca3a5039aaf9.jpe

哈夫曼树

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

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

编码与解码

数据在计算机上是以二进制表达的,即计算机只识别二进制序列,所以所有字符内容都需要完成与二进制的转换,才能在计算机中存储和呈现为我们看到的内容。并且这种转换方式必须是一致的,即字符内容若以方式 A 转换为二进制序列,则二进制序列同样需要以方式 A 转换为字符内容,否则会产生所谓的乱码现象。这种字符到二进制的转换即为编码,二进制到字符的转换即为解码,编码和解码需要使用相同的映射规则,才不会产生乱码。

哈夫曼编码

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

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

哈夫曼树的构造

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

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

这里自然不可能以所有字符集作示例,假设字符集范围为 A~J
字符集合为:contentArr = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
对应的频率为:valueArr = [5, 3, 4, 0, 2, 1, 8, 6, 9, 7]

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

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

contentArr = ['D', 'F', 'E', 'B', 'C', 'A', 'H', 'J', 'G', 'I']
valueArr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

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

树结构中定义的 acceptNewNode 方法,用于向树中添加新字符,其中 value 表示新字符的频率,content 表示字符体。

第一个元素 D,频率为 0

img_a86d58facaeaf1a5c546f86eb4fb155d.png

第二个元素 F,频率为 1

img_82852d730a43f92eb0eeb1a65527ad65.png

第三个元素 E,频率为 2

img_2ff95cd0c1aa6d1c7c0a9a1cb8cbef7c.png

...
...
...

第十个元素 I,频率为 9

img_a40258caa49e11436cc29f8250a936c1.png

哈夫曼树编解码

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

构造哈希表

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

# 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()

代码中以 codeMap 作为存储键值对的哈希表, 以 byteArr 存储二进制路径信息。因为哈夫曼树是满二叉树,节点的左子树存在则右子树同时存在,所以判断左子树是否存在即可判断是否为叶子节点。每个左叶子节点访问结束则记录键值对到 codeMap 中,并将路径 byteArr 回退到父节点,开始访问右子树;每个右叶子节点访问结束则记录键值对到 codeMap 中,并将路径 byteArr 回退到父节点的父节点,访问其右子树。

编码与解码

构造完成哈希表后,编码 encode 过程只需要根据字符取二进制序列即可。解码 decode 过程就是根据二进制序列,不断在二叉树中查找字符而已,找到字符后则从根节点继续查找下一个字符。

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

# 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

github 链接:哈夫曼树

网友评论

登录后评论
0/500
评论