赫夫曼树 订阅
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 展开全文
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
信息
外文名
Huffman Tree
又    名
最优树
带权路径长度
WPL
中文名
哈夫曼树
路径长度
根结点到第L层结点路径长度为L-1
应    用
哈夫曼编码
哈夫曼树简介
在计算机数据处理中,哈夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节,即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
收起全文
精华内容
下载资源
问答
  • 赫夫曼树
    2022-03-06 19:53:38

    (一)树中一些概念

    路径:从某一结点到其根结点的通路,其中的分支数目称为路径长度

    权:可以给结点赋值称为它的权,带权路径长度就是权乘以路径长度

    树的带权路径长度:所有叶子结点的带权路径长度之和(wpl)。wpl最小的树最优,就是赫夫曼树,这样权越大的结点离根越近。

    (二)赫夫曼树排列

    所有结点的权重按从小到大放在一个序列中,最小两位相加,结果再放入序列,依次循环。最后根据它们每两个相加的关系组装二叉树。

    实现结点:

    public class HuffmanNode implements Comparable<HuffmanNode> {
    	private int weight;
    	private HuffmanNode left;
    	private HuffmanNode right;
    	public HuffmanNode(int w) {
    		this.weight=w;
    	}
    	
    	public int getWeight() {
    		return weight;
    	}
    
    	public void setWeight(int weight) {
    		this.weight = weight;
    	}
    
    	public HuffmanNode getLeft() {
    		return left;
    	}
    
    	public void setLeft(HuffmanNode left) {
    		this.left = left;
    	}
    
    	public HuffmanNode getRight() {
    		return right;
    	}
    
    	public void setRight(HuffmanNode right) {
    		this.right = right;
    	}
    	
    	@Override
    	public String toString() {
    		return "HuffmanNode [weight=" + weight + "]";
    	}
    
    	//实现一个比较器便于比较权重大小
    	@Override
    	public int compareTo(HuffmanNode o) {
    		// TODO Auto-generated method stub
    		return this.weight-o.weight;
    	}
    	//采用前序遍历
    	public void preList() {
    		System.out.println(this);
    		if (this.left!=null) {
    			this.left.preList();
    		}
    		if (this.right!=null) {
    			this.right.preList();
    		}
    	}
    }
    

    实现赫夫曼树:

    /*
    	 * 定义将int数组转换为huffman树的方法
    	 */
    	public static HuffmanNode convert(int[] array) { 
    		//因为结点实现了比较器,所以可以新建一个集合装入结点
    		//结点就会按权重大小排序
    		List<HuffmanNode> list=new ArrayList<HuffmanNode>();
    		for (int i:array) {
    			list.add(new HuffmanNode(i));
    		}
    		/*
    		 * 将最小的两个权值相加,加起来的新结点过后重新
    		 * 放进集合中,再把这两个删除了,最终只剩下一个
    		 * 根结点,注意list集合的存取顺序是一致的
    		 * 要用Collections的sort()函数对其排序
    		 */
    		while(list.size()>1) {
    			Collections.sort(list);
    			HuffmanNode left=list.get(0);HuffmanNode right=list.get(1);
    			HuffmanNode newNode=new HuffmanNode(list.get(0).getWeight()+list.get(1).getWeight());
    	        newNode.setLeft(list.get(0));
    	        newNode.setRight(list.get(1));
    			list.add(newNode);
    	        list.remove(left);list.remove(right);
    		}
    		return list.get(0);
    	}

    更多相关内容
  • C语言实现赫夫曼树的构建及赫夫曼编码的源代码,帮助你掌握Huffman编码的算法实现。赫夫曼树的建立,及实现其编码,和数据结构教材上的算法同步。基于C语言,模拟赫夫曼树的构造并对之进行编码。代码简洁,附报告书...
  • 本人本科期间学习数据结构写的实验,内容如下 1、输入一段报文,例如: CAST CAST SAT AT A TASA ... 2、建赫夫曼树,并输出各个字符的赫夫曼编码 3、输入编码01100……,能准确翻译成报文 4、要求有菜单。
  • 小弟写的赫夫曼树的构建及赫夫曼编码算法,可以实现根据字母频率对字母进行编码; 每一个字母的Huffman编码进文章进行编码;根据文章的Huffman序列,进行解码。
  • 赫夫曼树的构建和赫夫曼编码的获取,最基础的内容,将课程的伪代码变为了可运行的
  • 本篇文章对赫夫曼树编码的问题进行了分析说明,需要的朋友参考下
  • 赫夫曼树建立和编码

    2018-12-01 15:07:58
    赫夫曼树的创建及赫夫曼编码(通过修改txt文件获取不同的编码).zip,赫夫曼树的创建及赫夫曼编码(通过修改txt文件获取不同的编码),赫夫曼树的创建及赫夫曼编码,HTNTree.c,HTNTree.h,Constants.h,main.c,.DS_Store,...
  • 二叉树、赫夫曼树

    2018-05-22 17:09:09
    二叉树、赫夫曼树,自己用C++实现,包括树的创建、遍历等常用操作。
  • 赫夫曼树课程设计 这可是我的课程设计呀 亲自验证过 可以画树的
  • //算法5.11 根据赫夫曼树求赫夫曼编码 #include using namespace std; typedef struct { int weight; int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; void Select(HuffmanTree HT...
  • 赫夫曼树数据结构

    2018-01-03 08:31:24
    (2) 在森林中选出两个根结点的权值最小的合并,作为一棵新的左、右子,且新的根结点权值为其左、右子根结点权值之和; (3)从森林中删除选取的两棵,并将新加入森林; (4)重复(2)、(3)步,直到森林中只...
  • 构建赫夫曼树

    2016-07-27 14:22:50
    通过输入英文来构建赫夫曼树,并在当前目录下打印赫夫曼树图像
  • 1,赫夫曼树 1.1,赫夫曼树基本介绍及相关概念 给定n个权值作为n个叶子节点,构造一颗二叉树,若该树的**带权路径长度(WPL)**达到最小,称这样的的二叉树为最优二叉树,也称为赫夫曼树,或者哈夫曼树、霍夫曼树 ...

    1,赫夫曼树

    1.1,赫夫曼树基本介绍及相关概念

    • 给定n个权值作为n个叶子节点,构造一颗二叉树,若该树的**带权路径长度(WPL)**达到最小,称这样的的二叉树为最优二叉树,也称为赫夫曼树,或者哈夫曼树、霍夫曼树
    • 赫夫曼树是带权路径长度最短的数,权值较大的节点离根较近
    • 路径和路径长度:在一棵树中,从一个节点往下可以达到的孩子和孙子节点之间的通路,称为路径;通路中分支的数量称为路径长度;若规定根节点的层数为1,则从根节点到第L层节点的路径长度为L - 1
    • 节点的权及带权路径长度:若将树中的节点赋给一个有意义的值,则该值称为节点的权;从根节点到该节点的路径长度与该权值的乘积称为该节点的带权路径长度
    • 树的带权路径长度:树的带权路径长度规定为所有叶子节点的带权路径长度之和,记为WPL(Weighted path length),权值越大的节点离根节点越近的二叉树才是最优二叉树,如图:
      在这里插入图片描述

    1.2,赫夫曼树基本思想及示意图

    • 首先对要处理的数组从小到大进行排序,每一个数据都可以转换为一个节点,每一个节点都可以看为一个最简单的二叉树(不带左右子节点的二叉树)
    • 从转换好的有序节点集合中,取出两个最小的节点组成一颗二叉树
    • 在这颗新二叉树中,左右子节点分别为取出的两个节点,父节点为这两个子节点的带权路径和
    • 二叉树生成完成后,从节点集合中移除两个最小子节点,并将生成的二叉树父节点加入到集合中
    • 之后再次对集合排序并重复以上操作,直到集合中只有一个元素,这样说明赫夫曼树已经生成完成,可以对该树进行输出查看
    • 对一个数组{13,7,8,3,29,6,1}生成的赫夫曼树如图:
      在这里插入图片描述
    • 先对数组进行排序:{1,3,6,7,8,13,29}
    • 取出前两个元素:{1,3},生成一个新的二叉树,父节点为两个节点的带权路径和即:data = 1 * 1 + 3 * 1 = 4
    • 将两个节点从数组中移除,并添加父节点到数组中后重新排序,则新的数组元素为:{4,6,7,8,13,29},其中节点4存在{1,3}两个子节点
    • 以此类推,最终会生成上面的赫夫曼树

    1.3,赫夫曼树代码实现

    package com.self.datastructure.tree.huffman;
    
    import lombok.Data;
    import lombok.ToString;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * 赫夫曼树
     *
     * @author PJ_ZHANG
     * @create 2020-03-26 10:36
     **/
    public class HuffmanTree {
    
        public static void main(String[] args) {
            int[] array = {13, 7, 8, 3, 29, 6, 1};
            Node root = huffmanTree(array);
            preShowDetails(root);
        }
    
        /**
         * 生成赫夫曼树基本规则:
         * * 将数组的每个元素封装为Node, 并添加到集合中
         * * 对集合元素进行排序, 注意此处需要实现Comparable类, 并重写compareTo()
         * * 取前两个元素作为一个最简单的二叉树(不带子节点的)
         * * 以这两个元素作为一节点的左右两个子元素, 且该节点的权为这两个节点带权路径长度之和
         * * 将该父节点添加到集合中, 并对集合重新排序, 继续循环执行, 依次类推
         *
         * @param array
         */
        public static Node huffmanTree(int[] array) {
            // 转换为一个list
            List<Node> lstData = new ArrayList<>(10);
            for (int data : array) {
                lstData.add(new Node(data));
            }
            // 循环处理
            for (;lstData.size() > 1;) {
                // 对数组进行排序
                Collections.sort(lstData);
                // 获取前两个节点
                Node leftNode = lstData.get(0);
                Node rightNode = lstData.get(1);
                // 根据前两个节点带权路径构建第三个节点
                Node parentNode = new Node(leftNode.getData() + rightNode.getData());
                // 构建左右节点
                parentNode.setLeftNode(leftNode);
                parentNode.setRightNode(rightNode);
                // 移除前两个节点
                lstData.remove(leftNode);
                lstData.remove(rightNode);
                // 添加新构建的节点到集合中
                lstData.add(parentNode);
            }
            return lstData.get(0);
        }
    
        public static void preShowDetails(Node node) {
            if (null == node) {
                return;
            }
            System.out.print(node.getData() + "  ");
            if (null != node.getLeftNode()) {
                preShowDetails(node.getLeftNode());
            }
            if (null != node.getRightNode()) {
                preShowDetails(node.getRightNode());
            }
        }
    
        @Data
        static class Node implements Comparable<Node> {
    
            private int data;
    
            private Node leftNode;
    
            private Node rightNode;
    
            public Node(int data) {
                this.data = data;
            }
    
            @Override
            public String toString() {
                return "Node: [data = " + data;
            }
    
            /**
             * 进行数据比较, 满足数据升序排序
             * @param node
             * @return
             */
            @Override
            public int compareTo(Node node) {
                return this.data - node.getData();
            }
        }
    
    }
    

    2,赫夫曼编码

    2.1,赫夫曼编码基本介绍

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

    2.2,赫夫曼编码原理剖析

    2.2.1,定长编码

    • 定长编码是将传递文本首先按照ASCII码转换为数字类型,再对数字类型二进制化后进行传递,传递的信息即为原始文本直译,流程如下:
    • 如有原始文本:

    i like like like java do you like a java

    • 原始文本转换为ASCII码后如下:

    105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97

    • ASCII码二进制化后如下:

    01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001

    • 按照二进制传递消息,传递消息长度为 359(包括空格)

    2.2.2,变长编码

    • 定长编码是对原始文本的直译,传递信息较大,因此可以用变长编码进行重组
    • 同样一串原始文本,变长编码会对文本内容进行统计,统计各个字符的个数:

    // 字符统计
    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=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d

    • 字符统计完成后,根据字符所占个数,从大到小以二进制进行递增赋值。如空格出现次数最多,则赋值为0,其次是a,赋值01,再次i,赋值10,依次类推
    • 按照上面的方式,会对传递的编码进行组合,最终组合的传递文本肯定远小于定长编码
    • 但是变长编码存在问题:前缀重合。即存在部分字符的二进制表达式是其他字符的前缀,在解析中可能会存在混乱,如01和0101,不能确定是两个01还是一个完整的0101
    • 根据上面问题,提出了前缀编码概念,即字符的编码不能是其他字符编码的前缀,赫夫曼编码就是一种前缀编码

    2.2.3,赫夫曼编码

    • 同变长编码,赫夫曼编码同样会统计字符所占个数,并以该个数作为节点的权值构建赫夫曼树
    • 则按照字符统计频次: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

    • 按照上面的赫夫曼编码,原始文本字符串对应的编译后的编码应该为:

    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110

    • 字符长度为 133,直译字符长度为359,压缩比例超过60%
    • 同时,生成赫夫曼树后,每一个原始数组有效节点在赫夫曼树都以叶子节点存在,所以前缀不可能重复
    • 最后需要注意一个问题:赫夫曼树根据排序方式不同,虽然赫夫曼树的WPL完成相等,但生成的赫夫曼树会有些许差别。比如对于权值一样的节点排序,如果存在新生成父节点与原始节点权值相等,再排序时,将父节点放在前面与放在后面生成的赫夫曼树是不一致的;以上树为例,存在另外一种赫夫曼树组合方式
      在这里插入图片描述

    2.3,赫夫曼编码 — 数据压缩解压

    2.3.1,数据压缩逻辑

    • 先对需要传递的文本进行字符统计,并以单个字符出现的频次进行排序
    • 对排序生成的数组构建赫夫曼树,此处注意排序方式不同,构建的数不同,但树的WPL是一致的
    • 对赫夫曼树的每一个叶子节点,即有效数据节点进行路径统计,左侧节点路径代表为0,右侧节点路径代表为1,从根节点开始,每一个叶子节点都有唯一的路径表达,且符合前缀表达式
    • 将传递文本根据ASCII码进行拆分,并将每一个字符转换为对应的路径,最终生成一个二进制数字串
    • 此时生成的二进制串是远大于需要传递的文本长度的,需要对需要传递的串每八位进行截取,并生成一个byte类型的数字,最终转换成为一个byte[],此时这个字节数组以及上上一步生成的路径映射Map是真正需要传递出去的数据
    • 代码在解压部分一块附上

    2.3.2,数据解压逻辑

    • 对于解压部分来说,解压就是顺着压缩的步骤反向走一遍
    • 首先,解压初始化入参是能接受到压缩后传递的byte[]数组和路径映射Map
    • 先对byte[]数组二进制化,转换为二进制数字串,也就是每一个ASCII字符在赫夫曼树中对应路径组成的二进制数字串
    • 然后对路径映射Map进行反转,传递的是字符 -> 路径的映射,转换为路径 -> 字符的映射,转换完成后,可以直接通过路径获取目标字符,重组数据串
    • 因为二进数数组串满足前缀表达式,所以按二进制数字串的每一个字符依次向后移动,从反转后的Map中根据截取路径获取有效字符
      • 获取到后,拼接到结果串中,并以下一个字符作为起点,继续向后截取
      • 如果获取不到,则继续扩入一个字符进行获取
      • 依次类推,直接截取到二进制数字串结尾,获取到所有有效数据

    2.3.3,压缩解压代码

    package com.self.datastructure.tree.huffmancode;
    
    import lombok.Data;
    import org.apache.commons.collections.CollectionUtils;
    
    import java.util.*;
    
    /**
     * 霍夫曼编码
     *
     * @author PJ_ZHANG
     * @create 2020-04-07 15:16
     **/
    public class HuffmanCode {
    
        public static void main(String[] args) {
            String content = "i like like like java do you like a java";
            // 数据压缩
            // 先将传递字符串转换为byte数组, 并对每一种ASCII码出现频率进行统计
            // 根据频率大小构造赫夫曼树, 并将每一个叶子节点对应的编码值进行Map映射
            // 将原始字符串转换为赫夫曼编码字符串, 此时转换为一串二进制数字
            // 将这一串二进制数字转换为byte数组, 并准备进行传递
            // 最终传递需要赫夫曼树的Map映射和二进制数子串的byte数组
            // 路径映射,
            Map<Byte, String> pathMap = new HashMap<>(16);
            // 最终获取到的结果如下
            // [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
            byte[] encodeBytes = encode(content, pathMap);
            System.out.println("最终生成的十进制传输数据: " + Arrays.toString(encodeBytes));
            // 数据解压
            // 将传递的byte[]数组, 转换为赫夫曼编码的二进制数字串
            // 将二进制数组串, 对照赫夫曼编码字典, 重新转换为字符串
            byte[] decodeBytes = decode(encodeBytes, pathMap);
            System.out.println("解析内容完成: " + new String(decodeBytes));
        }
    
        /**
         * 反编译文本内容
         * 反编译文本内容与编译文本内容相反
         *
         * @param encodeBytes 传递的十进制数字串
         * @param pathMap 字符到频次映射
         * @return
         */
        private static byte[] decode(byte[] encodeBytes, Map<Byte, String> pathMap) {
            // 首先转换十进制传递数组为二进制数字串
            // 反编译的二进制串: 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
            String binaryStr = decodeBinaryStr(encodeBytes);
            // 转换二进制数字串为原始字符的字节数组
            byte[] bytes = decodeContent(binaryStr, pathMap);
            return bytes;
        }
    
        /**
         * 反编译二进制数字串成功后, 开始进行截取映射字典, 生成byte数组, 以便后续进行文本解析
         *
         * @param binaryStr 二进制数字串
         * @param pathMap 字符和路径映射
         * @return
         */
        private static byte[] decodeContent(String binaryStr, Map<Byte, String> pathMap) {
            // 反转字符和路径映射, 处理为路径映射字符
            Map<String, Byte> path2ByteMap = reverseMap(pathMap);
            // 根据路径一段段截取二进制数字串, 并拼凑为有效的byte码
            byte[] resultBytes = doDecodeContent(binaryStr, path2ByteMap);
            return resultBytes;
        }
    
        /**
         * 反编译为最终需要的字节码
         * @param binaryStr 二进制自己串
         * @param path2ByteMap 路径到字符的映射
         * @return
         */
        private static byte[] doDecodeContent(String binaryStr, Map<String, Byte> path2ByteMap) {
            // 截取的每一个数字, 添加到集合中
    
            List<Byte> lstBytes = new ArrayList<>(10);
            for (int i = 0; i < binaryStr.length();) {
                int count = 1;
                for (;;) {
                    // 以count作为一个标识位, 一直向后移动, 多括进一个字符
                    // 如果路径到字符映射中, 包含该路径, 则匹配成功, 并添加该字符到集合
                    String currStr = binaryStr.substring(i, i + count);
                    if (null != path2ByteMap.get(currStr)) {
                        // 添加字符到集合中
                        lstBytes.add(path2ByteMap.get(currStr));
                        break;
                    }
                    count++;
                }
                // 匹配成功后, i直接进count位, 进行下一组数据处理
                i += count;
            }
            // 转换集合为数组
            byte[] bytes = new byte[lstBytes.size()];
            int index = 0;
            for (Byte currByte : lstBytes) {
                bytes[index++] = currByte;
            }
            return bytes;
        }
    
        /**
         * 反转字符串, 反转为<value, key>形式
         *
         * @param pathMap
         * @return
         */
        private static Map<String,Byte> reverseMap(Map<Byte, String> pathMap) {
            Map<String, Byte> path2ByteMap = new HashMap<>(16);
            for (Map.Entry<Byte, String> entry : pathMap.entrySet()) {
                path2ByteMap.put(entry.getValue(), entry.getKey());
            }
            return path2ByteMap;
        }
    
        /**
         * 反编译为二进制数字串
         * @param encodeBytes 十进制字符
         * @return 二进制数字串
         */
        private static String decodeBinaryStr(byte[] encodeBytes) {
            StringBuilder sb = new StringBuilder();
            boolean isNeedSub = true;
            for (int i = 0; i < encodeBytes.length; i++) {
                if (i == encodeBytes.length - 1 && encodeBytes[i] > 0) {
                    isNeedSub = false;
                }
                sb.append(decodeDecimal(isNeedSub, encodeBytes[i]));
            }
            return sb.toString();
        }
    
        /**
         * 转换
         * @param isNeedSub 是否需要截取
         * @param encodeByte 当前需要转换的数据
         * @return
         */
        private static String decodeDecimal(boolean isNeedSub, int encodeByte) {
            String str = "";
            // 此处负数通过二进制转换会转换为标准的32位, 但是正数不会补0
            // 所以需要对数据转换后再截取, 转换方式为与256进行或运算
            // 256的二进制为: 1 0000 0000, 无论任务数字与256进行或运算后, 绝对能保证第九位的1, 则后八位有效
            // 转换完成后, 截取后八位作为有效数据
            // 注意: 最后一位需要处理的数据不一定满8位, 所以不满八位的情况下一定为正数, 需要原样处理
            // 满八位后, 可能为负数, 需要进行判断是否截取, 在调用方法中已经加标识位判断
            if (isNeedSub) {
                encodeByte |= 256;
                str = Integer.toBinaryString(encodeByte);
                str = str.substring(str.length() - 8);
            } else {
                str = Integer.toBinaryString(encodeByte);
            }
            return str;
        }
    
        /**
         * 编译文本内容
         *
         * @param content 文本内容
         * @param pathMap 字符Byte到赫夫曼码的映射
         * @return
         */
        private static byte[] encode(String content, Map<Byte, String> pathMap) {
            // 获取到字节码
            byte[] bytes = content.getBytes();
            // 统计频次, 以频次作为构建赫夫曼节点的权值
            Map<Byte, Integer> timeMap = new HashMap<>(16);
            statisticsTime(bytes, timeMap);
            // 转换频次映射Map为List
            List<Node> lstNode = transformMap2List(timeMap);
            // 转换为赫夫曼树
            Node huffmanTree = encodeHuffmanTree(lstNode);
            // 根据赫夫曼树, 生成字符的映射路径
            encodeByte2Path(huffmanTree, pathMap);
            // 根据传递内容, 拼接赫夫曼编码的二进制串, 按照上面传递的字符, 长度应该为133
            // 另外不同方式方式构建的赫夫曼树, 获得的串不一致
            // 比如形同time值的不同数据, 放在list的不同位置, 拼出来的树不一样, 但带权路径一样
            String binaryStr = encodeBinaryStr(bytes, pathMap);
            // 构建完成二进制串后, 对二进制串每8位生成一个十进制数据进行传递, 并转换为byte
            // 此处主要为了减少传递数据
            byte[] resultData = encodeResultData(binaryStr);
            return resultData;
        }
    
        /**
         * 对二进制数字串, 每8位构造一个十进制数据, 并传递出去,
         * 这一步构造的数据, 是真正需要传递出去的数据
         *
         * @param binaryStr
         * @return
         */
        private static byte[] encodeResultData(String binaryStr) {
            // 获取长度
            int length = (binaryStr.length() + 7) / 8;
            int count = 0;
            int index = 0;
            byte[] bytes = new byte[length];
            // 截取长度进行处理
            for (int i = 0; i < length; i++) {
                String currStr = "";
                if (i == length - 1) {
                    currStr = binaryStr.substring(count);
                } else {
                    currStr = binaryStr.substring(count, count + 8);
                    count += 8;
                }
                // 截取完成后, 转为byte型
                byte currData = (byte) Integer.parseInt(currStr, 2);
                bytes[index++] = currData;
            }
            return bytes;
        }
    
        /**
         * 拼接二进制数字串
         * @param bytes 传递字符串转换后的byte
         * @param pathMap byte到二进制路径的映射
         * @return
         */
        private static String encodeBinaryStr(byte[] bytes, Map<Byte, String> pathMap) {
            StringBuilder sb = new StringBuilder();
            for (byte b : bytes) {
                sb.append(pathMap.get(b));
            }
            return sb.toString();
        }
    
        /**
         * 根据赫夫曼树, 构建路径映射
         *
         * @param huffmanTree 赫夫曼树
         * @param pathMap 路径映射
         */
        private static void encodeByte2Path(Node huffmanTree, Map<Byte, String> pathMap) {
            StringBuilder sb = new StringBuilder();
            if (null != huffmanTree.getLeftNode()) {
                // 左侧拼接0
                appendPath(huffmanTree.getLeftNode(), "0", sb, pathMap);
            }
            if (null != huffmanTree.getRightNode()) {
                // 右侧拼接1
                appendPath(huffmanTree.getRightNode(), "1", sb, pathMap);
            }
        }
    
        /**
         * 拼接路径
         *
         * @param node 当前节点
         * @param pathCode 路径值
         * @param sb 拼接字符
         * @param pathMap 映射字符
         */
        private static void appendPath(Node node, String pathCode, StringBuilder sb, Map<Byte, String> pathMap) {
            StringBuilder newSB = new StringBuilder(sb);
            newSB.append(pathCode);
            if (null != node.getLeftNode()) {
                appendPath(node.getLeftNode(), "0", newSB, pathMap);
            }
            if (null != node.getRightNode()) {
                appendPath(node.getRightNode(), "1", newSB, pathMap);
            }
            // 遍历只处理叶子节点, 生成的虚拟父节点, data值为null
            if (null != node.getData()) {
                pathMap.put(node.getData(), newSB.toString());
            }
        }
    
        /**
         * 转换为赫夫曼树
         *
         * @param lstNode 构造的字符节点集合
         * @return 赫夫曼树根节点
         */
        private static Node encodeHuffmanTree(List<Node> lstNode) {
            for (;CollectionUtils.isNotEmpty(lstNode) && lstNode.size() > 1;) {
                // 每一次循环排序一次, 保证取到的前两个二叉树为最小数据
                Collections.sort(lstNode);
                // 构造父节点, 并设置左右子节点
                Node leftNode = lstNode.get(0);
                Node rightNode = lstNode.get(1);
                Node parentNode = new Node();
                parentNode.setTime((byte) (leftNode.getTime() + rightNode.getTime()));
                parentNode.setLeftNode(leftNode);
                parentNode.setRightNode(rightNode);
                // 从集合中移除前两个节点
                lstNode.remove(leftNode);
                lstNode.remove(rightNode);
                // 添加新节点
                lstNode.add(parentNode);
            }
            return lstNode.get(0);
        }
    
        /**
         * 转换映射频次为List, 方便后续赫夫曼树转换
         *
         * @param timeMap
         * @return
         */
        private static List<Node> transformMap2List(Map<Byte, Integer> timeMap) {
            List<Node> lstNode = new ArrayList<>(10);
            for (Map.Entry<Byte, Integer> entry : timeMap.entrySet()) {
                Node node = new Node(entry.getKey(), entry.getValue());
                lstNode.add(node);
            }
            return lstNode;
        }
    
        /**
         * 统计每一个字符出现的频次
         *
         * @param bytes
         * @param pathMap
         */
        private static void statisticsTime(byte[] bytes, Map<Byte, Integer> timeMap) {
            for (byte currByte : bytes) {
                Integer time = timeMap.get(currByte);
                time = null == time ? 1 : ++time;
                timeMap.put(currByte, time);
            }
        }
    
        @Data
        static class Node implements Comparable<HuffmanCode.Node> {
    
            private Byte data; // 字符
    
            private int time; // 字符频次
    
            private Node leftNode;
    
            private Node rightNode;
    
            public Node(Byte data, int time) {
                this.data = data;
                this.time = time;
            }
    
            @Override
            public String toString() {
                return "Node: [data = " + data + ", time = " + time + "] ";
            }
    
            /**
             * 进行数据比较, 满足数据升序排序
             * @param node
             * @return
             */
            @Override
            public int compareTo(Node node) {
                return this.getTime() - node.getTime();
            }
        }
    
    }
    

    2.4,赫夫曼编码 — 文件压缩解压

    2.4.1,文件压缩逻辑

    • 赫夫曼编码是基于字节数组进行编码,编码为二进制数字串后再转换为字节数组进行输出
    • 因为所有文件都可以通过输入流转换为字节数组,所以在理论上是都可以通过赫夫曼编码进行压缩的
    • 将原始文件读到内存中经过赫夫曼编码逻辑生成路径映射Map及赫夫曼编码的字节数组,并将这两个对象写入目标文件即为压缩后的文件
    • 代码在解压中附上

    2.4.2,文件解压逻辑

    • 接文件压缩,文件压缩将路径映射Map及赫夫曼编码的字节数组写入压缩文件,再文件解压时需要读取文件内这两部分内容
    • 读取到两个对象后,通过赫夫曼编码解压部分代码进行内容解析,解析生成一个原始文件对应的byte[]
    • 将这个byte[]对象直接通过输出流输出为一个新文件,即文件解压

    2.4.3,压缩解压代码

    package com.self.datastructure.tree.huffmancode;
    
    import java.io.*;
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * 文件压缩_赫夫曼编码
     *
     * @author PJ_ZHANG
     * @create 2020-04-08 11:24
     **/
    public class FileHuffmanCode {
    
        public static void main(String[] args) {
            // 文件压缩
            // 首先压缩方式与文本基本一致, 读取到文件的所有字节码后
            // 构造赫夫曼树, 生成路径映射
            // 构造二进制数字串之后转为byte[]数组
            // 写出byte[]数组和路径映射到文件中, 该文件即为压缩文件
            compress("F:\\123.bmp", "F:\\123.zip");
            System.out.println("压缩完成...");
    
            // 文件解压
            // 解压是先从第一布的压缩文件路径中读取到写出的byte[]数组和路径映射
            // 之后对byte[]数组进行二进制数字串转换再多最后的源文件字节数组转换
            // 最后写出字节数组到目标文件中, 视为对压缩文件的解压
            decompress("F:\\123.zip", "F:\\1234.bmp");
            System.out.println("解压完成...");
        }
    
        /**
         * 文件解压
         *
         * @param srcFilePath
         * @param desFilePath
         */
        private static void decompress(String srcFilePath, String desFilePath) {
            FileInputStream is = null;
            ObjectInputStream ois = null;
            FileOutputStream os = null;
    
            try {
                is = new FileInputStream(srcFilePath);
                ois = new ObjectInputStream(is);
                // 按顺序读取赫夫曼码映射和赫夫曼编码转换后的字节数组
                Map<Byte, String> pathMap = (Map<Byte, String>) ois.readObject();
                byte[] bytes = (byte[]) ois.readObject();
                // 解压为真是的字节数组
                byte[] needBytes = ContentHuffmanCode.decode(bytes, pathMap);
                // 写出去
                os = new FileOutputStream(desFilePath);
                os.write(needBytes);
                os.flush();
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                try {
                    is.close();
                    ois.close();
                    os.close();
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        }
    
        /**
         * 文件压缩
         *
         * @param srcFilePath 文件源路径
         * @param desFilePath 文件目标路径
         */
        private static void compress(String srcFilePath, String desFilePath) {
            // 初始化输入输出流
            FileInputStream is = null;
            FileOutputStream os = null;
            ObjectOutputStream oos = null;
    
            try {
                // 读取文件字节码
                is = new FileInputStream(srcFilePath);
                byte[] bytes = new byte[is.available()];
                is.read(bytes);
                // 构造赫夫曼编码路径映射及转换后的字节码
                Map<Byte, String> pathMap = new HashMap<>(16);
                byte[] huffmanBytes = ContentHuffmanCode.encode(bytes, pathMap);
                // 写数据到目标文件中, 作为压缩文件
                os = new FileOutputStream(desFilePath);
                oos = new ObjectOutputStream(os);
                oos.writeObject(pathMap);
                oos.writeObject(huffmanBytes);
                oos.flush();
            } catch (Exception e) {
                e.printStackTrace();
            } finally {
                try {
                    is.close();
                    os.close();
                    oos.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
    
        }
    
    }
    
    展开全文
  • 实现对一串字符的赫夫曼编码与译码,不能实现对文件的编码与译码。
  • 赫夫曼树的实现及编码一、简介1、简介2、相关定义二、赫夫曼树算法1、算法思路2、代码实现三、赫夫曼树编码1、基本介绍2、代码实现简介:相关定义: 一、简介 1、简介 1)给定n个权值(节点的值)作为n个叶子结点,...

    一、赫夫曼树简介

    1、简介

    1)给定n个权值(节点的值)作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为 赫夫曼树(哈夫曼树、霍夫曼树,最优二叉树)。
    2)赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近

    2、相关定义

    1、路径:从一个节点往下可以到达子节点的之间的通路;
    2、路径长度:通路中分支的数目。若规定跟节点所在的层数为1,则从根节点到第L层节点的路径长度为L-1;
    3、节点的权:给树中的节点赋予一个有着某种含义的值;
    4、节点的带权路径:从根结点到该结点之间的路径长度与该结点的权的乘积
    5、WPL(weighted path length)树的带权路径长度:规定为所有叶子节点的带权路径长度之和。 权值越大的结点离根结点越近的二叉树才是最优二叉树。

    WPL最小的树就是赫夫曼树:
    在这里插入图片描述

    二、赫夫曼树算法

    1、算法思路

    将数列 arr={12,3,5,8,34},转成一颗赫夫曼树,步骤如下:
    1、从小到大对数组进行排序,将每个数值存入 ArrayList 链表,每个数值都是一个节点,每个节点可以看成一个最简单的二叉树。
    2、从 ArrayList 取出根节点权值最小的两颗二叉树,组成一颗新的二叉树,该新的二叉树的根节点的权值就是前两颗二叉树根节点权值的和。
    3、然后从 ArrayList 中将前两颗二叉树根节点remove,再把新的二叉树的根节点的权值放入 ArrayList 中,然后再次排序。
    4、不断重复上述步骤,直到 ArrayList 中只剩下 赫夫曼树的根节点时退出循环,这样就可以得到一棵赫夫曼树了。

    2、代码实现

    import java.util.ArrayList;
    import java.util.Collections;
    
    /**
     * 哈夫曼树:最优二叉树
     */
    public class HuffManTree {
        public static void main(String[] args) {
            int[] arr = {12,3,5,8,34};
            //生成赫夫曼树
            Node huffManTree = createHuffManTree(arr);
            //前序遍历赫夫曼树
            preOrder(huffManTree);
        }
    
        //创建赫夫曼树的方法
        public static Node createHuffManTree(int[] arr) {
    //遍历arr数组,将arr的每个元素构建成一个NOde,将Node放入ArrayList;
            ArrayList<Node> nodes = new ArrayList<>();
            for (int value : arr) {
                nodes.add(new Node(value));
    
            }
    //循环,直到ArrayList只剩一个节点时结束
            while (nodes.size() > 1) {
                //从大到小排序
                Collections.sort(nodes);
                //取出权值最小的两个节点(二叉树)
                Node leftNode = nodes.get(0);
                Node rightNode = nodes.get(1);
    
               //构建一个新的二叉树,左节点的值加上右节点的值等于父节点
                Node parent = new Node(leftNode.value + rightNode.value);
                parent.left = leftNode;
                parent.right = rightNode;
    
                //从ArrayList 删除处理过的节点
    
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                //将父节点加入到ArrayList
                nodes.add(parent);
            }
    //最后返回赫夫曼树的头就可以了
            return nodes.get(0);
        }
        
        //编写一个前序遍历的方法
        public  static  void preOrder(Node  root){
            if(root!=null){
                root.preOrder();
            }else {
                System.out.println("空树,无法遍历");
            }
        }
    }
    /**
     * 创建节点类
     * 为了让NOde对象支持排序COllectins 集合排序
     * 让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) {
            //从小到大排序
            return this.value - o.value;
        }
    }
    

    三、赫夫曼树编码

    1、基本介绍

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

    2、实现原理:

    1)String str=“i like like like java do you like a java”
    2) d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
    3) 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

    步骤: 构成赫夫曼树的步骤:

    1. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树
      2)取出根节点权值最小的两颗二叉树
    2. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
    3. 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理, 就得到一颗赫夫曼树
    1. 根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为 0 向右的路径为 1 , 编码 如下:
      o: 1000
      a : 110
      l: 001
    2. 按照上面的赫夫曼编码,我们的"i like like like java do you like a java" 意这里我们使用的无损压缩) 10101001101111011110100110111101111010011011110111101000011000011100110011110000110 01111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为 133 6) 长度为 : 133
      说明:
      原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
      此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性 赫夫曼编码是无损处理方案

    2、代码实现

    2.1、赫夫曼编码及解码的详细代码(带注释)

    
    import java.io.FileInputStream;
    import java.io.FileOutputStream;
    import java.io.ObjectInputStream;
    import java.io.ObjectOutputStream;
    import java.util.*;
    
    /**
     * 赫夫曼编码
     */
    public class HuffManCode {
        public static void main(String[] args) {
            String s = "i like like like java do you like a java";
            byte[] bytes = s.getBytes();
            byte[] huffManCodesBytes = huffManZip(bytes);
    
            System.out.println("压缩后的结果是: " + Arrays.toString(huffManCodesBytes) + ",长度是:" + huffManCodesBytes.length);
            byte[] decode = decode(huffManCodes, huffManCodesBytes);
            System.out.println("解压缩之后的原字符串:" + new String(decode));
        }
    
        /**
         * 功能:封装测试的方法,方便调用
         *
         * @param bytes 原始字符串的数组
         * @return 返回的是经过赫夫曼编码处理后的字节数组,可以理解成压缩后的数组
         */
        private static byte[] huffManZip(byte[] bytes) {
            //将字节数组转换成list
            List<HuffManCodeNode> listCode = getCode(bytes);
            //生成赫夫曼树
            HuffManCodeNode huffManTree = createHuffManTree(listCode);
            //生成赫夫曼编码
            getCode(huffManTree);
            //测试赫夫曼编码转数组
            for (Map.Entry<Byte, String> entry : huffManCodes.entrySet()) {
                
            }
            byte[] zip = zip(bytes, huffManCodes);
            return zip;
    
        }
    
        /**
         * 功能:生成赫夫曼编码
         */
        private static List<HuffManCodeNode> getCode(byte[] bytes) {
            //创建ArrayList 集合存放字符编码和字符编码个数
            ArrayList<HuffManCodeNode> nodes = new ArrayList<HuffManCodeNode>();
            //创建map集合存放字符和对应字符出现的次数
            Map<Byte, Integer> counts = new HashMap<Byte, Integer>();
            //遍历字节数组,统计每个字符出现的次数,放入到Map集合中
            for (byte b : bytes) {
                Integer count = counts.get(b);
                if (count == null) {
                    counts.put(b, 1);
                } else {
                    counts.put(b, count + 1);
                }
            }
            //遍历Map,把每个键值对转换成一个HuffManCodeNode对象,并加入nodes集合
            for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
                nodes.add(new HuffManCodeNode(entry.getKey(), entry.getValue()));
            }
            return nodes;
        }
    
        /**
         * 功能:创建赫夫曼树
         */
        public static HuffManCodeNode createHuffManTree(List<HuffManCodeNode> nodes) {
            while (nodes.size() > 1) {
                //先进行排序
                Collections.sort(nodes);
                //获取两个最小二叉树组成新的二叉树的左右子节点,两个的权值作为父节点的权值
                HuffManCodeNode leftNode = nodes.get(0);
                HuffManCodeNode rightNode = nodes.get(1);
                //新的二叉树的父节点没有data值。
                HuffManCodeNode parentNode = new HuffManCodeNode(null, leftNode.weigth + rightNode.weigth);
                //父节点的左右子树
                parentNode.left = leftNode;
                parentNode.rigth = rightNode;
                //从ArrayList移除前两个二叉树,然后把新二叉树的节点放入ArrayList中
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                nodes.add(parentNode);
            }
            return nodes.get(0);
        }
    
    
        /**
         * 功能:前序遍历
         */
        public static void preOrder(HuffManCodeNode root) {
            if (root != null) {
                root.preOrder();
            } else {
                System.out.println("空树,无法遍历!");
            }
        }
    
        /**
         * 功能:生成赫夫曼树对应的赫夫曼编码,将赫夫曼编码表存放在map中
         * =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
         */
        static Map<Byte, String> huffManCodes = new HashMap<>();
        static StringBuilder stringBuilder = new StringBuilder();
    
        //为了方便调用,重载
        public static Map<Byte, String> getCode(HuffManCodeNode root) {
            if (root == null) {
                return null;
            }
            getCode(root.left, "0", stringBuilder);
            getCode(root.rigth, "1", stringBuilder);
            return huffManCodes;
        }
    
        /**
         * 功能:将传入的root的节点的所有叶子节点的赫夫曼编码得到,并放入到huffManCodes;
         *
         * @param root          传入的节点
         * @param code          路径:左子节点 0;右子节点 1;
         * @param stringBuilder 拼接得到的赫夫曼编码
         * @return
         */
        public static void getCode(HuffManCodeNode root, String code, StringBuilder stringBuilder) {
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            //将code 放入到stringBuilder2
            stringBuilder2.append(code);
            //root 为空 不处理
            if (root != null) {
                //判断该节点是叶子节点还是非叶子节点
                if (root.data == null) {//非叶子节点
                    //向左递归
                    getCode(root.left, "0", stringBuilder2);
                    //向右递归
                    getCode(root.rigth, "1", stringBuilder2);
                } else {//说明是个叶子节点
                    huffManCodes.put(root.data, stringBuilder2.toString());
                }
            }
        }
    
        /**
         * 功能:编写一个方法,将字符串对应的byte[] 数组,通过生成的 赫夫曼编码表,返回赫夫曼编码压缩后的byte[]
         * /将"10101000101111111100100010111111110010001011111111001001010011
         * 01110001110000011011101000111100101000 101111111100110001001010011011100"
         * 转成byte
         */
        private static byte[] zip(byte[] bytes, Map<Byte, String> huffManCode) {
            StringBuilder stringBuilder = new StringBuilder();
            //从map集合中获取赫夫曼编码进行拼接
            for (byte b : bytes) {
                stringBuilder.append(huffManCode.get(b));
            }
            System.out.println("测试 stringBuilder~~~=" + stringBuilder.toString());
            //一个byte 相当于8个字节,计算stringBuilder与8取余
            int len = 0;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
    
            //创建byte[]  存储压缩后的byte[]
            byte[] resBytes = new byte[len];
            int index = 0;
            //遍历赫夫曼编码
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String str;
                //如果剩余位数不够8位,直接截取剩余的所有位数,
                if (i + 8 > stringBuilder.length()) {
                    str = stringBuilder.substring(i);
                } else {//如果剩余位数大于8位,则截取8位
                    str = stringBuilder.substring(i, i + 8);
    
                }
                //将截取到的编码 转换成byte
                resBytes[index] = (byte) Integer.parseInt(str, 2);
                index++;
            }
            return resBytes;
        }
    
        /**
         * 功能:完成数据的解压
         * 思路
         * 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) {
            //先得到huffManBytes  对应的二进制的字符串,形式1010100010111·····
            StringBuilder stringBuilder = new StringBuilder();
    
            //将bytes数组转成二进制的字符串
            for (int i = 0; i < huffManBytes.length; i++) {
                byte b = huffManBytes[i];
                //判断是不是最后一个字节
                boolean flag = (i == huffManBytes.length - 1);
                stringBuilder.append(byteToBitString(!flag, b));
    
            }
            System.out.println(stringBuilder.toString());
    
            //把字符串安装指定的赫夫曼编码进行解码
            // 把赫夫曼编码表进行调换,因为反向查询 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<>();
    
            for (int i = 0; i < stringBuilder.length(); ) {
                int count = 1;
                boolean flag = true;
                Byte b = null;
    
    
                while (flag) {
                    //i 不动,count移动,指定匹配到一个字符
                    String key = stringBuilder.substring(i, i + count);
                    b = map.get(key);
                    //匹配不到,count++;
                    if (b == null) {
                        count++;
                    } else {//匹配到
    
                        flag = false;
                    }
                }
    
                list.add(b);
                //i 直接移动到 count
                i += count;
    
            }
    
            //当 for 循环结束后,我们 list 中就存放了所有的字符
            // 把 list 中的数据放入到 byte[] 并返回
            byte[] resbyte = new byte[list.size()];
            for (int i = 0; i < resbyte.length; i++) {
                resbyte[i] = list.get(i);
    
            }
            return resbyte;
    
        }
    
        /**
         * 功能:将一个byte 转成二进制字符串
         *
         * @param b    需要转换的byte
         * @param flag 标志是否需要补高位如果是 true ,表示需要补高位,如果是 false 表示不补, 如果是最后一 个字节,无需补高位
         * @return
         */
        private static String byteToBitString(boolean flag, byte b) {
            int tmp = b;
            //如果是正数,需要补齐高位
            if (flag) {
                //按位与 256   1 0000 000 | 0000 0001 => 1 0000 0001
                tmp |= 256;
            }
            String str = Integer.toBinaryString(tmp);
            if (flag) {
                return str.substring(str.length() - 8);
            } else {
                return str;
            }}
    
    
    //创建Node,带数据和权值
    class HuffManCodeNode implements Comparable<HuffManCodeNode> {
        Byte data;//存放数据本身
        int weigth;//权值,表示字符出现的次数
        HuffManCodeNode left;
        HuffManCodeNode rigth;
    
        public HuffManCodeNode(Byte data, int weigth) {
            this.data = data;
            this.weigth = weigth;
        }
    
        @Override
        public int compareTo(HuffManCodeNode o) {
            return this.weigth - o.weigth;
        }
    
        @Override
        public String toString() {
            return "{HuffManCodeNode data=" + data + ", weigth=" + weigth + '}';
        }
    
    
        public void preOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.rigth != null) {
                this.rigth.preOrder();
            }
        }
    }
    

    初学数据结构和算法,有不足的地方希望大家多多指出~~一起学习进步!!

    展开全文
  • 一、创建赫夫曼树 构成赫夫曼树的步骤: 1) 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树 2) 取出根节点权值最小的两颗二叉树 3) 组成一颗新的二叉树, 该新...

    目录

    一、创建赫夫曼树

    代码实现:最后返回值式创建好的赫夫曼树的顶点

    对int[] arr = {13, 7, 8, 3, 29, 6, 1};进行赫夫曼树,我们创建好的node数组依次是这样变化

    创建节点:节点有前序遍历方法,之后遍历树时只需利用树的根节点来调用遍历方法

    遍历方法:

    二、赫夫曼编码的应用(压缩->还原)

    代码实现

    把字符串转为字节数组

    把字节数组转为带有字节和此字节出现次数的list集合并返回

    创建赫夫曼树并返回根节点(遍历用)

    生产赫夫曼编码(使用Map来存储对应关系)

    将原来的字符串按照赫夫曼编码组合起来(用StringBuilder)并以八位一分割转为10进制数字构成的数组

    还原:根据赫夫曼编码和数字数组还原为二进制编码,再将Map翻转,依据Map把二进制编码转为Ascii码,再根据Ascii码还原为英文的字符串

    在将字节转为二进制字符串时有一点要注意,传输过来是补码,需要分情况还原为源码

    三、赫夫曼编码的使用例子

    压缩

    解压


     

    一、创建赫夫曼树

    构成赫夫曼树的步骤:

    1) 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树

    2) 取出根节点权值最小的两颗二叉树

    3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和 

    4) 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复  1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树

    代码实现:最后返回值式创建好的赫夫曼树的顶点

    public static Node createHuffmanTree(int[] arr) {
            //数组不支持排序,我们把数组元素装到Node中,然后把这些Node装到list中
            ArrayList<Node> list = new ArrayList<>();
            for (int i = 0; i < arr.length ; i++) {
                list.add(new Node(arr[i]));//节点的创建只有一个左指针和右指针以及自己的值
            }
    
            //循环操作的过程
            while (list.size() > 1) {
                //排序:从小到大
                Collections.sort(list);
                //取出根节点权值最小的两个二叉树,此时一个节点就是一个二叉树
                //①取出第一个值
                Node leftNode = list.get(0);
                //②取出第二个值
                Node rightNode = list.get(1);
                //③构建成树
                Node parent = new Node(leftNode.value + rightNode.value);
                parent.left = leftNode;
                parent.right = rightNode;
                //从list中删除leftNode,rightNode
                list.remove(leftNode);
                list.remove(rightNode);
                //把parent在加入到list中
                list.add(parent);
    
                System.out.println(list);
            }
    //得到了赫夫曼树的根节点
            return list.get(0);
       }
    }

    对int[] arr = {13, 7, 8, 3, 29, 6, 1};进行赫夫曼树,我们创建好的node数组依次是这样变化

    [Node{value=6}, Node{value=7}, Node{value=8}, Node{value=13}, Node{value=29}, Node{value=4}]
    [Node{value=7}, Node{value=8}, Node{value=13}, Node{value=29}, Node{value=10}]
    [Node{value=10}, Node{value=13}, Node{value=29}, Node{value=15}]
    [Node{value=15}, Node{value=29}, Node{value=23}]
    [Node{value=29}, Node{value=38}]
    [Node{value=67}]

    创建节点:节点有前序遍历方法,之后遍历树时只需利用树的根节点来调用遍历方法

    //创建节点类
    //为了让节点实现排序,所以让它实现comparable接口
    class Node implements Comparable<Node> {
    
    
        int value;
        Node left;
        Node right;
    
        //前序遍历的方法
        public void perOrder() {
            System.out.println(this);
            if (this.left != null) {
                this.left.perOrder();
            }
            if (this.right != null) {
                this.right.perOrder();
            }
        }
    
    
        public Node(int value) {
            this.value = value;
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        @Override
        public int compareTo(Node n) {
            return this.value - n.value;
        }
    }

    遍历方法:

     public static void perOrder(Node root) {
        if (root != null) {
                root.perOrder();
            } else {
                System.out.println("空的树,没法遍历");
         }
     }

    遍历结果:

    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}

    二、赫夫曼编码的应用(压缩->还原)

    1) 传输一个字符串:i like like like java do you like a java  (包括空格在内有40个字符)

    2)通信领域中信息的处理方式1-定长编码

    对应的Ascii码为:105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97

    3)此时转为二进制为:01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001 (共有359位)

    4)  通信领域中信息的处理方式2-变长编码

            d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9  // 各个字符对应的个数

            按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

    5)在赫夫曼树的基础上左边用0表示,右边用1表示        

    6) 此时每一个字母有了自己对应的二进制编码,而且编码有一个特点:从第一位开始不会有重复的,每一个都是独立的,不会出现长的编码包含短的编码的情况

    o: 1000   u: 10010  d: 100110  y: 100111  i: 101

    a : 110     k: 1110    e: 1111       j: 0000       v: 0001

    l: 001          : 01

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

    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110  通过赫夫曼编码处理  长度为  133

    8)此时赫夫曼编码的作用体现出来了,因为计算机底层传输都是用的二进制编码,我们把原先的355位压缩到了133位

    9)此时传输并不奏效,反而加大了工作量,原先的40个字符,现在有133个,但是二进制数可以八位为一体成为字节,所以变为[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]为17位

    10)把这17为数字和赫夫曼编码集一同发送,按照赫夫曼编码集还原,从而实现数据的压缩--->还原

    代码实现

    把字符串转为字节数组

    String str = "i like like like java do you like a java";
      byte[] bytes = str.getBytes();

    此时字符串变为:

    [105, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97, 32, 100, 111, 32, 121, 111, 117, 32, 108, 105, 107, 101, 32, 97, 32, 106, 97, 118, 97]

    把字节数组转为带有字节和此字节出现次数的list集合并返回

    public static List<Node> toList(byte[] bytes) {
    
            ArrayList<Node> list = new ArrayList<>();
    //        遍历bytes,统计每一个byte出现的次数,用map的key和value表示
            HashMap<Byte, Integer> map = new HashMap<>();
    
            for (Byte b : bytes) {
                Integer count = map.get(b);
                if (count == null) {
                    map.put(b, 1);
                } else {
                    map.put(b, count + 1);
                }
            }
    
    //        把每一个键值对转成Node对象,并加入到nodes集合中
            for (Map.Entry<Byte, Integer> e : map.entrySet()) {
                list.add(new Node(e.getKey(), e.getValue()));
            }
    
            return list;
        }

     此时list为:

    [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}]

    创建赫夫曼树并返回根节点(遍历用)

     public static Node creadHuffmanTree(List<Node> list) {
    
            while (list.size() > 1) {
                Collections.sort(list);
    
                Node leftNode = list.get(0);
                Node rightNode = list.get(1);
    
                Node parent = new Node(null, leftNode.weight + rightNode.weight);
    
                parent.left = leftNode;
                parent.right = rightNode;
    
                list.remove(leftNode);
                list.remove(rightNode);
    
                list.add(parent);
            }
    
            return list.get(0);
        }

    根节点为:Node{data=null, weight=40}

    生产赫夫曼编码(使用Map来存储对应关系)

    //重载以下方法
        public static Map<Byte, String> creatHuffmanCodes(Node root) {
            if (root != null) {
                creatHuffmaCodes(root.left, "0", stringBuilder);
                creatHuffmaCodes(root.right, "1", stringBuilder);
                return huffmanCodes;
            } else {
                return null;
            }
    
        }
    
        //    生成赫夫曼树对应的赫夫曼编码
    //    思路:先考虑生成的码存放在哪里:我们用Map<Byte,String>来存放
        static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
        //          在生成赫夫曼编码的过程中,需要不断的对路径进行拼接:我们定义StringBuilder来存放叶子节点的路径
        static StringBuilder stringBuilder = new StringBuilder();
    
        public static void creatHuffmaCodes(Node node, String code, StringBuilder stringBuilder) {
            StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
            stringBuilder2.append(code);
            if (node != null) {//有节点才处理
                if (node.data == null) {//非叶子节点
                    //向左递归
                    creatHuffmaCodes(node.left, "0", stringBuilder2);
                    //向右递归
                    creatHuffmaCodes(node.right, "1", stringBuilder2);
                } else {//叶子节点
                    huffmanCodes.put(node.data, stringBuilder2.toString());
                }
            }
        }

    此时赫夫曼编码为:

    {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011} 

    将原来的字符串按照赫夫曼编码组合起来(用StringBuilder)并以八位一分割转为10进制数字构成的数组

    public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
            StringBuilder stringBuilder = new StringBuilder();
    
            for (byte b : bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
            System.out.println("stringBuilder:" + stringBuilder);
    
            int len;//处理后byte[]的长度
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
    
            byte[] by = new byte[len];
            int index = 0;
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                String substring;
                if (i + 8 > stringBuilder.length()) {
                    substring = stringBuilder.substring(i);
                } else {
                    substring = stringBuilder.substring(i, i + 8);
                }
    
                //子字符串转成byte,放到by中
                by[index] = (byte) Integer.parseInt(substring, 2);
                index++;
            }
            return by;
        }
    

    此时StringBuilder(二进制编码)为:

    1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

    转为数字数组为:

    [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]

    还原:根据赫夫曼编码和数字数组还原为二进制编码,再将Map翻转,依据Map把二进制编码转为Ascii码,再根据Ascii码还原为英文的字符串

    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
            //先把数字变成二进制数组
            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < huffmanBytes.length; i++) {
                //判断是不是最后一个字节
                boolean flag = (i == huffmanBytes.length - 1);
                stringBuilder.append(bytesToBiteString(!flag, huffmanBytes[i]));
            }
            System.out.println("还原回来的:" + stringBuilder.toString());
    
            //把二进制字符串按照赫夫曼编码表进行解码
            //把赫夫曼编码表进行调换,反向查询
            HashMap<String, Byte> map = new HashMap<String, Byte>();
            for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
                map.put(entry.getValue(), entry.getKey());
            }
            System.out.println("还原回来的:" + map);
    
            //创建一个集合,存放byte
            ArrayList<Byte> list = new ArrayList<>();
            //遍历StringBuilder,与map的key匹配
            for (int i = 0; i < stringBuilder.length(); ) {
                int count = 1;//count是用来遍历的,i直接跳到count的位置即可
                boolean flag = true;
                Byte b = null;
                while (flag) {
                    String substring = stringBuilder.substring(i, i + count);
                    b = map.get(substring);
                    if (b == null) {//说明没有匹配到
                        count++;
                    } else {
                        flag = false;
                    }
                }
                list.add(b);
                i += count;
            }
            System.out.println("临时的ArraryList:" + list);
            //for循环结束以后,list中存放了:所有的字符:"i like like like java do you like a java";
            //把list中的数据放到byte[]中并返回
            byte[] bytes = new byte[list.size()];
            for (int i = 0; i < bytes.length; i++) {
                bytes[i] = list.get(i);
            }
            return bytes;
        }
    

    在将字节转为二进制字符串时有一点要注意,传输过来是补码,需要分情况还原为源码

     /**
         * 把一个字节转为二进制字符串
         *
         * @param flag 表示是否需要补高位,如果是true则需要补高位,反之不需要
         * @param b    传入的一个byte
         * @return b对应的二进制的字符串(补码形式)
         */
        public static String bytesToBiteString(boolean flag, byte b) {
            int temp = b;//将b转为int类型,因为Integer有toBinaryString()
            //如果是正数,要补高位
            if (flag) {
                temp |= 256;//按位与 1 0000 0000 | 0000 0001 =>1 0000 0001
            }
            String s = Integer.toBinaryString(temp);//返回的是temp对应的二进制的补码
            if (flag) {
                return s.substring(s.length() - 8);
            } else {
                return s;
            }
        }

    三、赫夫曼编码的使用例子

    我们上述的代码实现了压缩与还原,将其封装后便成了赫夫曼编码压缩文件和还原文件的两个方法

    又因为赫夫曼编码是字节码,所以既可以实现文件的压缩,又可以实现图片、视频的压缩。有兴趣可以试试

    文件的压缩传输解压需要用到io流

    压缩

    /**
         * @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 = getHuffmanCodesBytes(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());
                }
            }
    
        }

    解压

       /**
         * @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());
                }
    
            }
        }

    展开全文
  • 赫夫曼树matlab代码霍夫曼编码Python和MATLAB实现 该存储库由Huffman编码的MATLAB和Python实现组成。 Huffman源代码由David Albert Huffman引入,并于1952年9月在IRE会议录中以“”的名义出版。 描述 霍夫曼编码是...
  • 1、 简介:在给定n个权值作为n个叶子节点,构造一颗二叉树,如果该二叉树的带权路径长度(wpl)达到最小,称为这样的树称为最优二叉树,也称赫夫曼树赫夫曼树是带权路径最短的树,权值越大的结点离根结点最近。 2...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,596
精华内容 2,238
关键字:

赫夫曼树