精华内容
下载资源
问答
  • 8.4,赫夫曼树 赫夫曼树是一种带权路径最短的二叉树。带权路径:根节点到所有叶子结点所需路径*结点权值之和。通常路径即为结点所在层数之差,所以权值越大结点离根结点越近。 赫夫曼树构建思路: 1,将数据按照...

    8.4,赫夫曼树

    赫夫曼树是一种带权路径最短的二叉树。带权路径:根节点到所有叶子结点所需路径*结点权值之和。通常路径即为结点所在层数之差,所以权值越大结点离根结点越近。

    赫夫曼树构建思路:

    1,将数据按照权值从小到大顺序排列,每个数据结点都看作一个二叉树;

    2,分别取出权值最小的两个二叉树组成新树,其权值为前两者之和;

    3,再将新树加入排列中,重复1-2步骤,直到所有结点都被处理。

    注意:所有的数据都存在了叶子结点上。

    现使用java实现赫夫曼树的创建。

    image-20201106153132577
    package com.lsk.tree;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    /*
     * 赫夫曼数的构建思路:
     * 定义:带有权值路劲之和最小的二叉树即为赫夫曼树
     * 思路:1,将节点排序,选出权值最小的两个的节点;
     * 		2,将权值之和作为新的父节点,组成了一棵新的二叉树
     * 		3,再将新的二叉树加入权值排序,继续组件新的二叉树;
     * 		4,重复1、2、3;直到所有节点都被处理组建成一个根结点时*/
    
    public class HuffmanTree {
    	public static void main(String[] args) {
    		int[] arr = { 13, 7, 8, 3, 29, 6, 1};
    		Node root = createhuffmanTree(arr);
    		preOrder(root);
    	}
    	//前序遍历赫夫曼树
    	public static void preOrder(Node root)
    	{
    		if(root!=null) {
    			root.preOrder();
    		}else {
    			System.out.println("该树为空!");
    		}
    	}
    
    	//创建赫夫曼树
    	public static Node createhuffmanTree(int[] arr) {
    		// arr的每一个元素即为一个node节点
    		// 将node放入list中以便使用sort方法
    		List<Node> node = new ArrayList<>();
    		for (int weight : arr) {
    			node.add(new Node(weight));
    		}
    		while(node.size()>1)
    		{
    			Collections.sort(node);
    			Node leftNode = node.get(0);	//较小的位于左子树
    			Node rightNode = node.get(1);
    			Node parent = new Node(leftNode.weight + rightNode.weight);	//组建新树
    			parent.left = leftNode;		//分别链接到左右子树
    			parent.right = rightNode;
    			node.add(parent);	//加入节点中重新排序
    			node.remove(leftNode);
    			node.remove(rightNode);
    		}
    		//返回赫夫曼树
    		return node.get(0);
    	}
    }
    
    // 节点类 为了让node结点能实现排序功能,这里继承Comparable
    class Node implements Comparable<Node> {
    	Node left; // 左子树
    	Node right;// 右子树
    	byte data; // 存放数据
    	int weight;// 权值
    
    	public Node(int weight) {
    		super();
    		this.weight = weight;
    	}
    
    	public Node(byte data, int weight) {
    		this.data = data;
    		this.weight = weight;
    	}
    
    //	前序遍历结点
    	public void preOrder() {
    		System.out.println(this);
    		if(this.left!=null) {
    			this.left.preOrder();
    		}
    		if(this.right!=null)
    		{
    			this.right.preOrder();
    		}
    	}
    
    
    	@Override
    	public String toString() {
    		return "Node [data=" + data + ", weight=" + weight + "]";
    	}
    	@Override
    	public int compareTo(Node o) {
    		// 实现从小到大排序
    		return this.weight - o.weight;
    	}
    }
    
    

    8.5,赫夫曼编码

    赫夫曼树的重要应用就是通信领域中的赫夫曼编码了。

    定长编码:比如在传输中,我们需要对字符串"i like like like java do you like a java"进行编码,首先会根据ASCII编码表,将i转换为105,再转换为对应的二进制0110 1001;然后依次进行类似的操作。

    变长编码:对字符串中出现的字符进行次数统计,频次最高的使用最短的0进行编码,然后是1,10,11,...;比如0=' ',1 = a,10='i',11='e'......然后上面的字符串编码就是10010110...,但这样简单的处理会出现多义性问题。

    因此,我们需要做到前缀编码,即一个编码对应唯一的字符。

    赫夫曼编码:

    基于赫夫曼树,以左0右1遍历结点的结果组合,作为结点的字符编码。由于结点的位置不同,每一个字符的编码都将是唯一的。

    下面用赫夫曼编码实现对数据的压缩和解压。

    压缩思路:

    1,统计待压缩字符串各字符出现的次数,把次数作为他们的权值,封装成node结点;

    2,由node结点构造赫夫曼树。

    3,然后以Map<Byte,String>的形式存储赫夫曼编码表,即每一个字符对应一个二进制的字符串;

    4,然后把字符串拼接起来每8位一截取(用于发送),即是压缩后的字符形式了;

    解压思路:

    1,将压缩后的编码形式转换成二进制,

    2,再逐一遍历二进制字符串和赫夫曼编码表匹配,并将匹配的的放入字节数组中。

    image-20201107143242063

     	public static void main(String[] args) {
            //准备测试字符串数据
            String content = "i like like like java do you like a java";
            //将字符串转为字节数组形式
            byte[] bytes = content.getBytes();
            
            //1,将统计的数据和权值转换成对node
            List<Node> nodes = getNodes(bytes);
            
            //2,根据结点创建赫夫曼树,返回一个根结点
            Node huffmanTreeRoot = createHuffmanTree(nodes);
    
            //3,根据赫夫曼树创建赫夫曼编码表
           	huffmanCodes = getCodes(huffmanTreeRoot);
    
            //4,压缩方法,返回压缩后的字节数组,长度17。可见本例中压缩率为23/40=57.5%
            byte[] bytesCodes = huffmanZip(bytes);
     
            //5,解压方法,返回原始字符串
            byte[] originalBytes = decode(huffmanCodes, bytesCodes);
            System.out.println(new String(originalBytes));
        }
    
    /**
    	 * 遍历字节数组,将字符出现次数作为对应权值存入hashMap并转换为Node结点对象
    	 *
    	 * @param bytes 传入的字节数组
    	 * @return 返回一个已经转换好的Node结点数组
    	 */
    	public static List<Node> getNodes(byte[] bytes) {
    		List<Node> nodes = new ArrayList<Node>();
    		Map<Byte, Integer> elementMap = new HashMap<>();
    		// 遍历字节数组拿到数据,统计每个字符出现的次数作为权值
    		for (byte b : bytes) {
    			// 实质上将遍历得到的每个字节当做key
    			Integer count = elementMap.get(b);
    			// 没有即存放,此时value为1
    			if (count == null) {
    				elementMap.put(b, 1);
    			} else {
    				elementMap.put(b, count + 1);
    			}
    		}
    
    		// 再将map转为node对象:key——>data;value——>weight
    		// map的遍历
    		for (Map.Entry<Byte, Integer> entry : elementMap.entrySet()) {
    			nodes.add(new Node(entry.getKey(), entry.getValue()));
    		}
    		return nodes;
    	}
    
    /**
    	 * 创建赫夫曼树
    	 *
    	 * @param nodes 传入的node数组
    	 * @return 返回一个赫夫曼树根结点
    	 */
    	public static Node createHuffmanTree(List<Node> nodes) {
    
    		while (nodes.size() > 1) {
    			Collections.sort(nodes);
    			Node leftNode = nodes.get(0); // 较小的位于左子树
    			Node rightNode = nodes.get(1);
    			Node parent = new Node(null, leftNode.weight + rightNode.weight); // 组建新树
    			parent.left = leftNode; // 分别链接到左右子树
    			parent.right = rightNode;
    			nodes.add(parent); // 加入节点中重新排序
    			nodes.remove(leftNode);
    			nodes.remove(rightNode);
    		}
    		// 返回赫夫曼树根结点
    		return nodes.get(0);
    	}
    
     /**
         * 由赫夫曼树生成对应的赫夫曼编码表
         * 思路:1->赫夫曼编码表存放在Map<byte,String>中
         * 2->形如:{32(' ')=01, 97('a')=100, 100=11000, 117=11001......
         * 3->左子结点是0,右子结点是1,string一个个拼接而成(使用stringBuilder)
         */
    
        //1,定义一个静态map结构的huffmanCodes
        static Map<Byte, String> huffmanCodes = new HashMap<>();
        //2,定义一个stringBuilder,用于存放叶子结点的路径
        static StringBuilder stringBuilder = new StringBuilder();
    
        /**
         * 根据赫夫曼树构建赫夫曼编码表的具体算法:
         * 这是一个递归过程,将传入赫夫曼根节点的赫夫曼树生成对应的赫夫曼编码表
         *
         * @param node          待传入的赫夫曼树根节点
         * @param code          拼接规则:左子结点是0,右子结点是1
         * @param stringBuilder 拼接后的路径
         */
        public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
            StringBuilder strBuilder = new StringBuilder(stringBuilder);
            //将code拼接到strBuilder
            strBuilder.append(code);
            if (node != null) {
                //非叶子结点
                if (node.data == null) {
                    //向左递归
                    getCodes(node.left, "0", strBuilder);
                    //向右递归
                    getCodes(node.right, "1", strBuilder);
                } else {
                    //遍历到了叶子结点,则存放入huffmanCodes中
                    huffmanCodes.put(node.data, strBuilder.toString());
                }
            }
        }
    
        /**
         * 为了调用方便,对getCodes进行重载,直接返回huffmanCodes
         *
         * @param node 传入的赫夫曼树根结点
         * @return 返回一个map结构的赫夫曼编码表
         */
        public static Map<Byte, String> getCodes(Node node) {
            if (node == null) {
                return null;
            } else {
                //处理root的左子树
                getCodes(node.left, "0", stringBuilder);
                //处理root的右子树
                getCodes(node.right, "1", stringBuilder);
                return huffmanCodes;
            }
        }
    
    /**
         * 按照赫夫曼编码表规则将原始数据压缩成字节数组
         *
         * @param bytes
         * @param huffmanCodes
         * @return
         */
        public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
            //将bytes数组按照赫夫曼编码规则拼接成一个二进制串
            StringBuilder stringBuilder = new StringBuilder();
            for (byte b : bytes) {
                stringBuilder.append(huffmanCodes.get(b));
            }
            System.out.println(stringBuilder.toString());
    
            //定义赫夫曼压缩的字节数组的长度
            int len;
            if (stringBuilder.length() % 8 == 0) {
                len = stringBuilder.length() / 8;
            } else {
                len = stringBuilder.length() / 8 + 1;
            }
            //定义赫夫曼压缩的字节数组
            byte[] huffmanCodeBytes = new byte[len];
            int index = 0;
            //对字符串8个一截取,并放入对应压缩后的字节数组中
            for (int i = 0; i < stringBuilder.length(); i += 8) {
                //用于装载每次截取的字符串
                String str;
                if (i + 8 > stringBuilder.length()) {//某一个不够8位时
                    str = stringBuilder.substring(i); //此时截取起始位置到末尾
                } else {
                    str = stringBuilder.substring(i, i + 8);
                }
                //将String字符数组转换为byte
    			/* 细节:以第一个8位字符串"10101000"为例(i l ' '->101 01 000)
    			将它强转为byte,溢出后转换成了负数求补码,所以输出是-88*/
                huffmanCodeBytes[index] = (byte) Integer.parseInt(str, 2);
                index++;
            }
            return huffmanCodeBytes;
        }
    
    /**
         * 封装:将原始字节数组转换为赫夫曼编码的字节数组
         *
         * @param bytes 压缩前数组
         * @return 返回压缩后数组
         */
        public static byte[] huffmanZip(byte[] bytes) {
            List<Node> nodes = getNodes(bytes);
            Node huffmanTreeRoot = createHuffmanTree(nodes);
            getCodes(huffmanTreeRoot);
            //测试赫夫曼编码
    		for(Byte key : huffmanCodes.keySet()){
    			System.out.println("key:"+key+"--->"+huffmanCodes.get(key));
    		}
            byte[] bytesCodes = zip(bytes, huffmanCodes);
            return bytesCodes;
        }
    
    /**
         * 将一个字节转换成二进制字符串形式。
         * 截取:因为返回的int32位的补码形式,所以需要截取8位
         * 补位:正数不足8位时截取会造成越界异常,需要补高位,比如1,补成1 0000 0001
         * 判断:都是按8位处理的,但最后一位不需要截取和补位(可能就位数不足),比如28,1110,补成0000 1110,会造成多义性
         * @param flag 判断是否需要补高位(对正数,对最后一个不需要)
         * @param b 传入字节
         * @return
         */
    	public static String byteToBitString(boolean flag,byte b){
    		int temp = b;
    		if(flag){
    		    //不足8位时,和1 0000 0000 与运算,可以补齐前面的0
                temp |= 256;
            }
    		String str = Integer.toBinaryString(temp);
    		if(flag){
    		    //只需要截取后面的8位即可
    		    return str.substring(str.length()-8);
            }else{
                return str;
            }
    	}
    
     /**
         * @param huffManCodes 赫夫曼编码表
         * @param huffManBytes 赫夫曼编码的字节数组
         * @return
         */
    	public static byte[] decode(Map<Byte,String> huffManCodes,byte[] huffManBytes){
    	    //1,首先将编码的字节数组转换为二进制串
            //2,遍历map,根据<string,byte>匹配转换成每个字节
            //3,以字节数组的形式返回
            StringBuilder stringBuilder = new StringBuilder();
            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());
            //实现map翻转
            Map<String,Byte> reverseCodeMap = new HashMap<>();
            for(Map.Entry<Byte,String> entry : huffManCodes.entrySet()){
                reverseCodeMap.put(entry.getValue(),entry.getKey());
            }
            //存放匹配的字节数组
            List<Byte> byteList = new ArrayList<>();
            for(int i = 0;i<stringBuilder.length();){
                int count = 1; //第二指针,i不动,count移位
                boolean flag = true; //是否匹配的标志
                Byte b = null; //记录匹配对应的字节
                while(flag){
                    String s = stringBuilder.substring(i, i + count);
                    b = reverseCodeMap.get(s);
                    if(b==null){
                        count++; //没有匹配的继续移动指针
                    }else {
                        flag = false;
                    }
                }
                byteList.add(b);
                i += count; //每次匹配在上次结束的地方开始
            }
            //list数组转换为byte数组
            byte[] originalBytes = new byte[byteList.size()];
            for(int i = 0;i<byteList.size();i++){
                originalBytes[i] = byteList.get(i);
            }
    	    return originalBytes;
        }
    
    
    
    展开全文
  • 赫夫曼树+赫夫曼编码——《大话数据结构》读书笔记

    赫夫曼树

    赫夫曼树定义与原理

    从树中一个节点到另一个节点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径长度

    图6-12-4的二叉树a中,根结点到结点D的路径长度就为4,二叉树b中根结点到结点D的路径长度为2。树的路径长度就是从树根到每一结点的路径长度之和。二叉树a的树路径长度就为1+1+2+2+3+3+4+4=20。二叉树b的树路径长度就为1+2+3+3+2+1+2+2=16。

    如果考虑到带权的结点,结点的带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和,则其中带权路径长度WPL最小的二叉树称做赫夫曼树

    有了赫夫曼对带权路径长度的定义,我们可以计算一下上图这两棵树的WPL值。

    二叉树a的WPL=5X1+15X2+40X3+30X4+10X4=315

    注意:这里5是A结点的权,1是A结点的路径长度,其他同理。

    二叉树b的WPL=5X3+15X3+40X2+30X2+10X2=220

    这样的结果意味着什么呢?如果我们现在有10000个学生的百分制成绩需要计算五级分制成绩, 用二叉树a的判断方法,需要做31500次比较,而二叉树b的判断方法,只需要22000次比较,差不多少了三分之一量,在性能上提高不是一点点。

    那么现在的问题就是:图6-12-4的二叉树b这样的树是如何构造出来的,这样的二叉树是不是就是最优的赫夫曼树呢?别急,且看下面的分析。

    1. 先把有权值的叶子结点按照从小到大的顺序排列成一个有序序列,即:A5,E10,B15,D30,C40。

    2. 取头两个最小权值的结点作为一个新节点N1的两个子结点,注意相对较小的是左孩子,这里就是A为N1的左孩子,E为N1的右孩子,如图6-12-5所示。新结点的权值为两个叶子权值的和5+10=15。

    3. 将N1替换A与E,插入有序序列中,保持从小到大排列。即:N1 15, B15, D30, C40。

    4. 重复步骤2,。将N1与B作为一个新结点N2的两个子结点。如图6-12-6所示。N2的权值=15+15=30。

    5. 将N2替换N1与B插入有序序列中,保持从小到大序列。即:N2 30, D30, C40。

    6. 重复步骤2。将N2与D作为一个新结点N3的两个子结点。如图6-12-7所示。N3的权值=30+30=60。

    7. 将N3替换N2与D,插入有序序列中,保持从小到大排列。即C40,N3 60。

    8. 重复步骤2。将C与N3作为一个新结点T的两个子结点,如图6-12-8所示。由于T即是根结点,完成赫夫曼树的构造。

    此时的图6-12-8二叉树的带权路径长度WPL=40X1+30X2+15X3+10X4+5X4=205。与图6-12-4的二叉树b为WPL值220相比,还少了15。显然此时构造出来的二叉树才是最优的赫夫曼树。

    通过刚才的步骤,我们可以得出构造赫夫曼树的赫夫曼算法描述。

    1. 根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树T1中只有一个带权为w1根结点,其左右子树均为空。
    2. 在F中选区两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为左右子树上根结点的权值之和。
    3. 在F中删除这两棵树,同时将新得到的二叉树加入到F中。
    4. 重复2和3步骤,直到F只含一棵树为止。这棵树便是赫夫曼树。

    赫夫曼编码

    赫夫曼研究这种最优树的目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。

    比如我们有一段文字内容为"BADCADFEED"要网络传输给别人,显然用二进制的数字(0和1)来表示是很自然的想法。我们现在这段文字只有六个字母ABCDEF,那么我们可以用相应的二进制数据表示,如表6-12-2所示。

    这样真正传输的数据就是编码后的"001000011010000011101100100011",对方接收时可以3位一分来译码。如果一篇文章很长,这样的二进制串也将非常的可怕。而且事实上,不管是英文、中文或是其他语言,字母或汉字的出现频率是不相同的,比如英语中的几个元音字母"a e i o u",中文中的"的 了 有 在"等汉字都是频率极高。

    假设六个字母的频率为A 27,B 8,C 15,D 15,E 30,F 5,合起来正好是100%。那就意味着,我们完全可以重新按照赫夫曼树来规划他们。

    图6-12-9左图为构造赫夫曼树的过程的权值显示。右图为将权值左分支改为0,右分支改为1后的赫夫曼树。

    此时,我们对这六个字母用其从树根到叶子所经过路径的0或1来编码,可以得到如表6-12-3所示这样的定义。

    我们将文字内容为"BADCADFEED"再次编码,对比可以看到结果串变小了。

    • 原编码二进制串:0010000110100000111011001000011(共30个字符)
    • 新编码二进制串:1001010010101001000111100(共25个字符)

    也就是说,我们的数据被压缩了,节约了大约17%的存储或传输成本。随着字符的增加和多字符权重的不同,这种压缩会更加显出其优势。

    当我们接收到1001010010101001000111100这样压缩过的新编码时,我们应该如何把它解码出来呢?

    编码中非0即1,长度不等的话其实是很容易混淆的,所以若要设计长短不等的编码,则必须是任一字符的编码都不是另一个字符的编码的前缀,这种编码称做前缀编码

    仔细观察就会发现,表6-12-3中的编码就不存在容易与1001、1000混淆的"10"和"100"编码。

    可仅仅是这样不足以让我们去方便地解码的,因此在解码时,还是要用到赫夫曼树,即发送方和接收方必须要约定好同样的赫夫曼编码规则。

    当我们接收到 1001010010101001000111100 时,由约定好的赫夫曼树可知,1001得到第一个字母是B,接下来01意味着第二个字符是A,如图6-12-10所示,其余的也相应的可以得到,从而成功解码。

    一般地,设需要编码的字符集为{d1,d2,…,dn},各个字符在电文中出现的次数或频率集合为{w1,w2,…,wn},以d1,d2,…dn作为叶子结点,以w1,w2,…,wn作为相应叶子结点的权值来构造一棵赫夫曼树。规定赫夫曼树的左分支代表0,右分支代表1,则从根结点到叶子结点所经过的路径分支组成的0和1序列便为该结点对应字符的编码,这就是赫夫曼编码

    展开全文
  • 赫夫曼树的构建和赫夫曼编码的获取,最基础的内容,将课程的伪代码变为了可运行的
  • 赫夫曼树 一、什么是赫夫曼树? 如果给出一个学生的成绩从百分之转化为五级制,若使用ifelse则代码过于冗余,我们可以使用赫夫曼树的形式完成它: 但是出于查找更高效的考虑,我们可以将树构建成这样: 这样效率又...

    赫夫曼树

    一、什么是赫夫曼树?

    如果给出一个学生的成绩从百分制转化为五级制,若使用ifelse则代码过于冗余,我们可以使用赫夫曼树的形式完成它:

    在这里插入图片描述

    但是出于查找更高效的考虑,我们可以将树构建成这样:

    在这里插入图片描述

    这样效率又高了不少。

    二、赫夫曼树的定义与原理

    我们将上面这颗二叉树简化成带权二叉树:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-MSaGF8pH-1601463448290)(image-20200930183117115.png)]

    从树中一个节点到另一个节点之间的分支构成两个节点之间的路径,路径上的分支数目称做路径长度。 如a中根节点到D的路径长度为4,b中到D的路径长度为2

    树的路径长度就是从树根到每一节点的路径长度之和。 a的树路径长度就为1+1+2+2+3+3+4+4=20,b的树路径长度就为1+2+3+4+2+1+2+2=16

    节点的带权路径长度就为从该节点到树根之间的路径与结点上权的乘积。树的带权路径长度就为树中所有叶子节点的带权路径长度之和。假设有n个权值{w1,w2,w3,wn},构造一颗有n个叶子节点的二叉树,每个叶子节点带权wk,每个叶子的路径长度为lk,则称其中带权路径长度WPL最小的二叉树为赫夫曼树。 也称最优二叉树。

    那么a的WPL为 5 ∗ 1 + 15 ∗ 2 + 40 ∗ 3 + 30 ∗ 4 + 10 ∗ 5 = 315 5*1+15*2+40*3+30*4+10*5=315 51+152+403+304+105=315

    b的WPL为 5 ∗ 3 + 15 ∗ 3 + 40 ∗ 2 + 30 ∗ 2 + 10 ∗ 2 = 220 5*3+15*3+40*2+30*2+10*2=220 53+153+402+302+102=220

    三、如何构建赫夫曼树

    构建赫夫曼树的步骤:

    1. 将n个权值作为n个根节点,从小到大排序为一个有序的树集合
    2. 取出权值最小的两个树构建一颗新树,作为新树N的两个孩子
    3. 将N插入有序集合中,重新保持有序
    4. 重复步骤2,直到只含一棵树为止

    四、赫夫曼树的应用

    最基本的压缩编码方式:赫夫曼编码

    当年赫夫曼研究赫夫曼树的目的是为了优化电报的数据传输,例如我们的原文为BADCADFEED,并且知道六个字母的频率为A 27、B 8、C 15、D 15、E 30、F 5,合起来为100%,则我们可以构建一颗赫夫曼树:

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-5D8xhyRS-1601463448301)(image-20200930185020970.png)]

    并规定,左分支为0,右分支为1,那么我们可以得到这样的:

    字母ABCDEF
    二进制字符01100110100110000

    这样我们将原文就可以压缩为1001010010101001000111100,相比于其他的规定同样长度的01串短了很多。

    如果要设计长短不等的编码,则需要任一字符的编码都不是另一字符的前缀,这种编码称做前缀编码。

    给定字符集和各字符出现的次数或频率,以次数或频率作为叶子节点的权值来构建一个赫夫曼树,并规定左分支代表0,右分支代表1,则从根节点到叶子节点所经过的路径分治组成的01序列则为该节点对应字符的编码,称之为赫夫曼编码。

    五、赫夫曼树的相关性质

    赫夫曼树有他的一些性质:

    • 是正则二叉树,即树中只有度为0或2的节点
    • 有 n0 = n2 + 1,而 n = n0 + n2,故而 n0 = (n+1) /2,其中n0为叶节点,即编码

    六、赫夫曼树的代码实现

    这里给出赫夫曼书的Java实现:

    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 赫夫曼树
     *
     * auther:XingTL
     * date:2020/9/30 19:03
     */
    public class HuffmanTree {
        //节点类
        static class Node{
            int val;//权值
    
            Node left;
            Node right;
    
            public Node(int val){
                this.val = val;
            }
        }
    
        private Node root;
    
    
        public HuffmanTree(int[] vals){
            init(vals);
        }
    
        public HuffmanTree(){
            root = null;
        }
    
        //构建一颗赫夫曼树
        public void init(int[] vals){
            if(root != null){
                //只能初始化一次
                return;
            }
    
    
            List<Node> list = new ArrayList<>();
    
            for (int i = 0; i < vals.length; i++) {
                list.add(new Node(vals[i]));
            }
    
            while(list.size() > 1){
                Node n1 = getMin(list);
                Node n2 = getMin(list);
    
                Node node = new Node(n1.val+n2.val);
                node.left = n1;
                node.right = n2;
    
                list.add(node);
            }
            root = list.get(0);
        }
    
        //获取最小值并将其从list中移除
        private Node getMin(List<Node> list){
            if(list.isEmpty()){
                throw new RuntimeException();
            }
    
            int index = 0;
            Node min = list.get(index);
    
            for (int i = 1; i < list.size(); i++) {
                Node t = list.get(i);
                if(t.val < min.val){
                    min = t;
                    index = i;
                }
            }
            list.remove(index);
    
            return min;
        }
    
    
        //main 测试
        public static void main(String[] args) {
            int[] vals = {27,8,15,15,30,5};
    
            HuffmanTree huffmanTree = new HuffmanTree(vals);
    
            System.out.println();
        }
    }
    

    参考文献:《大话数据结构》

    展开全文
  • 赫夫曼树和赫夫曼编码的存储表示,自己搞定的,关键是一些总结。一些风格和数学的重要性,程序风格如HT[s1].parent=HT[s2].parent = i就淫荡的不行了,要分行在VC6下才能运行,数学也很重要,一些纠结的问题的时候,...
  • 哈夫曼编码实验报告实验一 哈夫曼编码实验目的掌握哈夫曼编码原理熟练掌握哈夫曼的生成方法;3、理解数据压缩二、实验要求实现哈夫曼编码和译码的生成算法。三、实验内容先统计要压缩编码的文件中的字符字母出现的...

    哈夫曼编码实验报告

    实验一 哈夫曼编码

    实验目的

    掌握哈夫曼编码原理

    熟练掌握哈夫曼树的生成方法;

    3、理解数据压缩

    二、实验要求

    实现哈夫曼编码和译码的生成算法。

    三、实验内容

    先统计要压缩编码的文件中的字符字母出现的次数,按字符字母和空格出现的概率对其进行哈夫曼编码,然后读入要编码的文件,编码后存入另一个文件;接着再调出编码后的文件,并对其进行译码输出,最后存入另一个文件中。

    五、实验原理

    1、哈夫曼树的定义:假设有n个权值,试构造一颗有n个叶子节点的二叉树,每个叶子带权值为wi,其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树;

    2、哈夫曼树的构造:weight为输入的频率数组,把其中的值赋给依次建立的HT Node对象中的data属性,即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序每次从取出两个最小和此次小的HT Node,将他们的data相加,构造出新的HTNode作为他们的父节点,指针parentleftchild,rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵

    ?? 通过已经构造出的,自底向上,由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样,根据每次向上搜索后,原节点为父节点的左孩子还是右孩子,来记录1或0,这样,每个频率都会有一个01编码与之唯一对应,并且任何编码没有前部分是同其他完整编码一样的。

    初始化,统计文本文件中各字符的个数作为权值,生成哈夫曼树

    根据符号概率的大小按由大到小顺序对符号进行排序

    把概率最小的两个符号组成一个节点

    重复步骤()(),直到概率和为1

    从根节点开始到相应于每个符号的“树叶”,概率大的标“0”,概率小的标“1”

    从根节点开始,对符号进行编码

    译码时流程逆向进行,从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码

    七、实验程序

    #include

    #include

    #include

    #include

    using namespace std;

    typedef struct //节点结构

    {

    char data; //记录字符值

    long int weight; //记录字符权重

    unsigned int parent,lchild,rchild;

    }HTNode,*HuffmanTree;

    typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表

    void Select(HuffmanTree &HT,int i,int &s1,int &s2) //在HT[1...t]中选择parent不为0且权值最小的两个结点,其序号分别为s1和s2

    {

    s1=0;s2=0;

    int n1=30000,n2=30000;

    for(int k=1;k<=i;k++)

    {

    if(HT[k].parent==0)

    {

    if(HT[k].weight

    {

    n2=n1; n1=HT[k].weight;

    s2=s1; s1=k;

    }

    else

    if(HT[k].weight

    {

    n2=HT[k].weight;

    s2=k;

    }

    }

    }

    }

    void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n)//将要编码的字符串存入空树中

    {

    ifstream fin1("zifu.txt");

    ifstream fin2("weight.txt");

    if(n<=1)return;

    int m=2*n-1;

    int i;

    HT=new HTNode[m+1];

    char *zifu;

    int *weight;

    zifu= new char[n+1];

    weight=new int[n+1];

    for(i=1;i<=n;i++)//将待编码的字符放在zifu数组中

    {

    char ch;

    ch=fin1.get();

    zifu[i]=ch;

    }

    for(i=1;i<=n;i++)//将带编码字符对应的权值放在weight数组中

    {

    fin2>>weight[i];

    }

    for( i=1;i<=n;i++)

    {

    HT[i].data=zifu[i];

    HT[i].weight=weight[i];

    }

    for(i=n+1;i<=m;i++)

    {

    HT[i].data='@';

    }

    for(i=1;i<=m;i++)

    展开全文
  • PAGE实 验 报 告课程名称: 数据结构实验名称: 赫夫曼编码及应用院 (系): 计算机与通信工程学院专业班级: 计算机科学与技术姓 名:学 号:指导教师:2020 年 5 月 12 日一、实验目的掌握赫夫曼树和赫夫曼编码的...
  • 关于赫夫曼树实验报告,里面包含对赫夫曼树设计的整个过程,从对文本文件的读取,以及建立赫夫曼树,对赫夫曼树进行编码和译码,最后还存在一个未解决的问题。
  • 赫夫曼编码编码和译码过程 加粗样式
  • 本人本科期间学习数据结构写的实验,内容如下 1、输入一段报文,例如: CAST CAST SAT AT A TASA ... 2、建赫夫曼树,并输出各个字符的赫夫曼编码 3、输入编码01100……,能准确翻译成报文 4、要求有菜单。
  • 构建哈夫曼,对其进行编码,实现译码功能,数据结构的实验报告。。
  • 哈夫曼编码实验

    2018-12-09 13:21:00
    Java哈夫曼编码实验--哈夫曼树的建立,编码与解码 建树,造树,编码,解码 一、哈夫曼树编码介绍 1、哈夫曼树: (1)定义:假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点...
  • 赫夫曼树和赫夫曼编码(C语言版)一.赫夫曼树(一)赫夫曼树的定义二.赫夫曼编码(一)赫夫曼编码的定义表示方法三.C语言编写(一)代码设计思路(二)源代码总览(三)部分源代码函数分析四.小结 一.赫夫曼树 ...
  • 这是本人在《数据结构》课上的 “ 哈夫曼编码和译码” 的实验报告程序。建议手动敲一遍加深印象。
  • 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本,试设计一个哈夫曼编码系统。
  • 二叉树的一个重要应用——赫夫曼树(最优二叉树),即所有叶子结点的平均带权路径最短。 赫夫曼算法叙述如下: (1)根据给定的n个权值{w1,w2,...wn}构成n棵二叉树的集合F={T1,,T2,...,Tn},其中每棵二叉树Ti中只有一个...
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼的基本概念及其...
  • 压缩包中包含实验报告,运行视频,...其中功能包括输入字母频率,然后生成相应的哈夫曼编码,然后编码txt文件中的文本,输出,并且会把输出结果存入文件。重新打开控制台,可以通过读取文件重新建立哈夫曼,就很强
  • //哈夫曼结构体集合 typedef struct Node{ int weight; int parent,lchild,rchild; }NODE,*PNODE; typedef struct HuffTree{ PNODE pbase; int len; }HUFFTREE,*PHUFFTREE; //哈夫曼编码结构体集合 ...
  • 补充提高实验(选做):哈夫曼与哈夫曼编码一.实验内容:实现哈夫曼编码的生成算法。二.实验目的:1、使学生熟练掌握哈夫曼的生成算法。2、熟练掌握哈夫曼编码的方法。三.问题描述:已知n个字符在原文中出现的...
  • 、数据结构课程设计报告题 目: 哈夫曼编码/译码学 院 数学与信息科学学院学科门类 理科专 业 数学类学 号 2013433033姓 名 田娟2014年 12 月30日目 录一、需求分析程序的功能··················...
  • 赫夫曼树,别名“哈夫曼树”、“最优树”以及“最优二叉树”。学习哈夫曼树之前,首先要了解几个名词。哈夫曼树相关的几个名词路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。哈夫曼树的编码c图 1 中...
  • 哈夫曼编码实验报告 实验一 哈夫曼编码 一实验目的 1掌握哈夫曼编码原理 2熟练掌握哈夫曼的生成方法 3理解数据编码压缩和译码输出编码的实 现 二实验要求 实现哈夫曼编码和译码的生成算法 三实验内容 先统计要压缩...
  • 一、实验目的 1、进一步掌握指针变量、动态变量的含义。 2、掌握二叉树的结构特性,以及各种存储结构的特点和适用范围。 3、掌握用指针类型描述、访问和处理二叉树的运算。...2、赫夫曼树的算法编码器的设计与实现
  • 1.目的:掌握赫夫曼(Huffman)赫夫曼编码的基本思想和应用。 2.任务:实现文件中数据的加解密与压缩。 二、内容、要求与安排方式 1.实验内容:将硬盘上的一个文本文件进行加密,比较加密文件和原始文件的...
  • /********************************...程序:赫夫曼树和赫夫曼编码的存储表示 完成者:小单 完成时间:2013年5月26日 *********************************************************/ //测试 #inclu
  • 实验赫夫曼编码及应用 实验学时:2 实验类型:综合型 一、目的与任务 1.目的:掌握赫夫曼(Huffman)赫夫曼编码的基本思想和应用。 2.任务:实现文件中数据的加解密与压缩。 二、内容、要求与安排方式 1....
  • 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码
  • 1、软 件 学 院哈夫曼与哈夫曼编码实验报告课程名称: 数据结构 姓 名: 郑斌 学 号: 7 班 级: 卓越131 实验四 哈夫曼与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼的生成算法。2、熟练掌握哈夫曼编码的...
  • 昆明理工大学信息工程与自动化学院学生实验报告 2011 2012 学年 第 1 学期 课程名称算法设计与分析 开课实验室信自楼机房 444 2011 年 11 月 02 日 年级专业班 学号 姓名 成绩 实验项目名称 哈夫曼编码 指导教师 教 ...

空空如也

空空如也

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

赫夫曼树及编码实验