精华内容
下载资源
问答
  • 哈夫曼树/赫夫曼树 Python实现赫夫曼树 Python实现哈夫曼树 哈夫曼编码 哈夫曼压缩 哈夫曼解压 最简单的方式实现哈夫曼树

    基本概述

    • 概念
      在这里插入图片描述
    • 解析
      在这里插入图片描述
      举例,如上图中 权值为13 的结点,那么它的“结点带权路径长度”为:13*(3-1)=26

    在这里插入图片描述
    上图中,中间的二叉树,wpl最小,而且权值为13的结点,满足“权值越大离根结点越近” 那么它就是赫夫曼树!

    构建赫夫曼树 思路

    • 构建赫夫曼树的步骤
      以数列:[13,7,8,3,29,6,1 ] 为例
      在这里插入图片描述
      注释:
      (1)每一个结点可以看成一个二叉树,二叉树的分类中有说到
      (2)取出排序后,前两个数;就是取出根结点权值最小的两颗二叉树

    • 图解
      (1)原数组 [13,7,8,3,29,6,1 ],第一次升序后:[1,3,6,7,8,13,29],取出前两个数(看下图的最底层),权值的和为新的根结点 4
      (2)重新将数组连同刚刚产生的根结点4进行升序,数组为[4,6,7,8,13,29],此时选出的前两个数是4和6(看下图中的倒数第二层),让它们权值的和为新的根结点 10,将10放入剩下的未处理数组中:[10,7,8,13,29]
      (3)再次升序时,会发现 10 应该排在 7和8的后面,所以升序后的数组为:[7,8,10,13,29],取出的前两个数是7和8,此时它们 应该和 根结点10 位于同一层,即倒数第三层,而且应该在10的前面(看下图的倒数第三层),因为它们是两个数 独立形成一个新的二叉树 那么在同一层的 [10,13,29] 前两个应该再生成一个新的根结点即是 23 (看下图倒数第四层)
      (4)让7和8相加,形成新的根结点15 ,将15放入剩下的未处理数组中:[15,23,29],以此类推,具体看下图,下图是从底层向上操作的↓↓↓
      在这里插入图片描述
      在这里插入图片描述

    Python实现构建赫夫曼树

    • 先解决:每次从列表中选出最小的2个数
      (1)第一种思路:遍历数组,进行比较;思路很好,但是没调用内置排序方法效率高
    array = [4, 20, 3, 4, 5, 6, 7]
    num1 = num2 = float('inf')
    for x in range(0, len(array)):
        if num1 > array[x]:
            num2 = num1
            num1 = array[x]
        elif num2 > array[x]:
            num2 = array[x]
    
    print(num1, num2)
    

    补充知识点:列表中如何按照元素的对象、类进行排序?

    • Java中通过实现 Comparable接口,可以给对象排序,Python中也可以在列表中按照元素的对象、类进行排序
    • 两种方法: operator模块中实现列表中的对象排序如何用内置的sort()函数实现对象的排序
    import operator  # 导入operator 包,pip install operator
    
    lis = []  # 待排序列表
    class Infor:  # 自定义的元素
        def __init__(self, stu_id, name, age):
            self.stu_id = stu_id
            self.name = name
            self.age = age
    
    # 将对象加入列表中
    lis.append(Infor(1, 'cbc', '11'))
    lis.append(Infor(15, 'acd', '13'))
    lis.append(Infor(6, 'bcd', '16'))
    lis.append(Infor(6, 'acd', '18'))
    lis.append(Infor(8, 'acd', '18'))
    
    '''operater模块:适用于数据量大'''
    # ----排序操作
    # 参数为排序依据的属性,可以有多个,这里优先id,使用时按需求改换参数即可
    temp = operator.attrgetter('stu_id', 'name')
    lis.sort(key=temp)  # 使用时改变列表名即可
    # ----排序操作
    # 此时lis已经变成排好序的状态了,排序按照stu_id优先,其次是name,遍历输出查看结果
    for obj in lis:
        print(obj.stu_id, obj.name, obj.age)
        
    '''内置的sort()'''
    lis.sort(cmp=None, key=lambda x:x.stu_id, reverse=False)
    # lis.sort(cmp=None, key=lambda x:(x.stu_id,x.name,...), reverse=False) # 多个指标,前主后次
    for obj in lis:
        print(obj.stu_id, obj.name, obj.age)
    

    注意:这两种方式都不能对空值进行操作,如果有空值会报错:TypeError: ‘<’ not supported between instances of ‘NoneType’ and ‘int’
    解决办法是:将空值换成“0”,这点相对于java实现 Comparable接口方式,有点不方便

    实现 创建赫夫曼树

    import operator
    
    
    class TreeNode(object):
        def __init__(self, val):
            self.val = val
            self.left = None
            self.right = None
    
    
    class HuffmanTree(object):
        def create_huffman_tree(self, array):
            '''
            创建赫夫曼树的方法
            :param array: 需要创建成赫夫曼树的数组
            :return: 创建好后的赫夫曼树的root结点
            '''
            # 为了操作方便,先遍历array数组,将array的每个元素构成一个TreeNode
            # 将TreeNode 对象放到 一个新的列表中
            nodes = []
            for item in array:
                nodes.append(TreeNode(item))
            # 对象排序
            while len(nodes) > 1:  # 到最后只有个新的根结点就停止
                temp = operator.attrgetter("val")
                nodes.sort(key=temp)
                # 取出根结点权值最小的两颗二叉树(结点)
                # left_node = nodes[0]
                # right_node = nodes[1]
                # 可以直接用pop第一个元素,下面的remove就不用写了
                left_node = nodes.pop(0)
                right_node = nodes.pop(0)
                # 构建一棵新的二叉树
                parent_node = TreeNode(left_node.val + right_node.val)
                parent_node.left = left_node  # 将父结点和左结点链接起来
                parent_node.right = right_node
                # 从nodes删除处理过的二叉树
                # nodes.remove(left_node)
                # nodes.remove(right_node)
                # 将parent_node加入nodes
                nodes.append(parent_node)
            return nodes[0]  # 返回根结点即可
    
        def pre_order(self, node):  # node 为根结点,前序遍历
            if node is None:
                return
            print(node.val, end=" ")
            self.pre_order(node.left)
            self.pre_order(node.right)
    
    
    if __name__ == '__main__':
        li = [13, 7, 8, 3, 29, 6, 1]
        h = HuffmanTree()
        huff_root = h.create_huffman_tree(li)
        h.pre_order(huff_root)
    '''输出结果:
    67 29 38 15 7 8 23 10 4 1 3 6 13 
    '''
    
    • 可以将上述结果,对照下图的前序遍历结果
      在这里插入图片描述

    赫夫曼编码

    • 介绍在这里插入图片描述
    • 原理剖析
      在这里插入图片描述
      变长编码:
      在这里插入图片描述
    • 赫夫曼编码 实现步骤
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
      在这里插入图片描述
    • 赫夫曼编码生成的就是前缀编码:因为 统计的每个字符 都是赫夫曼树的叶子结点,路径都是唯一的,所以生成的编码是唯一的

    在这里插入图片描述
    在这里插入图片描述

    数据压缩:创建赫夫曼树

    • 步骤
      在这里插入图片描述

    Python 实现

    补充知识点:如何获取字符串的字节数?

    (1)java中可以先用 getBytes 然后.length 获取字符串的字节数,Python可以通过 len()函数获取字符串长度或字节数
    (2)len 函数的基本语法格式为:len(string) ,它的结果是获取字符串的长度
    (3)在 Python 中,不同的字符所占的字节数不同,数字、英文字母、小数点、下划线以及空格,各占一个字节,而一个汉字可能占 2~4 个字节,具体占多少个,取决于采用的编码方式。例如,汉字在 GBK/GB2312 编码中占用 2 个字节,而在 UTF-8 编码中一般占用 3 个字节。
    以 UTF-8 编码为例,字符串“人生苦短,我用Python”所占用的字节数如下图所示。
    在这里插入图片描述
    可以通过使用 encode() 方法,将字符串进行编码后再获取它的字节数。例如,采用 UTF-8 编码方式,计算“人生苦短,我用Python”的字节数:

    # utf-8
    str1 = "人生苦短,我用Python"
    print(len(str1.encode())) # 27
    # 汉字加中文标点符号共 7 个,占 21 个字节,而英文字母和英文的标点符号占 6 个字节,
    # 一共占用 27 个字节
    
    # gbk
    str1 = "人生苦短,我用Python"
    print(len(str1.encode('gbk'))) # 20
    

    补充知识点:如何统计出字符串中每个字符的次数?

    • 方法一:直接使用字典
    '''法一'''
    s = 'helloworld'
    d = dict()
    for x in s:
        if x not in d:
            d[x] = 1
        else:
            d[x] = d[x] + 1
    print(d) # {'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}
    
    '''法二'''
    s = 'helloworld'
    d2 = dict()
    for x in s:
        d2[x] = d2.get(x, 0) + 1
    print(d2) # {'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}
    
    '''法三:字符串count结合使用'''
    s = 'helloworld'
    d3 = dict()
    for x in s:
        d3[x] = s.count(x)
    print(d3) # {'h': 1, 'e': 1, 'l': 3, 'o': 2, 'w': 1, 'r': 1, 'd': 1}
    
    # 至于先用set()集合去重,然后遍历原字符串用count统计出现次数的方法,类似就不加赘述了
    
    • 方式二:制表
    def count_char(str):
        str = str.lower()  # 化成小写
        ans = []
        for i in range(26):  # 列表赋初值  26 个 0
            ans.append(0)
        for i in str:
            if (ord(i) >= ord('a') and ord(i) <= ord('z')):
                ans[ord(i) - ord('a')] = ans[ord(i) - ord('a')] + 1  # 统计个数
        return ans
    
    if __name__ == "__main__":
        str = input()
        print(count_char(str))
    
    #-------
    def count_char(st):  # 定义数个数的函数
        keys = [chr(i + 97) for i in range(26)]  # 生成26个字母的key列表
        di = dict().fromkeys(keys, 0)  # 赋给每个key初始值0
        new = []  # 建立一个新列表用于存放有序的key
        st = st.lower()  # 将所有输入的字符改为小写
        for s in st:  # 遍历字符串
            di[s] = st.count(s)  # 输出每个字符的个数,存放到字典里
        for k in keys:  # 遍历keys,将其在di中的值添加到新列表,获得有序的26个字母的个数
            new.append(di[k])
        return new  # 返回存有26个字母个数的列表
    
    if __name__ == "__main__":
        st = input()  # 输入字符串
        str1 = ""  # 定义一个空字符串
        for s in st:  # 遍历输入的字符串
            if s.isalpha() != 0:  # 只有字母才添加到新字符串,标点忽略不计
                str1 += s
        print(count_char(str1))  # 输出列表
    
    • 方法三:Counter(计数器):用于追踪值的出现次数;Counter类继承dict类,所以它能使用dict类里面的方法

    特别注意: 它的统计输出是无序的

    '''直接导入类用法'''
    from collections import Counter
    
    str_exp = ' aaffbbcccdddee '
    c = Counter()  # 先新建实例
    for ele in str_exp:
        c[ele] = c[ele] + 1
    print(c, type(c)) # Counter({'c': 3, 'd': 3, ' ': 2, 'a': 2, 'f': 2, 'b': 2, 'e': 2})
    # 注意c的类型不是字典:<class 'collections.Counter'>
    # 继承dict类中的 items()方法
    for key, value in c.items():
        print(key, value, end=" | ") #  2 | a 2 | f 2 | b 2 | c 3 | d 3 | e 2 | 
    
    
    '''导入collections模块'''
    import collections
    obj = collections.Counter('aabbccc')
    print(obj)
    # 输出:Counter({'c': 3, 'a': 2, 'b': 2}) 它的类型不是字典是<class 'collections.Counter'
    
    '''elements()方法'''
    import collections
    obj = collections.Counter('aabbccc')
    print(sorted(obj.elements()))
    #输出:['a', 'a', 'b', 'b', 'c', 'c', 'c']
    for k in obj.elements():   #遍历打印obj所有元素
        print(k)
        
    '''most_common(指定一个参数n,列出前n个元素,不指定参数,则列出所有)'''
    import collections
    obj = collections.Counter('aabbbcccc')
    print(obj.most_common(2))
    #输出:[('c', 4), ('b', 3)]
    
    '''items(从dict类中继承的方法)'''
    import collections
    obj = collections.Counter('aabbbcccc')
    print(obj.items())
    
    for k,v in obj.items():
        print(k,v)
    
    # 输出:dict_items([('b', 3), ('c', 4), ('a', 2)])
    #     b 3
    #     c 4
    #     a 2
    
    '''update(增加元素)'''
    import collections
    obj = collections.Counter(['11','22'])
    obj.update(['22','55'])
    print(obj)
    
    #输出:Counter({'22': 2, '11': 1, '55': 1})
    
    '''subtract(原来的元素减去新传入的元素)'''
    import collections
    obj = collections.Counter(['11','22','33'])
    obj.subtract(['22','55'])
    print(obj)
    
    #输出:Counter({'11': 1, '33': 1, '22': 0, '55': -1})
    

    补充知识点:如何给字典排序

    • 说明:给字典排序 是为了让最后创建的结果更贴近所参考的教程,总体wpl是一样的,所以排不排序都无所谓;因为java在使用map[key,value] 在统计字符串出现的次数时,会自动按照 key 的大小升序排列!
    • 字典排序的方法,字典用法的总结:字典排序

    Python 实现数据压缩(创建赫夫曼树)

    import operator
    from collections import Counter
    from operator import itemgetter
    
    
    class TreeNode(object):
        def __init__(self, val, weight):
            self.val = val  # 存放数据(字符)本身,如"a" 或者"97"
            self.weight = weight  # 存放出现的次数
            self.left = None
            self.right = None
    
    
    class HuffmanCode(object):
        def get_nodes(self, bytes_array):
    
            nodes = []
            # 存储每个byte出现的次数
            # 统计一个字符串中每个元素出现的次数有很多种,这里为了操作方便,用Counter
            '''法一
            c = Counter()  # 创建一个统计对象
            for item in bytes_array:
                c[item] = c[item] + 1
            # 此时 c 会用字典的形式保存:key:每个元素;value:出现的次数
            '''
            # 法二 使用字典
            dic = {}
            for i in bytes_array:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] += 1
            '''如果不排序
            for key, value in dic.items(): 
                nodes.append(TreeNode(key, value))
            '''
    
            '''第一种排序 键值对 方式:
            dic_list = sorted(dic.items(), key=lambda x: x[0])
            print(dic_list)
            for index, value in enumerate(dic_list):  # 拿到 每一组键值对
              nodes.append(TreeNode(value[0], value[1]))  # 创建结点对象
            '''
    
            # 第二种排序 键值对 方式:
            dic_list = sorted(dic.items(), key=itemgetter(0), reverse=False)
            for item in dic_list:
                nodes.append(TreeNode(item[0], item[1]))
    
            return nodes
    
        def create_huffman_tree(self, nodes):
            while len(nodes) > 1:
                # 法一:nodes.sort(key=lambda x: x.weight)
                # 法二
                nodes.sort(key=operator.attrgetter("weight"))
                # 取出根结点权值最小的两颗二叉树(结点)
                left_node = nodes.pop(0)
                right_node = nodes.pop(0)
                # 构建一棵新的二叉树,它的根结点(不是叶子结点)没有val,用0补充;含有weight
                parent_node = TreeNode(0, left_node.weight + right_node.weight)
                parent_node.left = left_node  # 将父结点和左结点链接起来
                parent_node.right = right_node
                # 将parent_node加入nodes
                nodes.append(parent_node)
            return nodes[0]  # 返回根结点即可
    
        def pre_order(self, node):  # 前序遍历 传入node为根结点
            if node is None:
                return
            print(node.val, node.weight, end="  || ")
            self.pre_order(node.left)
            self.pre_order(node.right)
    
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        # content_bytes = list(content.encode('utf-8'))
        content_bytes = content.encode('utf-8')
        print(len(content_bytes))
        h = HuffmanCode()
        # 获取到结点列表
        obj_list = h.get_nodes(content_bytes)
        # 获取到赫夫曼树的根结点
        huffman_root = h.create_huffman_tree(obj_list)
        # 前序遍历
        h.pre_order(huffman_root)
        
    '''
    40
    
    [(32, 9), (97, 5), (100, 1), (101, 4), (105, 5), (106, 2), (107, 4), (108, 4), (111, 2), (117, 1), (118, 2), (121, 1)] # 只是给字典排了下序
    
    0 40  || 0 17  || 0 8  || 108 4  || 0 4  || 111 2  || 118 2  || 32 9  || 0 23  || 0 10  || 97 5  || 105 5  || 0 13  || 0 5  || 0 2  || 100 1  || 117 1  || 0 3  || 121 1  || 106 2  || 0 8  || 101 4  || 107 4  || 
    # 赫夫曼树在处理weight一样时,是按照排序规则来合并结点,所以形态会不一样,但是最后根结点是一样的,
    所以 看val为空的结点,间隔不管形态如何,间隔一定会一样的
    '''
    

    赫夫曼编码 和 赫夫曼编码后数据

    • 到这一步,我们要做的是编码,因为所有的val有值得结点,必然是位于赫夫曼树的叶子节点,按照上面的规定,从根结点出发,遍历每一条到叶子结点的路径,走过的路径向左则为0,向右则为1,因为之前学过遍历二叉树路径的方法,所以可以这样很巧妙的完成!

    补充知识点:如何遍历出二叉树的所有路径

    • 如下图有一颗10个结点的二叉树:
      在这里插入图片描述
    • 该怎么求它的所有路径?我们可以这样做
      (1)在什么情况下输出结点?假设只有一个根结点root,它没有左右子结点,此时就输出结点的值,所以如上图的二叉树,我们使用递归,找到每一个没有左右子结点的结点,如上图是:[7,8,9,5,6],所以我们的递归退出条件找到了,即是:存在当前结点并且它没有左右子结点了,那么就退出
      (2)为了串联起走过的路径,我们需要新增一个全局变量path,每次将走过的结点以字符串的形式串联起来,新增一个结果列表,输出最后结果!
    class TreeNote(object):  # 创建树的结点
        def __init__(self, val=-1):
            self.val = val
            self.left = None
            self.right = None
    
    
    class BinaryTree(object):  # 创建二叉树
        def __init__(self):
            self.root = None  # 根结点
    
        def add(self, val):  # 二叉树添加结点 
            node = TreeNote(val)
            if self.root is None:
                self.root = node
                return
            queue = [self.root]
            while queue:
                temp_node = queue.pop(0)
                if temp_node.left is None:
                    temp_node.left = node
                    return
                else:
                    queue.append(temp_node.left)
                if temp_node.right is None:
                    temp_node.right = node
                    return
                else:
                    queue.append(temp_node.right)
    
        def bre_order(self, node):  # 二叉树广度遍历
            if node is None:
                return
            queue = [node]
            while queue:
                temp_node = queue.pop(0)
                print(temp_node.val, end=" ")
                if temp_node.left is not None:
                    queue.append(temp_node.left)
                if temp_node.right is not None:
                    queue.append(temp_node.right)
    
        def find_rode(self, node, path, res):  # node:传入root;path:路径;res:结果
            if node is None:
                return []
            if node.left is None and node.right is None: # 当前结点没有左右子结点
                res.append(path + str(node.val))
                return res
            if node.left: # 向左递归
                self.find_rode(node.left, path + str(node.val), res)
            if node.right: # 向右递归
                self.find_rode(node.right, path + str(node.val), res)
    
    
    if __name__ == '__main__':
        t = BinaryTree()
        for i in range(10):
            t.add(i)
        print("\n广度遍历为:")
        t.bre_order(t.root)
        print()
        out_put = []
        t.find_rode(t.root, "", out_put) 
        print("二叉树所有路径为:")
        print(out_put)
    '''
    广度遍历为:
    0 1 2 3 4 5 6 7 8 9 
    二叉树所有路径为:
    ['0137', '0138', '0149', '025', '026']
    '''
    

    实现赫夫曼编码

    • 知道了怎么求二叉树的所有路径,那么就可以轻松求出赫夫曼树所有路径,按照新规定:走过的路径我们只需要拿到叶子结点的 val 即可,其他结点不需要拿val,路径则按照左边以“0”替换,右边以“1”替换,即可!
    import operator
    from operator import itemgetter
    
    class TreeNode(object):
        def __init__(self, val, weight):
            self.val = val  # 存放数据(字符)本身,如"a" 或者"97"
            self.weight = weight  # 存放出现的次数
            self.left = None
            self.right = None
    
    
    class HuffmanCode(object):
        # 返回赫夫曼树的结点列表
        def get_nodes(self, bytes_array):
            nodes = []
            dic = {}
            for i in bytes_array:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] += 1
            # 第二种排序 键值对 方式:
            dic_list = sorted(dic.items(), key=itemgetter(0), reverse=False)
            for item in dic_list:
                nodes.append(TreeNode(item[0], item[1]))
    
            return nodes
    
        # 构建赫夫曼树,返回赫夫曼树的根结点
        def create_huffman_tree(self, nodes):
            while len(nodes) > 1:
                nodes.sort(key=operator.attrgetter("weight"))
                # 取出根结点权值最小的两颗二叉树(结点)
                left_node = nodes.pop(0)
                right_node = nodes.pop(0)
                # 构建一棵新的二叉树,它的根结点,没有val,只有weight
                parent_node = TreeNode(0, left_node.weight + right_node.weight)
                parent_node.left = left_node  # 将父结点和左结点链接起来
                parent_node.right = right_node
                # 将parent_node加入nodes
                nodes.append(parent_node)
            return nodes[0]  # 返回根结点即可
    
        # 为了更好比对图,我们可以使用 广度遍历测试
        def bre_order(self, node):
            if node is None:
                return
            queue = [node]
            while queue:
                temp_node = queue.pop(0)
                print(temp_node.val, temp_node.weight, end=" || ")
                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
    
        # 获取赫夫曼编码表
        def get_codes(self, node, path, temp):
            if node is None:
                return
            if node.left is None and node.right is None:
                temp.append(path + "|" + str(node.val)) # 中间新增一个分割符号,最后更好拿到编码和val
                return temp
            if node.left:
                self.get_codes(node.left, path + "0", temp) # 左边让路径不断加上“0”
            if node.right:
                self.get_codes(node.right, path + "1", temp) # 左边让路径不断加上“1”
    
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        content_bytes = content.encode('utf-8')
        print(len(content_bytes))
        h = HuffmanCode()
        # 获取到结点列表
        obj_list = h.get_nodes(content_bytes)
        # 获取到赫夫曼树的根结点
        huffman_root = h.create_huffman_tree(obj_list)
        h.bre_order(huffman_root)
        print()
        # 赫夫曼编码
        out_put = []
        h.get_codes(huffman_root, "", out_put)
        for item in out_put:
            print(chr(int(item.split("|")[1])), item.split("|")[0], end=";")
            print()
    '''输出结果为
    40
    0 40 || 0 17 || 0 23 || 0 8 || 32 9 || 0 10 || 0 13 || 108 4 || 0 4 || 97 5 || 105 5 || 0 5 || 0 8 || 111 2 || 118 2 || 0 2 || 0 3 || 101 4 || 107 4 || 100 1 || 117 1 || 121 1 || 106 2 || 
    
    val对应的编码为:
    l 000;
    o 0010;
    v 0011;
      01;
    a 100;
    i 101;
    d 11000;
    u 11001;
    y 11010;
    j 11011;
    e 1110;
    k 1111;
    '''
    
    • 验证一下是否正确:因为得到的赫夫曼树形态有可能不一样,得到的编码也不一样,但是按照上面写的,最后将上面每个val对应的新编码值,去组合一下输入的字符串,得到的字符长度要为:133
    # 验证:手动输入(下一节实现自动生成如下编码,并且按照每八位压缩)
    final_str = "1010100010100111110010001010011111001000101001111100111011100001110001110000010011101000101100101000101001111100110001110111000011100"
    print(len(final_str)) # 133 恭喜我们做对了!
    

    数据压缩:赫夫曼编码字节数组

    • 按照上述步骤我们已经得到了每一个val的赫夫曼编码,并且存放在了数组中,接下来要做的就是自动将数组里的值生成上面的验证的:final_str 并且按8位 生成 赫夫曼编码字节数组
    • 对于上面我们用 out_put = [ ] 列表来保存数据,我们可以改成,在生成赫夫曼编码时直接用字典来保存每条路径,即是:dict[node.val]=path 这样在处理自动将输入的字符串转成赫夫曼编码,可以充分利用字典的特性,所以下面整体代码为:
    import operator
    from operator import itemgetter
    
    class TreeNode(object):
        def __init__(self, val, weight):
            self.val = val  # 存放数据(字符)本身,如"a" 或者"97"
            self.weight = weight  # 存放出现的次数
            self.left = None
            self.right = None
    
    
    class HuffmanCode(object):
        # 返回赫夫曼树的结点列表
        def get_nodes(self, bytes_array):
            nodes = []
            dic = {}
            for i in bytes_array:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] += 1
            # 第二种排序 键值对 方式:
            dic_list = sorted(dic.items(), key=itemgetter(0), reverse=False)
            for item in dic_list:
                nodes.append(TreeNode(item[0], item[1]))
    
            return nodes
    
        # 构建赫夫曼树,返回赫夫曼树的根结点
        def create_huffman_tree(self, nodes):
            while len(nodes) > 1:
                nodes.sort(key=operator.attrgetter("weight"))
                # 取出根结点权值最小的两颗二叉树(结点)
                left_node = nodes.pop(0)
                right_node = nodes.pop(0)
                # 构建一棵新的二叉树,它的根结点,没有val,只有weight
                parent_node = TreeNode(0, left_node.weight + right_node.weight)
                parent_node.left = left_node  # 将父结点和左结点链接起来
                parent_node.right = right_node
                # 将parent_node加入nodes
                nodes.append(parent_node)
            return nodes[0]  # 返回根结点即可
    
        # 为了更好比对图,我们可以使用 广度遍历测试
        def bre_order(self, node):
            if node is None:
                return
            queue = [node]
            while queue:
                temp_node = queue.pop(0)
                print(temp_node.val, temp_node.weight, end=" || ")
                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
    
        # 获取赫夫曼编码(每一条路径)
        def get_codes(self, node, path, temp):
            if node is None:
                return
            if node.left is None and node.right is None:
                temp[str(node.val)] = path # 改成字典来保存路径
                return temp
            if node.left:
                self.get_codes(node.left, path + "0", temp) # 左边让路径不断加上“0”
            if node.right:
                self.get_codes(node.right, path + "1", temp) # 左边让路径不断加上“1”
                
        def zip_codes(self, codes_array, srt_byte_content, str_join): # 充分利用字典特性
        	# 参数:传入赫夫曼编码数组,传入一个字节字符串,拼接字符串
            for item in srt_byte_content: # 遍历每一个字符串字节
                str_join += str(codes_array.get(str(item))) # 通过字节作为key,去找它的值,再拼接
            return str_join	
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        content_bytes = content.encode('utf-8')
        # print(len(content_bytes))
        h = HuffmanCode()
        # 获取到结点列表
        obj_list = h.get_nodes(content_bytes)
        # 获取到赫夫曼树的根结点
        huffman_root = h.create_huffman_tree(obj_list)
        # 广度遍历
        # h.bre_order(huffman_root)
        # 编码后
        out_put = {} # 改成字典
        h.get_codes(huffman_root, "", out_put)
        str_join = " "
        final_str = h.zip_codes(out_put, content_bytes, str_join) 
        print(final_str)
    ''' 输出结果
    1010100010111111110010001011111111001000101111111100111011100001110001110000010011101000
    101100101000101111111100110001110111000011100
    '''
    
    • 接下来需要将自动获取到的字符串 转成 byte数组
      (1)先要创建一个存下字符串的数组,有两种方式计算需要的数组长度,但是Python不需要规定长度也行,直接append添加每8个一组,最后多少都无所谓,emmmm!!!

    第一种写法:

    if len(str_join) % 8 == 0: # 自动获取的字符串长度先模上8
    	byte_array_len = len(str_join) / 8
    else:
    	byte_array_len = len(str_join) // 8 + 1
    byte_array = [0] * byte_array_len
    	print(len(byte_array)) # 17 
    

    第二种写法:

    byte_array_len = (len(str_join) + 7) // 8
    byte_array = [0] * byte_array_len
    print(len(byte_array)) # 17
    

    实现赫夫曼编码 转成 byte数组

    '''上面代码一模一样就不拷贝了'''
        def zip_codes(self, codes_array, srt_byte_content, str_join):  # 参数:传入一个字节字符串,传入赫夫曼编码数组
            for item in srt_byte_content:
                str_join += str(codes_array.get(str(item)))
            byte_array = []
            final_byte_array = []
            for i in range(1, len(str_join), 8):  # 步长取8,从第二位开始,第一位是个空格
                byte_array.append(str_join[i:i + 8])
            for item in byte_array:
            	print(item) # 输出检查
    			if item[0] == "1":
                    final_byte_array.append(int(item, base=2) - 256)  # 说明一
                else:
                    final_byte_array.append(int(item, base=2))
    		return final_byte_array
    
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        content_bytes = content.encode('utf-8')
        # print(len(content_bytes))
        h = HuffmanCode()
        # 获取到结点列表
        obj_list = h.get_nodes(content_bytes)
        # 获取到赫夫曼树的根结点
        huffman_root = h.create_huffman_tree(obj_list)
        # 前序遍历
        # h.pre_order(huffman_root)
        # print()
        # h.bre_order(huffman_root)
        # print()
        # 编码后
        out_put = {}
        h.get_codes(huffman_root, "", out_put)
        str_join = " "
        # final_str = h.zip_codes(out_put, content_bytes, str_join)
        final_byte = h.zip_codes(out_put, content_bytes, str_join)
        print(final_byte)
        print(len(final_byte) 
        
    '''输出结果
    10101000
    10111111
    11001000
    10111111
    11001000
    10111111
    11001110
    11100001
    11000111
    00000100
    11101000
    10110010
    10001011
    11111100
    11000111
    01110000
    11100
    
    [-88, -65, -56, -65, -56, -65, -50, -31, -57, 4, -24, -78, -117, -4, -57, 112, -228]
    
    17 
    ---
    可以计算压缩率为:(40-17)/ 40 = 0.575 
    '''
    
    • 说明一:默认切割出来的每八位,在计算机底层应该将它当做补码 才能进行存储,所以符号位为1的二进制码,表明它的原码是一个负数,那么怎么通过补码求出该数的十进制数?可以用快捷方法:算出补码无视符号位在二进制中的数 减去 256 即可!可以自行通过每个切割出来的字符串,当做补码然后求出它的原码,去掉符号位,求出二进制数,来验证!

    封装代码

    • 为了调用方便,我们将代码都封装到一个方法里,然后主函数调用该方法执行,主函数声明的全局变量,也都放入到一个类中,于是代码可以精简为:↓↓↓
    import operator
    from operator import itemgetter
    
    
    class TreeNode(object):
        def __init__(self, val, weight):
            self.val = val  # 存放数据(字符)本身,如"a" 或者"97"
            self.weight = weight  # 存放出现的次数
            self.left = None
            self.right = None
    
    
    class HuffmanCode(object):
        out_put_dic = {}  # 键值对:字符字节:赫夫曼编码
        str_join = ""  # 拼接字符串
    
        # 返回赫夫曼树的结点列表
        def get_nodes(self, bytes_array):
            nodes = []
            dic = {}
            for i in bytes_array:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] += 1
            # 给键值对 排序(可以有可无)
            dic_list = sorted(dic.items(), key=itemgetter(0), reverse=False)
            for item in dic_list:
                nodes.append(TreeNode(item[0], item[1]))
            return nodes
    
        # 构建赫夫曼树,返回赫夫曼树的根结点
        def create_huffman_tree(self, nodes):
            while len(nodes) > 1:
                nodes.sort(key=operator.attrgetter("weight"))
                # 取出根结点权值最小的两颗二叉树(结点)
                left_node = nodes.pop(0)
                right_node = nodes.pop(0)
                # 构建一棵新的二叉树,它的根结点,没有val,只有weight
                parent_node = TreeNode(0, left_node.weight + right_node.weight)
                parent_node.left = left_node  # 将父结点和左结点链接起来
                parent_node.right = right_node
                # 将parent_node加入nodes
                nodes.append(parent_node)
            return nodes[0]  # 返回根结点即可
    
        # 获取赫夫曼编码表
        def get_codes(self, node, path, temp):
            if node is None:
                return
            if node.left is None and node.right is None:
                temp[str(node.val)] = path
                return temp
            if node.left:
                self.get_codes(node.left, path + "0", temp)
            if node.right:
                self.get_codes(node.right, path + "1", temp)
            return temp
    
        def zip_codes(self, codes_array, srt_content_byte, str_join):  # 参数:传入一个字节字符串,传入赫夫曼编码数组
            for item in srt_content_byte:
                str_join += str(codes_array.get(str(item)))
            byte_array = []
            final_byte_array = []
            for i in range(0, len(str_join), 8):  # 步长取8,从第二位开始,第一位是个空格
                byte_array.append(str_join[i:i + 8])
            for item in byte_array:
    			if item[0] == "1":
                    final_byte_array.append(int(item, base=2) - 256) 
                else:
                    final_byte_array.append(int(item, base=2))
            return final_byte_array
    
        def huffman_zip(self, bytes_array):
            '''
            封装
            :param bytes_array: 传入一个原始字节数组
            :return: 返回一个压缩字节数组
            '''
            nodes = self.get_nodes(bytes_array)
            huffman_tree_root = self.create_huffman_tree(nodes)
            codes_array = self.get_codes(huffman_tree_root, "", HuffmanCode.out_put_dic)
            get_zip_byte = self.zip_codes(codes_array, bytes_array, HuffmanCode.str_join)
            return get_zip_byte
    
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        content_bytes = content.encode('utf-8')
        h = HuffmanCode()
        final = h.huffman_zip(content_bytes)
        print(final)
    '''输出结果
    [-88, -65, -56, -65, -56, -65, -50, -31, -57, 4, -24, -78, -117, -4, -57, 112, -228]
    '''
    

    数据解压

    • 第一步是还原回原来的赫夫曼编码字符串:即是通过最后的压缩字节数组,得到:“1010100010111111110010001011111111001000101111111100111011100001110001110000010011101000101100101000101111111100110001110111000011100” 我们可以遍历数组,如果是负数先加回265,如果是正数就不要加,但是这时候要注意两个重要问题:
      (1)如果压缩字节数组还没遍历到最后一个数,遇到正数,在正数转成二进制码时,需要补齐八位,即前面要补上0凑足八位二进制;
      (2)最后一位,如果是负数直接拼接起二进制码,如果是正数,不要补齐八位;因为前面我们在切割字符串时,是按照8位来切割的,最后剩下的,是直接转二进制的
    '''前面代码一样,就省略下了'''
        def be_back_str(self, huffman_array):  # 调用后,返回拼接哈夫曼编码
            # for ele in huffman_array: # 因为最后一个是负数,所以直接拼接上了,但是也可能是正数
            #     if ele < 0:
            #         HuffmanCode.str_join += str(bin(ele + 256))[2:]
            #     else:
            #         add_zero = 8 - len(bin(ele)[2:])
            #         HuffmanCode.str_join += ("0" * add_zero + bin(ele)[2:])
            # print(HuffmanCode.str_join)
            for i in range(len(huffman_array) - 1): # 遍历到数组前一个
                if huffman_array[i] < 0:
                    HuffmanCode.str_join += str(bin(huffman_array[i] + 256))[2:]
                else:
                    add_zero = 8 - len(bin(huffman_array[i])[2:])
                    HuffmanCode.str_join += ("0" * add_zero + bin(huffman_array[i])[2:])
            if huffman_array[-1] < 0: # 考虑最后一个数的两种情况
                HuffmanCode.str_join += bin(huffman_array[-1] + 256)[2:]
            else:
                HuffmanCode.str_join += bin(huffman_array[-1])[2:]
    		print(HuffmanCode.str_join) # 打印测试下
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        content_bytes = content.encode('utf-8')
        h = HuffmanCode()
        final = h.huffman_zip(content_bytes)
        print(final)
        h.be_back_str(final) 
    '''输出结果:
    101010001011111111001000101111111100100010111111110011101110000111000111
    0000010011101000101100101000101111111100110001110111000011100
    比较和前面的一致
    '''
    
    • 第二步,查找字符串,然后去原来的字典查值,得到字节数组,最后返回原来的字符串;这里要用到字符串的查找!

    完整代码

    import operator
    from operator import itemgetter
    
    
    class TreeNode(object):
        def __init__(self, val, weight):
            self.val = val  # 存放数据(字符)本身,如"a" 或者"97"
            self.weight = weight  # 存放出现的次数
            self.left = None
            self.right = None
    
    
    class HuffmanCode(object):
        out_put_dic = {}  # 键值对:字符字节:赫夫曼编码
        str_join = ""  # 拼接字符串
        final_bytes = []
    
        # 返回赫夫曼树的结点列表
        def get_nodes(self, bytes_array):
            nodes = []
            dic = {}
            for i in bytes_array:
                if i not in dic:
                    dic[i] = 1
                else:
                    dic[i] += 1
            # 给键值对 排序(可以有可无)
            dic_list = sorted(dic.items(), key=itemgetter(0), reverse=False)
            for item in dic_list:
                nodes.append(TreeNode(item[0], item[1]))
            return nodes
    
        # 构建赫夫曼树,返回赫夫曼树的根结点
        def create_huffman_tree(self, nodes):
            while len(nodes) > 1:
                nodes.sort(key=operator.attrgetter("weight"))
                # 取出根结点权值最小的两颗二叉树(结点)
                left_node = nodes.pop(0)
                right_node = nodes.pop(0)
                # 构建一棵新的二叉树,它的根结点,没有val,只有weight
                parent_node = TreeNode(0, left_node.weight + right_node.weight)
                parent_node.left = left_node  # 将父结点和左结点链接起来
                parent_node.right = right_node
                # 将parent_node加入nodes
                nodes.append(parent_node)
            return nodes[0]  # 返回根结点即可
    
        # 获取赫夫曼编码表
        def get_codes(self, node, path, temp):
            if node is None:
                return
            if node.left is None and node.right is None:
                temp[str(node.val)] = path
                return temp
            if node.left:
                self.get_codes(node.left, path + "0", temp)
            if node.right:
                self.get_codes(node.right, path + "1", temp)
            return temp
    
        def zip_codes(self, codes_array, srt_content_byte, str_join):  # 参数:传入一个字节字符串,传入赫夫曼编码数组
            for item in srt_content_byte:
                str_join += str(codes_array.get(str(item)))
            byte_array = []
            final_byte_array = []
            for i in range(0, len(str_join), 8):  # 步长取8,从第二位开始,第一位是个空格
                byte_array.append(str_join[i:i + 8])
            for item in byte_array:
                if item[0] == "1":
                    final_byte_array.append(int(item, base=2) - 256)
                else:
                    final_byte_array.append(int(item, base=2))
            return final_byte_array
    
        def huffman_zip(self, bytes_array):
            '''
            封装
            :param bytes_array: 传入一个原始字节数组
            :return: 返回一个压缩字节数组
            '''
            nodes = self.get_nodes(bytes_array)
            huffman_tree_root = self.create_huffman_tree(nodes)
            codes_array = self.get_codes(huffman_tree_root, "", HuffmanCode.out_put_dic)
            get_zip_byte = self.zip_codes(codes_array, content_bytes, HuffmanCode.str_join)
            return codes_array, get_zip_byte
    
        def be_back_str(self, huffman_array, codes_dict):
            '''
            :param huffman_array: 最后返回的哈夫曼编码字节数组
            :param codes_dict: 最开始存放字节对应的编码,键值对为>>>字节:哈夫曼编码
            :return: 返回原来的字符串
            '''
            for i in range(len(huffman_array) - 1):
                if huffman_array[i] < 0:
                    HuffmanCode.str_join += str(bin(huffman_array[i] + 256))[2:]
                else:
                    add_zero = 8 - len(bin(huffman_array[i])[2:])
                    HuffmanCode.str_join += ("0" * add_zero + bin(huffman_array[i])[2:])
            if huffman_array[-1] < 0:
                HuffmanCode.str_join += bin(huffman_array[-1] + 256)[2:]
            else:
                HuffmanCode.str_join += bin(huffman_array[-1])[2:]
            # 键值逆置 方便查找,开始键位布局不好,只能这里修改了,哭了
            codes_dict = dict(zip(codes_dict.values(), codes_dict.keys()))
            # 切割赫夫曼编码字符串,比对字典,添加到查找的内容到列表
            i = 0
            while i < len(HuffmanCode.str_join):
                count = 1
                flag = True
                b = None
                while flag:
                    key = HuffmanCode.str_join[i:i + count]  # i不动,让count移动,指定到匹配一个字符串
                    b = codes_dict.get(key)  # get()方法,如果没找到会返回一个None
                    if b is None:
                        count += 1
                    else:
                        flag = False
                HuffmanCode.final_bytes.append(b)
                i += count
            temp = " "
            for item in HuffmanCode.final_bytes:
                temp += str(chr(int(item)))
            return temp
    
    
    if __name__ == '__main__':
        content = "i like like like java do you like a java"
        content_bytes = content.encode('utf-8')
        h = HuffmanCode()
        final = h.huffman_zip(content_bytes)
        print(final[1])
        last_back_str = h.be_back_str(final[1], final[0])
        print(last_back_str)
    '''
    [-88, -65, -56, -65, -56, -65, -50, -31, -57, 4, -24, -78, -117, -4, -57, 112, -228]
     i like like like java do you like a java 
    '''
    
    展开全文
  • 1、哈夫曼树 1.1哈夫曼树基本介绍 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl) 达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree) 路径:在一棵树中,从一个结点往...

    1、哈夫曼树

    1.1哈夫曼树基本介绍

    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl) 达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)

    • 路径:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径
    • 路径长度:通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1
    • 结点的权:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权
    • 结点的带权路径长度:从根结点到该结点之间的路径长度与该结点的权的乘积
    • 树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL(weighted path length)

    比如:
    对于下图二叉树结构中的13结点
    权值:13
    路径:1——>5——>13
    路径长度:3-1=2
    带权路径长度:13 x 2 = 26
    该二叉树的带权路径长度为:13x2+7x2+8x2+3x2=62
    在这里插入图片描述
    哈夫曼树的特点:

    • 权值越大的结点离根结点越近
    • 树的带权路径长度WPL最小

    1.2哈夫曼树的创建

    构成哈夫曼树的步骤:

    1. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一棵最简单的二叉树
    2. 取出根节点权值最小的两棵二叉树
    3. 组成一棵新的二叉树, 该新的二叉树的根节点的权值是前面两棵二叉树根节点权值的和
    4. 再将这棵新的二叉树,以根节点的权值大小与之前剩下的二叉树进行再次排序,
    5. 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一棵哈夫曼树

    题目:要求把数列 {13, 7, 8, 3, 29, 6, 1},转成一棵哈夫曼树.

    图解
    1、排序:1, 3, 6, 7, 8, 13, 29
    2、找到最小根结点值最小的两棵二叉树,1,3构建如下二叉树在这里插入图片描述
    3、再进行排序:4,6,7,8,13,29 取4,6构建如下二叉树
    在这里插入图片描述
    4、再进行排序:7,8,10,13,29 取7,8构建如下二叉树
    在这里插入图片描述
    5、再进行排序:10,13,15,29 取10,13构建如下二叉树
    在这里插入图片描述
    6、再进行排序:15,23,29 取15,23 构建如下二叉树
    在这里插入图片描述
    7、再进行排序:29,38 取29,38 得到最终的哈夫曼树
    在这里插入图片描述

    代码实现:

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    // 创建结点类
    // 为了让Node 对象持续排序Collections集合排序
    // 让Node 实现Comparable接口
    class Node implements Comparable<Node> {
    	int value; // 结点权值
    	Node left; // 指向左子结点
    	Node right; // 指向右子结点
    	//写一个前序遍历
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}	
    	public Node(int value) {
    		this.value = value;
    	}
    	@Override
    	public String toString() {
    		return "Node [value=" + value + "]";
    	}
    	@Override
    	//一个内部比较器实现权值集合排序
    	public int compareTo(Node o) {
    		// TODO Auto-generated method stub
    		// 表示从小到大排序
    		return this.value - o.value;
    	}
    
    }
    public class HuffmanTree {
    	public static void main(String[] args) {
    		int arr[] = { 13, 7, 8, 3, 29, 6, 1 };
    		Node root = createHuffmanTree(arr);	
    		//测试一把
    		System.out.println("前序遍历已经创建好的哈夫曼树:");
    		preOrder(root); //
    		
    	}	
    	//编写一个前序遍历的方法
    	public static void preOrder(Node root) {
    		if(root != null) {
    			root.preOrder();
    		}else{
    			System.out.println("是空树,不能遍历~~");
    		}
    	}
    	// 创建赫夫曼树的方法
    	/**
    	 * 
    	 * @param arr 需要创建成哈夫曼树的数组
    	 * @return 创建好后的赫夫曼树的root结点
    	 */
    	public static Node createHuffmanTree(int[] arr) {
    		// 第一步为了操作方便
    		// 1. 遍历 arr 数组
    		// 2. 将arr的每个元素构成成一个Node
    		// 3. 将每个Node 放入到ArrayList中
    		int num=0;//记录排序的次数
    		List<Node> nodes = new ArrayList<Node>();
    		for (int value : arr) {
    			nodes.add(new Node(value));
    		}
    		
    		//我们处理的过程是一个循环的过程	
    		while(nodes.size() > 1) {		
    			//排序 从小到大 
    			Collections.sort(nodes);		
    			num++;
    			System.out.println("第"+num+"次排序nodes =" + nodes);		
    			//取出根节点权值最小的两颗二叉树 
    			//(1) 取出权值最小的结点(二叉树)
    			Node leftNode = nodes.get(0);
    			//(2) 取出权值第二小的结点(二叉树)
    			Node rightNode = nodes.get(1);
    			
    			//(3)构建一颗新的二叉树
    			Node parent = new Node(leftNode.value + rightNode.value);
    			parent.left = leftNode;
    			parent.right = rightNode;
    			
    			//(4)从ArrayList删除处理过的二叉树
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    			//(5)将parent加入到nodes
    			nodes.add(parent);
    		}	
    		//返回哈夫曼树的root结点
    		return nodes.get(0);		
    	}
    }
    
    1次排序nodes =[Node [value=1], Node [value=3], Node [value=6], Node [value=7], Node [value=8], Node [value=13], Node [value=29]]2次排序nodes =[Node [value=4], Node [value=6], Node [value=7], Node [value=8], Node [value=13], Node [value=29]]3次排序nodes =[Node [value=7], Node [value=8], Node [value=10], Node [value=13], Node [value=29]]4次排序nodes =[Node [value=10], Node [value=13], Node [value=15], Node [value=29]]5次排序nodes =[Node [value=15], Node [value=23], Node [value=29]]6次排序nodes =[Node [value=29], Node [value=38]]
    前序遍历已经创建好的哈夫曼树:
    Node [value=67]
    Node [value=29]
    Node [value=38]
    Node [value=15]
    Node [value=7]
    Node [value=8]
    Node [value=23]
    Node [value=10]
    Node [value=4]
    Node [value=1]
    Node [value=3]
    Node [value=6]
    Node [value=13]
    

    2、哈夫曼编码

    2.1哈夫曼编码的基本介绍

    哈夫曼编码(Huffman Coding)是一种编码方式, 属于一种程序算法
    哈夫曼编码是哈夫曼树在电讯通信中的经典的应用之一
    赫夫曼编码广泛地用于数据文件压缩,其压缩率通常在20%~90%之间
    赫夫曼码是可变字长编码(VLC) 的一种,Huffman于1952年提出一种编码方法,称之为最佳编码

    2.2编码原理解析

    1、通信领域中信息的处理方式1-定长编码:
    在这里插入图片描述
    缺点:所占字符长度太长消耗大量内存空间

    2、通信领域中信息的处理方式2-变长编码
    在这里插入图片描述
    缺点:不是前缀编码,编码匹配时会出现多义性(比如:上图中字符“a”的编码是1空格对应的编码是0,在解码过程中会把10对应的“i”解成“a”和空格)

    前缀编码:字符的编码都不能是其他字符编码的前缀, 即不能匹配到重复的编码

    3、通信领域中信息的处理方式3-赫夫曼编码
    i like like like java do you like a java // 共40个字符(包括空格)
    d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
    按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值.
    在这里插入图片描述
    根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为0 向右的路径为1 , 编码如下:
    o: 1000 u: 10010 d: 100110 y: 100111 i: 101 a : 110
    k: 1110 e: 1111 j: 0000 v: 0001 l: 001 : 01

    按照上面的赫夫曼编码,我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)
    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
    通过赫夫曼编码处理 长度为 133

    说明:

    • 原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
    • 此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性
    • 赫夫曼编码是无损处理方案

    注意:
    我们发现在构建哈夫曼树的过程中会有权值相同的结点,这时候就会产生问题,两个结点构成的新二叉树的根结点的权值与还未进出处理的多个结点权值相同,那这时到底应该排在它们的前面,中间还是后面呢?
    (通常是排在前面的)
    这种情况下排序方式的不同导致最后得到的哈夫曼树也不同,进而导致哈夫曼编码方式也会不同
    比如:上面的图片中的哈夫曼树是把已经构建好的二叉树排在权值相同的二叉树前面得到的,而下面这张图中的是排在后面得到的

    在这里插入图片描述
    虽然会导致编码方式不同,但是最后的编码长度还是133是不会变的

    2.3 哈夫曼编码的实现

    功能:需要创建 “i like like like java do you like a java” 对应的哈夫曼树
    思路:
    (1) Node { data (存放字符对应的ASCII码), weight (权值), left 和 right }
    (2) 得到 “i like like like java do you like a java” 对应的 byte[] 数组
    (3) 编写一个方法,将准备构建哈夫曼树的Node 节点放到 List , 形式 :[Node[date=97 ,weight = 5], Node[]date=32,weight = 9]…], 体现 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
    (4) 可以通过List 创建对应的哈夫曼树
    (5)向左的路径为0 向右的路径为1 ,得到哈夫曼编码表

    生成哈夫曼树对应的哈夫曼编码 , 如下表:
    =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011

    代码实现

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    //创建Node ,待数据和权值
    class Node implements Comparable<Node>  {
    	Byte data; // 存放数据(字符)本身,比如'a' => 97 ' ' => 32
    	int weight; //权值, 表示字符出现的次数
    	Node left;//
    	Node right;
    	public Node(Byte data, int weight) {
    		this.data = data;
    		this.weight = weight;
    	}
    	@Override
    	public int compareTo(Node o) {
    		// 从小到大排序
    		return this.weight - o.weight;
    	}
    	public String toString() {
    		return "Node [data = " + data + " weight=" + weight + "]";
    	}
    	//前序遍历
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    }
    
    public class HuffmanCode{
    	public static void main(String[] args) {	
    		String content = "i like like like java do you like a java";
    		byte[] contentBytes = content.getBytes();
    		System.out.println(contentBytes.length); //40
    		List<Node> nodes = getNodes(contentBytes);
    		System.out.println("nodes=" + nodes);
    		
    		//测试一把,创建的哈夫曼树
    		System.out.println("哈夫曼树");
    		Node huffmanTreeRoot = createHuffmanTree(nodes);
    		System.out.println("前序遍历");
    		huffmanTreeRoot.preOrder();
    		
    		//测试一把是否生成了对应的哈夫曼编码
    		Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    		System.out.println("~生成的哈夫曼编码表:" );
    		System.out.println( huffmanCodes);
    	}
    	
    	//生成哈夫曼树对应的哈夫曼编码
    		//思路:
    		//1. 将哈夫曼编码表存放在 Map<Byte,String> 形式
    		//   生成的哈夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    		static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
    		//2. 在生成哈夫曼编码表示,需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
    		static StringBuilder stringBuilder = new StringBuilder();	
    		//为了调用方便,重载 getCodes
    		private static Map<Byte, String> getCodes(Node root) {
    			if(root == null) {
    				return null;
    			}
    			//处理root的左子树
    			getCodes(root.left, "0", stringBuilder);
    			//处理root的右子树
    			getCodes(root.right, "1", stringBuilder);
    			return huffmanCodes;
    		}
    		
    		/**
    		 * 功能:将传入的node结点的所有叶子结点的赫夫曼编码得到,并放入到huffmanCodes集合
    		 * @param node  传入结点
    		 * @param code  路径: 左子结点是 0, 右子结点 1
    		 * @param stringBuilder 用于拼接路径
    		 */
    		private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    			StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    			//将code 加入到 stringBuilder2
    			stringBuilder2.append(code);
    			if(node != null) { //如果node == null不处理
    				//判断当前node 是叶子结点还是非叶子结点
    				if(node.data == null) { //非叶子结点
    					//递归处理
    					//向左递归
    					getCodes(node.left, "0", stringBuilder2);
    					//向右递归
    					getCodes(node.right, "1", stringBuilder2);
    				} else { //说明是一个叶子结点
    					//就表示找到某个叶子结点的最后
    					huffmanCodes.put(node.data, stringBuilder2.toString());
    				}
    			}
    		}
    		
    	//前序遍历的方法
    	private static void preOrder(Node root) {
    		if(root != null) {
    			root.preOrder();
    		}else {
    			System.out.println("哈夫曼树为空");
    		}
    	}
    	
    	/**
    	 * 
    	 * @param bytes 接收字节数组
    	 * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
    	 */
    	private static List<Node> getNodes(byte[] bytes) {		
    		//1创建一个ArrayList
    		ArrayList<Node> nodes = new ArrayList<Node>();
    		
    		//遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
    		Map<Byte, Integer> counts = new HashMap<>();
    		for (byte b : bytes) {
    			Integer count = counts.get(b);
    			if (count == null) { // Map还没有这个字符数据,第一次
    				counts.put(b, 1);
    			} else {
    				counts.put(b, count + 1);
    			}
    		}		
    		//把每一个键值对转成一个Node 对象,并加入到nodes集合
    		//遍历map
    		for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
    			nodes.add(new Node(entry.getKey(), entry.getValue()));
    		}
    		return nodes;		
    	}		
    	//可以通过List 创建对应的哈夫曼树
    	private static Node createHuffmanTree(List<Node> nodes) {		
    		while(nodes.size() > 1) {
    			//排序, 从小到大
    			Collections.sort(nodes);
    			//取出第一颗最小的二叉树
    			Node leftNode = nodes.get(0);
    			//取出第二颗最小的二叉树
    			Node rightNode = nodes.get(1);
    			//创建一颗新的二叉树,它的根节点 没有data, 只有权值
    			Node parent = new Node(null, leftNode.weight + rightNode.weight);
    			parent.left = leftNode;
    			parent.right = rightNode;
    			
    			//将已经处理的两颗二叉树从nodes删除
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    			//将新的二叉树,加入到nodes
    			nodes.add(parent);
    			
    		}
    		//nodes 最后的结点,就是哈夫曼树的根结点
    		return nodes.get(0);		
    	}
    }
    
    40
    nodes=[Node [data = 32 weight=9], Node [data = 97 weight=5], Node [data = 100 weight=1], Node [data = 101 weight=4], Node [data = 117 weight=1], Node [data = 118 weight=2], Node [data = 105 weight=5], Node [data = 121 weight=1], Node [data = 106 weight=2], Node [data = 107 weight=4], Node [data = 108 weight=4], Node [data = 111 weight=2]]
    哈夫曼树
    前序遍历
    Node [data = null weight=40]
    Node [data = null weight=17]
    Node [data = null weight=8]
    Node [data = 108 weight=4]
    Node [data = null weight=4]
    Node [data = 106 weight=2]
    Node [data = 111 weight=2]
    Node [data = 32 weight=9]
    Node [data = null weight=23]
    Node [data = null weight=10]
    Node [data = 97 weight=5]
    Node [data = 105 weight=5]
    Node [data = null weight=13]
    Node [data = null weight=5]
    Node [data = null weight=2]
    Node [data = 100 weight=1]
    Node [data = 117 weight=1]
    Node [data = null weight=3]
    Node [data = 121 weight=1]
    Node [data = 118 weight=2]
    Node [data = null weight=8]
    Node [data = 101 weight=4]
    Node [data = 107 weight=4]
    ~生成的哈夫曼编码表:
    {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    

    2.4 使用哈夫曼编码实现数据压缩与解压

    上面已经生成哈夫曼树对应的哈夫曼编码 , 如下表:
    =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011

    现在使用哈夫曼编码来生成哈夫曼编码数据 ,即按照上面的哈夫曼编码,将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如下:
    1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

    压缩数据:将上面得到的字符串哈夫曼编码转成一个压缩后的字节数组
    解压数据:将压缩得到的字节数组解压为原字符串

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    //创建Node ,待数据和权值
    class Node implements Comparable<Node>  {
    	Byte data; // 存放数据(字符)本身,比如'a' => 97 ' ' => 32
    	int weight; //权值, 表示字符出现的次数
    	Node left;//
    	Node right;
    	public Node(Byte data, int weight) {
    		this.data = data;
    		this.weight = weight;
    	}
    	@Override
    	public int compareTo(Node o) {
    		// 从小到大排序
    		return this.weight - o.weight;
    	}
    	public String toString() {
    		return "Node [data = " + data + " weight=" + weight + "]";
    	}
    	//前序遍历
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    }
    
    public class test{
    	public static void main(String[] args) {	
    		String content = "i like like like java do you like a java";
    		byte[] contentBytes = content.getBytes();
    		System.out.println(contentBytes.length); //40
    		List<Node> nodes = getNodes(contentBytes);
    		System.out.println("nodes=" + nodes);
    		
    		//测试一把,创建的哈夫曼树
    		System.out.println("哈夫曼树");
    		Node huffmanTreeRoot = createHuffmanTree(nodes);
    		System.out.println("前序遍历");
    		huffmanTreeRoot.preOrder();
    		
    		//测试一把是否生成了对应的哈夫曼编码
    		Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    		System.out.println("~生成的哈夫曼编码表:" );
    		System.out.println( huffmanCodes);
    		
    		System.out.println(content);
    		//测试,得到哈夫曼编码处理后的byte[]数组
    		byte[] huffmanCodeBytes = zip(contentBytes, huffmanCodes);
    		System.out.println("huffmanCodeBytes=" + Arrays.toString(huffmanCodeBytes));//17
    		
    		//解压数据
    		System.out.println("将压缩后的Byte数组解压为原字符串:");
    		byte[] sourceBytes = decode(huffmanCodes,huffmanCodeBytes);
    		System.out.println("原来的字符串="+ new String(sourceBytes));
    	}
    	//完成数据的解压
    		//思路
    		//1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    		//   重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
    		//2.  赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码  =》 "i like like like java do you like a java"
    		//编写一个方法,完成对压缩数据的解码
    		/**
    		 * 
    		 * @param huffmanCodes 哈夫曼编码表 map
    		 * @param huffmanBytes 哈夫曼编码得到的字节数组
    		 * @return 就是原来的字符串对应的数组
    		 */
    		private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
    			//1. 先得到 huffmanBytes 对应的 二进制的字符串 , 形式 1010100010111...
    			StringBuilder stringBuilder = new StringBuilder();
    			//将byte数组转成二进制的字符串
    			for(int i = 0; i < huffmanBytes.length; i++) {
    				byte b = huffmanBytes[i];
    				//判断是不是最后一个字节
    				boolean flag = (i == huffmanBytes.length - 1);
    				stringBuilder.append(byteToBitString(!flag, b));
    			}
    			//把字符串安装指定的哈夫曼编码进行解码
    			//把哈夫曼编码表进行调换,因为反向查询 a->100 100->a
    			Map<String, Byte>  map = new HashMap<String,Byte>();
    			for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
    				map.put(entry.getValue(), entry.getKey());
    			}
    			
    			//创建要给集合,存放byte
    			List<Byte> list = new ArrayList<>();
    			//i 可以理解成就是索引,扫描 stringBuilder 
    			for(int  i = 0; i < stringBuilder.length(); ) {
    				int count = 1; // 小的计数器
    				boolean flag = true;
    				Byte b = null;
    				
    				while(flag) {
    					//1010100010111...
    					//递增的取出 key 1 
    					String key = stringBuilder.substring(i, i+count);//i 不动,让count移动,指定匹配到一个字符
    					b = map.get(key);
    					if(b == null) {//说明没有匹配到
    						count++;
    					}else {
    						//匹配到
    						flag = false;
    					}
    				}
    				list.add(b);
    				i += count;//i 直接移动到 count	
    			}
    			//当for循环结束后,我们list中就存放了所有的字符  "i like like like java do you like a java"
    			//把list 中的数据放入到byte[] 并返回
    			byte b[] = new byte[list.size()];
    			for(int i = 0;i < b.length; i++) {
    				b[i] = list.get(i);
    			}
    			return b;
    			
    		}
    		/**
    		 * 将一个byte 转成一个二进制的字符串, 如果看不懂,可以参考我讲的Java基础 二进制的原码,反码,补码
    		 * @param b 传入的 byte
    		 * @param flag 标志是否需要补高位如果是true ,表示需要补高位,如果是false表示不补, 如果是最后一个字节,无需补高位
    		 * @return 是该b 对应的二进制的字符串,(注意是按补码返回)
    		 */
    		private static String byteToBitString(boolean flag, byte b) {
    			//使用变量保存 b
    			int temp = b; //将 b 转成 int
    			//如果是正数我们还存在补高位
    			if(flag) {
    				temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
    			}
    			String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
    			if(flag) {
    				return str.substring(str.length() - 8);
    			} else {
    				return str;
    			}
    		}
    	//编写一个方法,将字符串对应的byte[] 数组,通过生成的赫夫曼编码表,返回一个哈夫曼编码 压缩后的byte[]
    		/**
    		 * 
    		 * @param bytes 这时原始的字符串对应的 byte[]
    		 * @param huffmanCodes 生成的赫夫曼编码map
    		 * @return 返回赫夫曼编码处理后的 byte[] 
    		 * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
    		 * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
    		 * => 对应的 byte[] huffmanCodeBytes  ,即 8位对应一个 byte,放入到 huffmanCodeBytes
    		 * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
    		 * huffmanCodeBytes[1] = -88
    		 */
    		private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    			
    			//1.利用 huffmanCodes 将  bytes 转成  赫夫曼编码对应的字符串
    			StringBuilder stringBuilder = new StringBuilder();
    			//遍历bytes 数组 
    			for(byte b: bytes) {
    				stringBuilder.append(huffmanCodes.get(b));
    			}
    			
    			System.out.println("字符串对应的哈夫曼编码:" + stringBuilder.toString());
    			
    			//将 "1010100010111111110..." 转成 byte[]
    			
    			//统计返回  byte[] huffmanCodeBytes 长度
    			//一句话 int len = (stringBuilder.length() + 7) / 8;
    			int len;
    			if(stringBuilder.length() % 8 == 0) {
    				len = stringBuilder.length() / 8;
    			} else {
    				len = stringBuilder.length() / 8 + 1;
    			}
    			//创建 存储压缩后的 byte数组
    			byte[] huffmanCodeBytes = new byte[len];
    			int index = 0;//记录是第几个byte
    			for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8
    					String strByte;
    					if(i+8 > stringBuilder.length()) {//不够8位
    						strByte = stringBuilder.substring(i);
    					}else{
    						strByte = stringBuilder.substring(i, i + 8);
    					}	
    					//将strByte 转成一个byte,放入到 huffmanCodeBytes
    					huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
    					index++;
    			}
    			return huffmanCodeBytes;
    		}
    	//生成赫夫曼树对应的赫夫曼编码
    		//思路:
    		//1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
    		//   生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    		static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
    		//2. 在生成赫夫曼编码表示,需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
    		static StringBuilder stringBuilder = new StringBuilder();	
    		//为了调用方便,重载 getCodes
    		private static Map<Byte, String> getCodes(Node root) {
    			if(root == null) {
    				return null;
    			}
    			//处理root的左子树
    			getCodes(root.left, "0", stringBuilder);
    			//处理root的右子树
    			getCodes(root.right, "1", stringBuilder);
    			return huffmanCodes;
    		}
    		
    		/**
    		 * 功能:将传入的node结点的所有叶子结点的赫夫曼编码得到,并放入到huffmanCodes集合
    		 * @param node  传入结点
    		 * @param code  路径: 左子结点是 0, 右子结点 1
    		 * @param stringBuilder 用于拼接路径
    		 */
    		private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    			StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    			//将code 加入到 stringBuilder2
    			stringBuilder2.append(code);
    			if(node != null) { //如果node == null不处理
    				//判断当前node 是叶子结点还是非叶子结点
    				if(node.data == null) { //非叶子结点
    					//递归处理
    					//向左递归
    					getCodes(node.left, "0", stringBuilder2);
    					//向右递归
    					getCodes(node.right, "1", stringBuilder2);
    				} else { //说明是一个叶子结点
    					//就表示找到某个叶子结点的最后
    					huffmanCodes.put(node.data, stringBuilder2.toString());
    				}
    			}
    		}
    		
    	//前序遍历的方法
    	private static void preOrder(Node root) {
    		if(root != null) {
    			root.preOrder();
    		}else {
    			System.out.println("赫夫曼树为空");
    		}
    	}
    	
    	/**
    	 * 
    	 * @param bytes 接收字节数组
    	 * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
    	 */
    	private static List<Node> getNodes(byte[] bytes) {		
    		//1创建一个ArrayList
    		ArrayList<Node> nodes = new ArrayList<Node>();
    		
    		//遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
    		Map<Byte, Integer> counts = new HashMap<>();
    		for (byte b : bytes) {
    			Integer count = counts.get(b);
    			if (count == null) { // Map还没有这个字符数据,第一次
    				counts.put(b, 1);
    			} else {
    				counts.put(b, count + 1);
    			}
    		}		
    		//把每一个键值对转成一个Node 对象,并加入到nodes集合
    		//遍历map
    		for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
    			nodes.add(new Node(entry.getKey(), entry.getValue()));
    		}
    		return nodes;		
    	}		
    	//可以通过List 创建对应的赫夫曼树
    	private static Node createHuffmanTree(List<Node> nodes) {		
    		while(nodes.size() > 1) {
    			//排序, 从小到大
    			Collections.sort(nodes);
    			//取出第一颗最小的二叉树
    			Node leftNode = nodes.get(0);
    			//取出第二颗最小的二叉树
    			Node rightNode = nodes.get(1);
    			//创建一颗新的二叉树,它的根节点 没有data, 只有权值
    			Node parent = new Node(null, leftNode.weight + rightNode.weight);
    			parent.left = leftNode;
    			parent.right = rightNode;
    			
    			//将已经处理的两颗二叉树从nodes删除
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    			//将新的二叉树,加入到nodes
    			nodes.add(parent);
    			
    		}
    		//nodes 最后的结点,就是赫夫曼树的根结点
    		return nodes.get(0);		
    	}
    }
    
    40
    nodes=[Node [data = 32 weight=9], Node [data = 97 weight=5], Node [data = 100 weight=1], Node [data = 101 weight=4], Node [data = 117 weight=1], Node [data = 118 weight=2], Node [data = 105 weight=5], Node [data = 121 weight=1], Node [data = 106 weight=2], Node [data = 107 weight=4], Node [data = 108 weight=4], Node [data = 111 weight=2]]
    哈夫曼树
    前序遍历
    Node [data = null weight=40]
    Node [data = null weight=17]
    Node [data = null weight=8]
    Node [data = 108 weight=4]
    Node [data = null weight=4]
    Node [data = 106 weight=2]
    Node [data = 111 weight=2]
    Node [data = 32 weight=9]
    Node [data = null weight=23]
    Node [data = null weight=10]
    Node [data = 97 weight=5]
    Node [data = 105 weight=5]
    Node [data = null weight=13]
    Node [data = null weight=5]
    Node [data = null weight=2]
    Node [data = 100 weight=1]
    Node [data = 117 weight=1]
    Node [data = null weight=3]
    Node [data = 121 weight=1]
    Node [data = 118 weight=2]
    Node [data = null weight=8]
    Node [data = 101 weight=4]
    Node [data = 107 weight=4]
    ~生成的哈夫曼编码表:
    {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    i like like like java do you like a java
    字符串对应的哈夫曼编码:1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
    huffmanCodeBytes=[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    将压缩后的Byte数组解压为原字符串:
    原来的字符串=i like like like java do you like a java
    

    文件压缩:读取文件——>得到哈夫曼编码表——>进行压缩
    文件解压:读取压缩文件——>根据哈夫曼编码表——>完成解压

    import java.io.FileInputStream;
    import java.io.FileOutputStream;
    import java.io.InputStream;
    import java.io.ObjectInputStream;
    import java.io.ObjectOutputStream;
    import java.io.OutputStream;
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    public class HuffmanCode {
    	public static void main(String[] args) {	
    		//测试压缩文件
    		String srcFile = "C://Users//zhukun//Desktop//测试//01.docx";
    	    String dstFile = "C://Users//zhukun//Desktop//测试//01.zip";		
    		zipFile(srcFile, dstFile);
    		System.out.println("压缩文件ok~~");	
    		
    //		//测试解压文件
    //		String zipFile = "C://Users//zhukun//Desktop//01.zip";
    //		String dstFile = "C://Users//zhukun//Desktop//02.docx";
    //		unZipFile(zipFile, dstFile);
    //		System.out.println("解压成功!");
    	
    	}
    	//编写一个方法,完成对压缩文件的解压
    	/**
    	 * 
    	 * @param zipFile 准备解压的文件
    	 * @param dstFile 将文件解压到哪个路径
    	 */
    	public static void unZipFile(String zipFile, String dstFile) {	
    		//定义文件输入流
    		InputStream is = null;
    		//定义一个对象输入流
    		ObjectInputStream ois = null;
    		//定义文件的输出流
    		OutputStream os = null;
    		try {
    			//创建文件输入流
    			is = new FileInputStream(zipFile);
    			//创建一个和  is关联的对象输入流
    			ois = new ObjectInputStream(is);
    			//读取byte数组  huffmanBytes
    			byte[] huffmanBytes = (byte[])ois.readObject();
    			//读取赫夫曼编码表
    			Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
    			
    			//解码
    			byte[] bytes = decode(huffmanCodes, huffmanBytes);
    			//将bytes 数组写入到目标文件
    			os = new FileOutputStream(dstFile);
    			//写数据到 dstFile 文件
    			os.write(bytes);
    		} catch (Exception e) {
    			// TODO: handle exception
    			System.out.println(e.getMessage());
    		} finally {
    			
    			try {
    				os.close();
    				ois.close();
    				is.close();
    			} catch (Exception e2) {
    				// TODO: handle exception
    				System.out.println(e2.getMessage());
    			}
    			
    		}
    	}
    	
    	//编写方法,将一个文件进行压缩
    	/**
    	 * 
    	 * @param srcFile 你传入的希望压缩的文件的全路径
    	 * @param dstFile 我们压缩后将压缩文件放到哪个目录
    	 */
    	public static void zipFile(String srcFile, String dstFile) {
    		
    		//创建输出流
    		OutputStream os = null;
    		ObjectOutputStream oos = null;
    		//创建文件的输入流
    		FileInputStream is = null;
    		try {
    			//创建文件的输入流
    			is = new FileInputStream(srcFile);
    			//创建一个和源文件大小一样的byte[]
    			byte[] b = new byte[is.available()];
    			//读取文件
    			is.read(b);
    			//直接对源文件压缩
    			byte[] huffmanBytes = huffmanZip(b);
    			//创建文件的输出流, 存放压缩文件
    			os = new FileOutputStream(dstFile);
    			//创建一个和文件输出流关联的ObjectOutputStream
    			oos = new ObjectOutputStream(os);
    			//把 赫夫曼编码后的字节数组写入压缩文件
    			oos.writeObject(huffmanBytes); //我们是把
    			//这里我们以对象流的方式写入 赫夫曼编码,是为了以后我们恢复源文件时使用
    			//注意一定要把赫夫曼编码 写入压缩文件
    			oos.writeObject(huffmanCodes);			
    		}catch (Exception e) {
    			// TODO: handle exception
    			System.out.println(e.getMessage());
    		}finally {
    			try {
    				is.close();
    				oos.close();
    				os.close();
    			}catch (Exception e) {
    				// TODO: handle exception
    				System.out.println(e.getMessage());
    			}
    		}	
    	}
    	//完成数据的解压
    	//思路
    	//1. 将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
    	//   重写先转成 赫夫曼编码对应的二进制的字符串 "1010100010111..."
    	//2.  赫夫曼编码对应的二进制的字符串 "1010100010111..." =》 对照 赫夫曼编码  =》 "i like like like java do you like a java"
    	//编写一个方法,完成对压缩数据的解码
    	/**
    	 * 
    	 * @param huffmanCodes 赫夫曼编码表 map
    	 * @param huffmanBytes 赫夫曼编码得到的字节数组
    	 * @return 就是原来的字符串对应的数组
    	 */
    	private static byte[] decode(Map<Byte,String> huffmanCodes, byte[] huffmanBytes) {
    		//1. 先得到 huffmanBytes 对应的 二进制的字符串 , 形式 1010100010111...
    		StringBuilder stringBuilder = new StringBuilder();
    		//将byte数组转成二进制的字符串
    		for(int i = 0; i < huffmanBytes.length; i++) {
    			byte b = huffmanBytes[i];
    			//判断是不是最后一个字节
    			boolean flag = (i == huffmanBytes.length - 1);
    			stringBuilder.append(byteToBitString(!flag, b));
    		}
    		//把字符串安装指定的赫夫曼编码进行解码
    		//把赫夫曼编码表进行调换,因为反向查询 a->100 100->a
    		Map<String, Byte>  map = new HashMap<String,Byte>();
    		for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
    			map.put(entry.getValue(), entry.getKey());
    		}
    		
    		//创建要给集合,存放byte
    		List<Byte> list = new ArrayList<>();
    		//i 可以理解成就是索引,扫描 stringBuilder 
    		for(int  i = 0; i < stringBuilder.length(); ) {
    			int count = 1; // 小的计数器
    			boolean flag = true;
    			Byte b = null;
    			
    			while(flag) {
    				//1010100010111...
    				//递增的取出 key 1 
    				String key = stringBuilder.substring(i, i+count);//i 不动,让count移动,指定匹配到一个字符
    				b = map.get(key);
    				if(b == null) {//说明没有匹配到
    					count++;
    				}else {
    					//匹配到
    					flag = false;
    				}
    			}
    			list.add(b);
    			i += count;//i 直接移动到 count	
    		}
    		//当for循环结束后,我们list中就存放了所有的字符  "i like like like java do you like a java"
    		//把list 中的数据放入到byte[] 并返回
    		byte b[] = new byte[list.size()];
    		for(int i = 0;i < b.length; i++) {
    			b[i] = list.get(i);
    		}
    		return b;
    		
    	}
     	
    	/**
    	 * 将一个byte 转成一个二进制的字符串, 如果看不懂,可以参考我讲的Java基础 二进制的原码,反码,补码
    	 * @param b 传入的 byte
    	 * @param flag 标志是否需要补高位如果是true ,表示需要补高位,如果是false表示不补, 如果是最后一个字节,无需补高位
    	 * @return 是该b 对应的二进制的字符串,(注意是按补码返回)
    	 */
    	private static String byteToBitString(boolean flag, byte b) {
    		//使用变量保存 b
    		int temp = b; //将 b 转成 int
    		//如果是正数我们还存在补高位
    		if(flag) {
    			temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
    		}
    		String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
    		if(flag) {
    			return str.substring(str.length() - 8);
    		} else {
    			return str;
    		}
    	}
    	
    	//使用一个方法,将前面的方法封装起来,便于我们的调用.
    	/**
    	 * 
    	 * @param bytes 原始的字符串对应的字节数组
    	 * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
    	 */
    	private static byte[] huffmanZip(byte[] bytes) {
    		List<Node> nodes = getNodes(bytes);
    		//根据 nodes 创建的赫夫曼树
    		Node huffmanTreeRoot = createHuffmanTree(nodes);
    		//对应的赫夫曼编码(根据 赫夫曼树)
    		Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
    		//根据生成的赫夫曼编码,压缩得到压缩后的赫夫曼编码字节数组
    		byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
    		return huffmanCodeBytes;
    	}
    	
    	
    	//编写一个方法,将字符串对应的byte[] 数组,通过生成的赫夫曼编码表,返回一个赫夫曼编码 压缩后的byte[]
    	/**
    	 * 
    	 * @param bytes 这时原始的字符串对应的 byte[]
    	 * @param huffmanCodes 生成的赫夫曼编码map
    	 * @return 返回赫夫曼编码处理后的 byte[] 
    	 * 举例: String content = "i like like like java do you like a java"; =》 byte[] contentBytes = content.getBytes();
    	 * 返回的是 字符串 "1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100"
    	 * => 对应的 byte[] huffmanCodeBytes  ,即 8位对应一个 byte,放入到 huffmanCodeBytes
    	 * huffmanCodeBytes[0] =  10101000(补码) => byte  [推导  10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
    	 * huffmanCodeBytes[1] = -88
    	 */
    	private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
    		
    		//1.利用 huffmanCodes 将  bytes 转成  赫夫曼编码对应的字符串
    		StringBuilder stringBuilder = new StringBuilder();
    		//遍历bytes 数组 
    		for(byte b: bytes) {
    			stringBuilder.append(huffmanCodes.get(b));
    		}
    		
    		//System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());
    		
    		//将 "1010100010111111110..." 转成 byte[]
    		
    		//统计返回  byte[] huffmanCodeBytes 长度
    		//一句话 int len = (stringBuilder.length() + 7) / 8;
    		int len;
    		if(stringBuilder.length() % 8 == 0) {
    			len = stringBuilder.length() / 8;
    		} else {
    			len = stringBuilder.length() / 8 + 1;
    		}
    		//创建 存储压缩后的 byte数组
    		byte[] huffmanCodeBytes = new byte[len];
    		int index = 0;//记录是第几个byte
    		for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长 +8
    				String strByte;
    				if(i+8 > stringBuilder.length()) {//不够8位
    					strByte = stringBuilder.substring(i);
    				}else{
    					strByte = stringBuilder.substring(i, i + 8);
    				}	
    				//将strByte 转成一个byte,放入到 huffmanCodeBytes
    				huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
    				index++;
    		}
    		return huffmanCodeBytes;
    	}
    	
    	//生成赫夫曼树对应的赫夫曼编码
    	//思路:
    	//1. 将赫夫曼编码表存放在 Map<Byte,String> 形式
    	//   生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
    	static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
    	//2. 在生成赫夫曼编码表示,需要去拼接路径, 定义一个StringBuilder 存储某个叶子结点的路径
    	static StringBuilder stringBuilder = new StringBuilder();
    	
    	
    	//为了调用方便,我们重载 getCodes
    	private static Map<Byte, String> getCodes(Node root) {
    		if(root == null) {
    			return null;
    		}
    		//处理root的左子树
    		getCodes(root.left, "0", stringBuilder);
    		//处理root的右子树
    		getCodes(root.right, "1", stringBuilder);
    		return huffmanCodes;
    	}
    	
    	/**
    	 * 功能:将传入的node结点的所有叶子结点的赫夫曼编码得到,并放入到huffmanCodes集合
    	 * @param node  传入结点
    	 * @param code  路径: 左子结点是 0, 右子结点 1
    	 * @param stringBuilder 用于拼接路径
    	 */
    	private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    		//将code 加入到 stringBuilder2
    		stringBuilder2.append(code);
    		if(node != null) { //如果node == null不处理
    			//判断当前node 是叶子结点还是非叶子结点
    			if(node.data == null) { //非叶子结点
    				//递归处理
    				//向左递归
    				getCodes(node.left, "0", stringBuilder2);
    				//向右递归
    				getCodes(node.right, "1", stringBuilder2);
    			} else { //说明是一个叶子结点
    				//就表示找到某个叶子结点的最后
    				huffmanCodes.put(node.data, stringBuilder2.toString());
    			}
    		}
    	}
    	
    	//前序遍历的方法
    	private static void preOrder(Node root) {
    		if(root != null) {
    			root.preOrder();
    		}else {
    			System.out.println("赫夫曼树为空");
    		}
    	}
    	
    	/**
    	 * 
    	 * @param bytes 接收字节数组
    	 * @return 返回的就是 List 形式   [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......],
    	 */
    	private static List<Node> getNodes(byte[] bytes) {
    		//1创建一个ArrayList
    		ArrayList<Node> nodes = new ArrayList<Node>();	
    		//遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
    		Map<Byte, Integer> counts = new HashMap<>();
    		for (byte b : bytes) {
    			Integer count = counts.get(b);
    			if (count == null) { // Map还没有这个字符数据,第一次
    				counts.put(b, 1);
    			} else {
    				counts.put(b, count + 1);
    			}
    		}		
    		//把每一个键值对转成一个Node 对象,并加入到nodes集合
    		//遍历map
    		for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
    			nodes.add(new Node(entry.getKey(), entry.getValue()));
    		}
    		return nodes;
    		
    	}
    	//可以通过List 创建对应的赫夫曼树
    	private static Node createHuffmanTree(List<Node> nodes) {
    		while(nodes.size() > 1) {
    			//排序, 从小到大
    			Collections.sort(nodes);
    			//取出第一颗最小的二叉树
    			Node leftNode = nodes.get(0);
    			//取出第二颗最小的二叉树
    			Node rightNode = nodes.get(1);
    			//创建一颗新的二叉树,它的根节点 没有data, 只有权值
    			Node parent = new Node(null, leftNode.weight + rightNode.weight);
    			parent.left = leftNode;
    			parent.right = rightNode;	
    			//将已经处理的两颗二叉树从nodes删除
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    			//将新的二叉树,加入到nodes
    			nodes.add(parent);		
    		}
    		//nodes 最后的结点,就是赫夫曼树的根结点
    		return nodes.get(0);	
    	}
    }
    
    //创建Node ,待数据和权值
    class Node implements Comparable<Node>  {
    	Byte data; // 存放数据(字符)本身,比如'a' => 97 ' ' => 32
    	int weight; //权值, 表示字符出现的次数
    	Node left;//
    	Node right;
    	public Node(Byte data, int weight) {
    		
    		this.data = data;
    		this.weight = weight;
    	}
    	@Override
    	public int compareTo(Node o) {
    		// 从小到大排序
    		return this.weight - o.weight;
    	}
    	public String toString() {
    		return "Node [data = " + data + " weight=" + weight + "]";
    	}	
    	//前序遍历
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    }
    
    展开全文
  • 包含实验报告,题目等等,十分详细,物超所值
  • 数据结构实践课-哈夫曼树-文件的压缩解压(MFC)
  • C语言哈夫曼树压缩/解压器 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。 新的...

    C语言哈夫曼树压缩/解压器

    小编是大一的菜鸡,这个题目是数据结构的一个实验题,为了完成这个作业,查找了各种资料,借鉴了很多人的代码,前后折腾了三天左右。代码可能跟网上的不一样,大佬路过请不要踩我。

    温馨提醒

    建议先认真学习Huffman树、文件操作、位或与等相关知识。代码小编已经加了很多标注,如果有不清楚的地方欢迎交流~

    原理

    建立Huffman树,可以获得权值总和最小的二叉树,对叶子结点用0或1进行二进制编码,由于一个字节的二进制含有8位,将字符转换为二进制进行存储,可以大大减小存储空间。

    头文件

    #include<stdio.h>
    #include<stdlib.h>
    #include<string>//需用到strcpy()
    #define MAX_SIZE 100//文件名长度
    #define ERROR -1
    #define OK 1``
    

    哈夫曼树存储结构

    typedef struct {
        unsigned int weight;//字符权重
        unsigned int parent, lchild, rchild;
    }HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
    typedef char** HuffmanCode;//动态分配数组存储哈夫曼编码表
    

    哈夫曼树相关函数

    这些函数基本上都是在严蔚敏的《数据结构》上抄过来的

    void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, unsigned int* w, int n) {
        //这里的w为无符号类型
        Create_HuffmanTree(HT, w, n);
        Create_HT_Codelist(HT, HC, n);
    }
    
    void Create_HuffmanTree(HuffmanTree& HT, unsigned int* w, int n) {
        if (n <= 1) 
            return;
        int m = 2 * n - 1;//结点数
        HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));//多出一个未用的0号单元
        if (!HT) 
            exit(ERROR);
        HTNode* p=HT+1;//跳过0号单元
        int i = 1;
        for (; i <= n; i++, p++)
            *p = { w[i-1],0,0,0 };//n个结点初始化,课本是用*w,最后w++,这里是为防止w[0]地址的丢失
        for (; i <= m; ++i, ++p) 
            *p = { 0,0,0,0 };//大于n的结点初始化
        for (i = n + 1; i <= m; ++i) {
            //建立哈夫曼树
            //在HT[i..i-1]选择parent为0且weight最小的两个结点,其序号分别为s1和s2
            int s1, s2;
            Select(HT, i - 1, s1, s2);
            HT[s1].parent = i; HT[s2].parent = i;
            HT[i].lchild = s1; HT[i].rchild = s2;//对左右子树的权值大小没有要求
            HT[i].weight = HT[s1].weight + HT[s2].weight;
        }
    }
    
    void Create_HT_Codelist(HuffmanTree HT, HuffmanCode& HC, int n) {
        HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));//分配n个字符编码的头指针
        char* cd = (char*)malloc(n * sizeof(char));//分配求编码的工作空间
        if ((!cd)||(!HC)) 
            exit(ERROR);
        cd[n - 1] = '\0';//编码最多有n-1位,最后一位定义位编码结束符
        int start;//编码结束符位置
        int c;
        for (int i = 1; i <= n; i++) {
            //逐个字符求哈夫曼编码
            start = n - 1;
            c = i;
            int f = HT[i].parent;
            for (; f != 0; c = f, f = HT[f].parent) 
                //从叶子到根逆向求编码
                if (HT[f].lchild == c)
                    cd[--start] = '0';
                else 
                    cd[--start] = '1';//左0右1
            HC[i] = (char*)malloc((n - start) * sizeof(char));//第0个不用,为第i个字符编码分配空间,'\0'也被存入
            if (!HC[i]) 
                exit(ERROR);
            strcpy_s(HC[i],n-start, &cd[start]);//从cd复制编码(串)到HC
        }
        free(cd);
    }//Creat_HT_Codelist
    

    Select函数是自己写的

    void Select(HuffmanTree T, int n, int&s1, int&s2) {
        if (n <= 1) 
            exit(ERROR);
        unsigned int m1 = 4294967295; unsigned int m2 = 4294967295;//最大值
        for(int i=1;i<=n;i++)
            if ((T[i].weight < m1)&&(T[i].parent==0)) {
                m1 = T[i].weight;
                s1 = i;
            }
        for (int i = 1; i <= n; i++) 
            if ((T[i].weight < m2) && (i != s1) && (T[i].parent == 0)) {
                //要确保s1跟s2不相等,结果为s1对应元素的权值<=s2
                m2 = T[i].weight;
                s2 = i;
            } 
    }
    

    压缩函数

    void Compress(char in_file_name[], char out_file_name[]) {
        FILE* f1,*f2;//f1为待压缩文件指针,f2为压缩后文件指针
        fopen_s(&f1, in_file_name, "rb");
        if (!f1)
            exit(ERROR);
       // fseek(f1, 0L, SEEK_SET);
        fseek(f1, 0L, SEEK_END);//将文件指针移到末尾
        unsigned long long FileSize = ftell(f1);//记录文件总字节数
        fseek(f1, 0L, SEEK_SET);//将指针移到开头
        unsigned int *FullWeight=(unsigned int *)malloc(256*sizeof(unsigned int));//记录256个字符是否存在及权值
        for (int i = 0; i < 256; i++)
            FullWeight[i] = 0;//初始化
        for (unsigned long long i = 0; i < FileSize; i++)//将文件的全部字符一个个读取出来
            FullWeight[(unsigned char)fgetc(f1)]++;//char转换为unsigned
        fclose(f1);
        int count=0;//字符种数
        for (int i = 0; i < 256; i++) 
            if (FullWeight[i]) 
                count++;
        unsigned char* CharSet = (unsigned char*)malloc(count * sizeof(unsigned char));//记录文件含有的字符
        unsigned int* WeightSet = (unsigned int*)malloc(count * sizeof(unsigned int));//记录字符的权值
        if (!CharSet || !WeightSet)
            exit(ERROR);
        int j=0;//最后的结果j=count-1
        for (int i = 0; i < 256; i++) 
            if (FullWeight[i]) {
                CharSet[j] = i;//字符表种字母顺序为26个英文字母的顺序
                WeightSet[j] = FullWeight[i];
                j++;
            }
        free(FullWeight);
        HuffmanTree HT;
        HuffmanCode HC;
        HuffmanCoding(HT, HC, WeightSet, count);
        fopen_s(&f2, out_file_name, "wb");//以二进制的形式写入
        if(!f2)
            exit(ERROR);
        fwrite(&count, sizeof(int), 1, f2);//写入字符个数
        //fwrite(&FileSize, sizeof(unsigned long long), 1, f2);//写入原文件字节总数
        //2n个哈夫曼树元素写入
        fwrite(HT, sizeof(HTNode), 2*count, f2);
        fwrite(CharSet, sizeof(unsigned char), count, f2);//写入字符表
        fwrite(WeightSet, sizeof(unsigned int), count, f2);//写入权值表
        //以下开始编码
        int offset = 8;//龙哥这里为7,记录一个字节内剩余位数
        int a = 0;//字符在CharSet里的位置
        unsigned char ReadByte;//读取的一个字节
        unsigned char TempByte=0;//暂时存储要写入的编码
        unsigned long long BitSize = 0;//记录位数,方便进行解压
        fopen_s(&f1, in_file_name, "rb");//以二进制的形式写入
        if (!f1)
            exit(ERROR);
        for (unsigned long long i = 0; i < FileSize; i++) {
            fread(&ReadByte, sizeof(unsigned char), 1, f1);
            a = 0;
            for (;; a++) 
                if (CharSet[a] == ReadByte) 
                    break;
            for (int b = 0; HC[a+1][b]; b++) {
                //若读到'\0',则跳出
                //第一个没用,为HC[a+1][b]
                TempByte = (TempByte << 1) | (HC[a+1][b] - '0');//利用位或TempByte左移一位并写入一位
                BitSize++;
                offset--;
                if (offset == 0) {
                    //字节8位已填满
                    offset = 8;//重置为8位
                    fwrite(&TempByte, sizeof(unsigned char), 1, f2);
                    TempByte = 0;
                }
            }
        }
        if (offset != 8) {
            //若最后一个字节用不完,也要强行用到8位
            TempByte <<= offset;
            fwrite(&TempByte, sizeof(unsigned char), 1, f2);
        }
        fwrite(&BitSize, sizeof(unsigned long long), 1, f2);//将位数写在文件的最后
        fclose(f1);
        fclose(f2);
        free(HT);
        free(HC);
        free(CharSet);
        free(WeightSet);
        printf("已成功压缩!");
    }
    

    压缩后的文件内容按顺序为:文件的字符种数count、哈夫曼树HT、字符表CharSet、权值表WeightSet、压缩后内容、文件的总位数

    解压函数

    void Decompress(char in_file_name[], char out_file_name[]) {
        int count;
        FILE * f1, * f2;//f1为in,f2为out
       // HuffmanCode HC;
        HuffmanTree HT;
        unsigned long long BitSize;
        unsigned char* CharSet;
        unsigned int* WeightSet;
        fopen_s(&f1, in_file_name, "rb");//用“rb”
        if (!f1)
            exit(ERROR);
        fread(&count, sizeof(int), 1, f1);//读取字符种数count
        HT = (HuffmanTree)malloc(2 * count * sizeof(HTNode));
        CharSet = (unsigned char*)malloc(count * sizeof(unsigned char));
        WeightSet = (unsigned int*)malloc(count * sizeof(unsigned int));
        if ((!HT) || (!CharSet) || (!WeightSet))
            exit(ERROR);
        fread(HT, sizeof(HTNode), 2 * count, f1);//读取哈夫曼树
        fread(CharSet, sizeof(unsigned char), count, f1);//读取字符表
        fread(WeightSet, sizeof(unsigned int), count, f1);//读取权值表
      //  Create_HT_Codelist(HT, HC, count);//建立编码表
        fseek(f1, -1L * sizeof(unsigned long long), SEEK_END);//跳到末尾
        fread(&BitSize, sizeof(unsigned long long), 1, f1);//读取位数
        //跳过文件头
        fseek(f1, sizeof(int) + 2 * count * sizeof(HTNode) + count * sizeof(unsigned char) + count * sizeof(unsigned int), SEEK_SET);
        //fseek(Enc, (long)(sizeof(unsigned char) + 2 * count * sizeof(HTNode) + count * sizeof(unsigned char) + count * sizeof(unsigned int)), SEEK_SET);
        unsigned char TempByte = 0;
        unsigned char ReadByte;
        int offset = 8;
        int Index = 2 * count - 1;//根节点
        fopen_s(&f2, out_file_name, "wb");//打开目标文件
        if (!f2)
            exit(ERROR);
        fread(&ReadByte, sizeof(unsigned char), 1, f1);
        for (unsigned long long a = 0; a < BitSize; a++) {
            TempByte = 1 & (ReadByte >> 7);//位与判断ReadByte的位为1还是0
            if (TempByte)//从根结点开始寻找
                Index = HT[Index].rchild;
            else
                Index = HT[Index].lchild;
            if ((!HT[Index].lchild) && (!HT[Index].rchild)) {
                //遇到了根节点
                fwrite(&CharSet[Index - 1], sizeof(unsigned char), 1, f2);//由于HT有0号单元,故需-1
                Index = 2 * count - 1;
            }
            offset--;
            ReadByte = ReadByte << 1;//舍弃第一位
            if (offset == 0) {
                //字节的8位用完
                fread(&ReadByte, sizeof(unsigned char), 1, f1);
                offset = 8;
            }
        }
        free(CharSet);
        free(WeightSet);
        free(HT);
        fclose(f1);
        fclose(f2);
        printf("解压成功!");
    }
    

    主函数

    主函数相当简单

    int main() {
        puts("--------------------------欢迎使用Jay牌压缩程序---------------------------");
        puts("输入数字“1”进行压缩");
        puts("输入数字“2”进行解压");
        puts("输入数字“3”则退出");
        puts("--------------------------------------------------------------------------");
        int mark;
        char in_file_name[MAX_SIZE];//待压缩&&待解压文件名
        char out_file_name[MAX_SIZE];//解压后&&压缩后文件名
        for (;;) {
            printf("输入选项:");
            scanf_s("%d", &mark);
            getchar();//取掉回车字符
            switch (mark) {
            case 1:printf("请输入待压缩的文件路径:");//绝对还是相对路径?
                scanf_s("%s", in_file_name, MAX_SIZE); getchar();
                printf("请输入压缩后的文件路径:");
                scanf_s("%s", out_file_name, MAX_SIZE); getchar();
                Compress(in_file_name, out_file_name); break;
            case 2:printf("请输入待解压的文件路径:");
                scanf_s("%s", in_file_name, MAX_SIZE); getchar();
                printf("请输入压缩后的文件路径:");
                scanf_s("%s", out_file_name, MAX_SIZE);无getchar();
                Decompress(in_file_name, out_file_name); break;
            case 3:return 0;
            default:printf("请输入有效数字!");
            }
            putchar('\n');
        }
        return 0;
    }
    

    运行结果

    w

    展开全文
  • c语言哈夫曼树

    2011-09-16 18:50:14
    高手所写,绝对给力。 利用哈夫曼树原理解压与压缩所有文件。文件利用正规的c语言代码编写方式,能够适应众多的编译环境。
  • Java小程序之哈夫曼树与文件压缩和解压缩(二)文件解压篇 一、解压原理: 了解了压缩原理之后,要解压文件就是压缩文件的逆过程;拿昨天的例子来说,如果我们收到这样一串二进制1 1 01 1 1 01 00(昨天漏掉了...

    Java小程序之哈夫曼树与文件压缩和解压缩(三)文件解压篇

    一、解压原理:
    了解了压缩原理之后,要解压文件就是压缩文件的逆过程;拿昨天的例子来说,如果我们收到这样一串二进制1 1 01 1 1 01 00(昨天漏掉了一个问题,这里是9个0 1,每8个一个字节,那么剩下的那个0需要补7个0,构成一个完整的字节,这样才能写出文件)怎么解压出aabbac呢?很自然的想到,我们需要拿到对应的哈夫曼编码;a的编码是1,b的编码是01,c的编码是00;拿到这个编码后,我们开始对这个0 1串分割,先取出一个0或1,看是否有对应的编码,如上,我们先取第一个1,编码中有1的编码,对应a,那么把第一个1还原为a,接下来,再去一个0或1,得到1,编码中有1,对应a,那么还原为a,接下来去0,没有编码,取01对应b,把01还原为b......以此类推
    有人会怀疑这样的正确性,不会解压错误吗?比如如果编码中有1 和11,那么11改怎么还原呢?是解析成两个1进行还原,还是解析成一个11进行还原呢?其实不用担心,这就是哈夫曼编码的优势,哈夫曼编码中不会出现这样的问题;不相信的话,你可以自己去检验下;

    将这么多,其实很简单,就类似于情报的破解,我只要有密码本就可以了;而哈夫曼编码就是我们的密码本;

    二、哈夫曼树文件解压实现:
    文件的压缩和解压缩是两个相对独立的程序;所以,我们在把压缩数据写入文件之前,需要把该文件对应的哈夫曼编码一起写入文件,相当于解压时的密码本;
    所以,昨天的压缩程序还少了一步,就是把编码写入压缩文件中;我们只需把每个字母对应的哈夫曼编码的长度以及所有字母对应的哈夫曼编码写入文件即可;


    读取文件的时候,先读取每个哈夫曼编码的长度,在根据长度去分割写入的哈夫曼编码,同时把哈夫曼编码写入对应的位置即可;如上图所示,前面的96长度都是0,不需要分割哈夫曼编码;97的长度是1,则分割1,并把1存入对应的字符数组中;同时分割01,把01存储在字符数组的第98个位置;以此类推;

    难点:处理不够8位01的写入,记得把补0的个数一起写入文件;

    三、整个思路整理如下:



    四、压缩工程源代码和解压缩工程源代码:
    两个独立的工程,代码不共享;
    用压缩工程压缩的文件,可以用解压缩的工程文件解压缩;

    压缩工程源代码:
    HuffmNode类和昨天的一样,就不上传了;

    更改后的compress类:
    package com.huaxin.compress;
    
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    import java.util.LinkedList;
    
    public class Compress {
    	
    	public int [] times = new int[256];
    	public String [] HuffmCodes=new String[256];
    	public LinkedList<HuffmNode> list = new LinkedList<HuffmNode>();
    	//统计次数
    	
    	//初始化
    	public Compress(){
    		for (int i = 0; i < HuffmCodes.length; i++) {
    			HuffmCodes[i]="";
    		}
    	}
    	
    	public void countTimes(String path) throws Exception{
    		//构造文件输入流
    		FileInputStream fis = new FileInputStream(path);
    		//读取文件
    		int value=fis.read();
    		while(value!=-1){
    			times[value]++;
    			value=fis.read();
    		}
    		//关闭流
    		fis.close();
    	}
    	
    	//构造哈夫曼树
    	public HuffmNode createTree(){
    		//将次数作为权值构造森林
    		for (int i = 0; i < times.length; i++) {
    			if(times[i]!=0){
    				HuffmNode node = new HuffmNode(times[i],i);
    				//将构造好的节点加入到容器中的正确位置
    				list.add(getIndex(node), node);
    			}
    		}
    		
    		//将森林(容器中的各个节点)构造成哈夫曼树
    		while(list.size()>1) {
    			//获取容器中第一个元素(权值最小的节点)
    			HuffmNode firstNode =list.removeFirst();
    			//获取中新的第一个元素,原来的第一个元素已经被移除了(权值次小的节点)
    			HuffmNode secondNode =list.removeFirst();
    			//将权值最小的两个节点构造成父节点
    			HuffmNode fatherNode =
    					new HuffmNode(firstNode.getData()+secondNode.getData(),-1);
    			fatherNode.setLeft(firstNode);
    			fatherNode.setRight(secondNode);
    			//父节点加入到容器中的正确位置
    			list.add(getIndex(fatherNode),fatherNode);
    		}
    		//返回整颗树的根节点
    		return list.getFirst();
    	}
    	//利用前序遍历获取编码表
    	public void getHuffmCode(HuffmNode root,String code){
    		//往左走,哈夫曼编码加0
    		if(root.getLeft()!=null){
    			getHuffmCode(root.getLeft(),code+"0");
    		}
    		//往右走,哈夫曼编码加1
    		if(root.getRight()!=null){
    			getHuffmCode(root.getRight(),code+"1");
    		}
    		//如果是叶子节点,返回该叶子节点的哈夫曼编码
    		if(root.getLeft()==null && root.getRight()==null){
    //			System.out.println(root.getIndex()+"的编码为:"+code);
    			HuffmCodes[root.getIndex()]=code;
    		}
    	}
    	
    	//压缩文件
    	public void compress(String path,String destpath) throws Exception{
    		
    		
    		
    		//构建文件输出流
    		FileOutputStream fos = new FileOutputStream(destpath);
    		FileInputStream fis = new FileInputStream(path);
    		/**===============把码表写入文件================*/
    		//将整个哈夫曼编码以及每个编码的长度写入文件
    		String code ="";
    		for (int i = 0; i < 256; i++) {
    			fos.write(HuffmCodes[i].length());
    			code+=HuffmCodes[i];
    			fos.flush();
    		}
    		//把哈夫曼编码写入文件
    		
    //		System.out.println("code="+code);
    		String str1="";
    		while(code.length()>=8){
    			str1=code.substring(0, 8);
    			int c=changeStringToInt(str1);
    //			System.out.println(c);
    			fos.write(c);
    			fos.flush();
    			code=code.substring(8);
    		}
    		//处理最后一个不为8的数
    		int last=8-code.length();
    		for (int i = 0; i <last; i++) {
    			code+="0";
    		}
    		str1=code.substring(0, 8);
    		int c=changeStringToInt(str1);
    		fos.write(c);
    		fos.flush();
    		
    		/**===============将数据写入到文件中================*/
    		
    		//读文件,并将对应的哈夫曼编码串接成字符串
    		int value=fis.read();
    		String str = "";
    		while(value!=-1){
    			str+=HuffmCodes[value];
    //			System.out.println((char)value+":"+str);
    			value=fis.read();
    		}
    		System.out.println(str);
    		fis.close();
    		
    			String s="";
    			//将字符8位分割,对弈一个字节
    			while(str.length()>=8){
    				s=str.substring(0, 8);
    				int b=changeStringToInt(s);
    //				System.out.println(c);
    				fos.write(b);
    				fos.flush();
    				str=str.substring(8);
    			}
    			
    			//最后不够8位添0
    			int last1=8-str.length();
    			for (int i = 0; i <last1; i++) {
    				str+="0";
    			}
    			s=str.substring(0, 8);
    //			System.out.println(s);
    			int d=changeStringToInt(s);
    			fos.write(d);
    			
    			//压缩后不够补0的个数暂
    			fos.write(last1);
    			fos.flush();
    			
    			fos.close();
    	
    	}
    	
    	//插入元素位置的索引
    	public int getIndex(HuffmNode node) {
    		for (int i = 0; i < list.size(); i++) {
    			if(node.getData()<=list.get(i).getData()){
    				return i;
    			}
    		}
           return list.size();
    	}
    	
    	//将字符串转换成整数
    	public int changeStringToInt(String s){
    		int v1=(s.charAt(0)-48)*128;
    		int v2=(s.charAt(1)-48)*64;
    		int v3=(s.charAt(2)-48)*32;
    		int v4=(s.charAt(3)-48)*16;
    		int v5=(s.charAt(4)-48)*8;
    		int v6=(s.charAt(5)-48)*4;
    		int v7=(s.charAt(6)-48)*2;
    		int v8=(s.charAt(7)-48)*1;
    		return v1+v2+v3+v4+v5+v6+v7+v8;
    			
    	}
    }
    

    重新测试了一个文件,Test也做了一下更改:

    package com.huaxin.compress;
    
    public class Test {
    	public static void main(String[] args) throws Exception {
    		//创建压缩对象
    		Compress compress = new Compress();
    		//统计文件中0-255出现的次数
    		compress.countTimes("C:\\Users\\Administrator\\Desktop\\my.docx");
    		//构造哈夫曼树,并得到根节点
    		HuffmNode root=compress.createTree();
    		//得到哈夫曼编码
    		compress.getHuffmCode(root, "");
    		//压缩文件
    		compress.compress("C:\\Users\\Administrator\\Desktop\\my.docx",
    				"C:\\Users\\Administrator\\Desktop\\my.docx.zip");
    		
    	}
    
    }
    



    解压工程源代码:
    package com.huaxin.decompress;
    
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.FileOutputStream;
    
    public class Decompress {
    	
    	//每个编码的长度
    	public int [] codelengths = new int [256];
    	//对应的哈夫曼编码值
    	public String [] codeMap=new String[256];
    	
    	public static void main(String[] args) {
    		
    		Decompress d = new Decompress();
    		d.decompress("C:\\Users\\Administrator\\Desktop\\my.docx.zip",
    				"C:\\Users\\Administrator\\Desktop\\mydecompress.docx");
    	
    	}
    	
    	/*
    	 * 解压思路:
    	 * 1、读取文件里面的码表
    	 * 2、得到码表
    	 * 3、读取数据
    	 * 4、还原数据
    	 */
    	
    	public void decompress(String srcpath,String destpath) {
    		
    		try {
    			FileInputStream fis = new FileInputStream(srcpath);
    			FileOutputStream fos = new FileOutputStream(destpath);
    			int value;
    			int codeLength=0;
    			String code="";
    			//还原码表
    			for (int i = 0; i < codelengths.length; i++) {
    				value=fis.read();
    				codelengths[i]=value;
    //				System.out.println(times[i]);
    				codeLength+=codelengths[i];
    			}
    			
    			//得到总长度
    			//将总长度除以8的到字节个数
    			int len=codeLength/8;
    			//如果不是8的倍数,则字节个数加1(对应压缩补0的情况)
    			if((codeLength)%8!=0){
    				len++;
    			}
    			//读取哈夫曼编码
    //			System.out.println("codeLength:"+len);
    			for (int i = 0; i < len; i++) {
    				//把读到的整数转换成二进制
    				code+=changeIntToString(fis.read());
    				
    			}
    //			System.out.println("哈夫曼编码:"+code);
    			
    			for (int i = 0; i < codeMap.length; i++) {
    				//如果第i个位置不为0 ,则说明第i个位置存储有哈夫曼编码
    				if(codelengths[i]!=0){
    					//将得到的一串哈夫曼编码按照长度分割分割
    					String ss=code.substring(0, codelengths[i]);
    					codeMap[i]=ss;
    					code=code.substring(codelengths[i]);
    				}else{
    					//为0则没有对应的哈夫曼编码
    					codeMap[i]="";
    				}
    			}
    			
    			//读取压缩的文件内容
    			String codeContent="";
    			while(fis.available()>1){
    				codeContent+=changeIntToString(fis.read());
    			}
    			//读取最后一个
    			value=fis.read();
    			//把最后补的0给去掉
    			codeContent=codeContent.substring(0, codeContent.length()-value);
    				
    			for (int i = 0; i < codeContent.length(); i++) {
    				
    				String codecontent=codeContent.substring(0, i+1);
    				
    				for (int j = 0; j < codeMap.length; j++) {
    					if(codeMap[j].equals(codecontent)){
    //						System.out.println("截取的字符串:"+codecontent);
    						fos.write(j);
    						fos.flush(); 
    						codeContent=codeContent.substring(i+1);
    //						System.out.println("截取后剩余编码长度:"+codeContent.length());
    //						count=1;
    						i=-1;
    						break;
    					}
    			}
    			}
    //			}
    			
    			fos.close();
    			fis.close();
    			
    		} catch (Exception e) {
    			e.printStackTrace();
    		}
    		
    
    	}
    	
    	//十进制转二进制字符串
    	public String changeIntToString(int value) {
    		String s="";
    		for (int i = 0; i < 8; i++) {
    			s=value%2+s;
    			value=value/2;
    		}
    		return s;
    	}
    
    }
    

    五、运行结果:字节大小相同




    打开文件后文件内容相同






    问题:为什么压缩后的文件反而更大了?


    答:因为我们写了很多与该问价解压的内容进去;平时的压缩一般是针对大文件的;举个简单的例子,你用系统的压缩软件,压缩一个只要几个字节的文本,你会发现,压缩文件也变得比原文件更大了;

    六、总结
    通过这个项目,学到了一些和数据结构相关的知识,其实也算是回顾吧。毕竟自己也学过数据结构这门课程;但重要的是,通过文件压缩与解压缩这个项目,把所学的数据结构用到了项目中,这是重要的;这个项目需要自己多思考,绝不是一下就能搞明白的,尤其是自学的人;还是根据思路,慢慢琢磨,仔细明白其中的原理吧;
    题外话,今天我们做了这段时间的Java项目总结;感觉自己还是需要多锻炼;上台发言还是有点紧张,语速过快;希望下次有更好的表现;在华信,在路上,让我们一起走上人生的巅峰;
    共勉!



    展开全文
  • 7.9 哈夫曼树(Huffman Tree)

    千次阅读 2019-08-15 17:39:02
    哈夫曼树原理,及构造方法 概述 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值...
  • 之前做的一个数据结构作业,通过哈夫曼树实现对文本的压缩与解压,参考了很多网上的方法,因为时间有限,注释并没有写,但是代码缩进还是比较清晰。 另外,哈夫曼树我单独写了个头文件,是在之前写二叉树类的基础上...
  • 1.哈夫曼树 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用。 结点之间的路径长度:从一个结点到另一个结点之间的分支...
  • 本篇博文将介绍什么是哈夫曼树,并且如何在java语言中构建一棵哈夫曼树,怎么利用哈夫曼树实现对文件的压缩和解压。首先,先来了解下什么哈夫曼树。   一、哈夫曼树 哈夫曼树属于二叉树,即树的结点最多拥有2个...
  • 本篇博文将介绍什么是哈夫曼树,并且如何在java语言中构建一棵哈夫曼树,怎么利用哈夫曼树实现对文件的压缩和解压。首先,先来了解下什么哈夫曼树。 一、哈夫曼树 哈夫曼树属于二叉树,即树的结点最多拥有2个...
  • 文章目录1、先掌握几个概念1.1 什么是路径?...  先听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也成为哈夫曼树(Huf...
  • 数据结构之哈夫曼树

    千次阅读 2019-06-20 16:22:00
    哈夫曼树 1.1基本介绍 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。 赫夫曼树是带权...
  • 首先这里的文本是指可以转字符串的(其他文件的...一个哈弗曼中离根节点最近的叶子 权重最大字符串/文本统计“ 我说切克,你说闹,呦呦切克闹,我们一起切克闹.” , : 3 —>0x01 闹 : 3 –>0x02 说 : 2 –>0x
  • 用python实现哈夫曼树与哈夫曼编码,并通过哈夫曼编码压缩核酸序列信息。
  • 哈夫曼树压缩和解压缩

    千次阅读 2019-01-17 20:53:12
    不知不觉放寒假了,时间很快,我大概是从去年的九月多开始学了java,到现在也差不多有四个月了,java基础呢也就写了几个小的管理系统,总感觉缺少点什么,当时是报着玩的心态,...今天的主题是哈夫曼树的编码,译码...
  • 1)给定n个权值(节点的值)作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为 赫夫曼树(哈夫曼树、霍夫曼树,最优二叉树)。 2)赫夫曼树是带权路径长度最短的树,权值较大...
  • 哈夫曼树制作压缩软件 太爱bandzip了,在这里推荐这款压缩软件(我的是低仿) 以下为自己软件图片 要求: (1)压缩对象为外存任意格式任意位置的文件。 (2)运行时,压缩原文件的规模应不小于5K。运行后,外存上...
  • 利用哈夫曼树实现文件压缩

    千次阅读 2017-02-27 10:51:49
    2.根据字符出现的次数构建哈夫曼树(得出字符的哈夫曼编码)。 3.根据字符的哈夫曼编码进行转换、压缩,然后创建压缩文件。 4.读取压缩文件,读出哈夫曼编码和字符的对照表。解压缩。 数据结构的设计: 1.保存字符...
  • Java小程序之哈夫曼树与文件压缩和解压缩(二)文件压缩篇 一、初识压缩与解压缩原理 压缩可以理解为:对文件的加密过程 解压可以理解为:对文件的解密过程 例如: 我 - a 是 - b 谁 - c 我是谁 - 》 abc 二...
  • 哈夫曼树算法压缩文件

    千次阅读 2016-03-12 15:22:31
    具体原理是:文件是由一个个字节组成,而字节有自己的ASCII码值,然后用一个整形数组把文件的ASCII码值记下来,出现了一个就在其对应的ASCII值得int数组下标加一。然后用哈夫曼算法处理这个整形数组,得到哈夫曼编码...
  • 哈夫曼树实现文件压缩与解压缩

    万次阅读 多人点赞 2016-06-06 21:23:14
    见识了360压缩的神奇后,想要实现自己的文件压缩程序,然后花了近一个星期的时间去完成文件压缩与解压缩,期间有很多坑,花了很长时间去调试它,最后把坑给填了(真心的感受到...在解压缩小文件时不会出现的问题在解压
  • 构建distance
  • 树包括堆、二叉树、哈夫曼树等。 图包括有向图、无向图、最小生成树、最短路径等(就职于高德地图的算法工程师,图的知识必须完全掌握(ง •̀_•́)ง)。 背包、栈、链表和队列在之前的一篇博文《基础大扫荡——...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 545
精华内容 218
关键字:

哈夫曼树解压原理