赫夫曼树及赫夫曼编码的分步骤实现-超详细!_设计赫夫曼编码的步骤-程序员宅基地

技术标签: java  二叉树  字符串  数据结构  

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;
    }


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_40589204/article/details/109547416

智能推荐

Java8 parallelStream——共享线程池对性能解析_jdk8 parallelstream 性能-程序员宅基地

文章浏览阅读3.3k次,点赞2次,收藏8次。最近做压测中发现一个应用中cpu过高,导致接口超时rt情况有些不大稳定,jstack打印线程一直在parallelStream相关的代码出进行计算。故对parallelStream相关做一下研究,找一下优化方法。java8并行流parallelStream,相信很多人都喜欢用,特别方便简单。但是有多少人真正知道里面采用的共享线程池对密集型任务,高并发下的性能影响呢可能你的一个应用里面..._jdk8 parallelstream 性能

C++ 11 创建和使用 unique_ptr_unique_ptr创建空节点-程序员宅基地

文章浏览阅读292次。https://www.cnblogs.com/DswCnblog/p/5628195.htmlunique_ptr 不共享它的指针。它无法复制到其他 unique_ptr,无法通过值传递到函数,也无法用于需要副本的任何标准模板库 (STL) 算法。只能移动unique_ptr。这意味着,内存资源所有权将转移到另一 unique_ptr,并且原始 unique_ptr 不再拥有此资源。我们建议..._unique_ptr创建空节点

NetCoreAPI配置全局路由_selector.attributeroutemodel.template-程序员宅基地

文章浏览阅读853次。1:新增类:RouteConvention,继承自IApplicationModelConvention/// <summary> /// 全局路由前缀配置 /// </summary> public class RouteConvention : IApplicationModelConvention { /// <summary> /// 定义一个路由前缀变量 /// </su_selector.attributeroutemodel.template

算 数-程序员宅基地

文章浏览阅读64次。从woody那里copy一段最简的fib代码[code="ruby"]x,y = 0,1 Array.new(10) {|i| [0,1].include?(i) ? 1 : (x,y = y,x+y)&&(x+y) } [/code]生成了这么多,太多了,中途终止了,不知道多少条。[code="ruby"] 1, 1, 2, ..._359579325206583560961765665172189099052367214309267232255589801

Java的BIO和NIO很难懂?用代码实践给你看,再不懂我转行!-程序员宅基地

文章浏览阅读280次。本文原题“从实践角度重新理解BIO和NIO”,原文由Object分享,为了更好的内容表现力,收录时有改动。1、引言这段时间自己在看一些Java中BIO和NIO之类的东西,也看了很多博客,发现各种关于NIO的理论概念说的天花乱坠头头是道,可以说是非常的完整,但是整个看下来之后,发现自己对NIO还是一知半解、一脸蒙逼的状态(请原谅我太笨)。基于以上原因,..._java bio粘包处理

Python3.9环境搭建RobotFramework_python-3.9.9-amd64用那个版本ride-程序员宅基地

文章浏览阅读9k次,点赞2次,收藏12次。Robot Framework是一个基于Python的,可扩展的关键字驱动的测试自动化框架,用于端到端验收测试和验收测试驱动开发(ATDD)。_python-3.9.9-amd64用那个版本ride

随便推点

Hbase相关操作_hbase 查询-程序员宅基地

文章浏览阅读2.4k次。1.进入shellhbase(main):003:0>hbase shell2.查看所有表hbase(main):003:0> list3.根据rowKey查询某个记录hbase(main):003:0>get '表名','rowKey'4.常用过滤器过滤方式是通过value过滤,匹配出value含7259的数据。scan 'buss_surface', FILTER=>"ValueFilter(=,'substring:7259')"过滤方式是通_hbase 查询

噪声:Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-data-程序员宅基地

文章浏览阅读2k次,点赞4次,收藏16次。Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-data文章目录Practical Poissonian-Gaussian noise modeling and fitting for single-image raw-dataPoissonian-Gaussian ModelingThe Noise Profile AlgorithmWavelet domain analysisSegmentat_practical poissonian-gaussian noise modeling and fitting for single-image ra

计算机开机最快设置,w7提高开机速度如何操作_win7电脑怎么开机更快-程序员宅基地

文章浏览阅读4k次。由于win7电脑使用时间过长或者存放时间久了,难免会出现硬件各方面的老化或者堆积了大量的垃圾,因此就会导致电脑开机时的速度有所降低,对此有些用户就想,在不更换硬件的条件下,有没有方法能够提高一下开机速度,那么win7电脑提高开机速度如何操作呢?这里小编就来告诉大家win7电脑开机更快操作步骤。具体方法:1、在任意界面按下:windows键+R,然后在框内输入msconfig,点确定2、然后选择“启..._如何提高w7系统的开机速度

1688API接口:item_search - 按关键字搜索商品_1688 一件代发 api-程序员宅基地

文章浏览阅读672次。今天分享的是1688平台API,item_search - 按关键字搜索商品接口1688的API开发接口,我们需要做下面几件事情。1)开放平台注册开发者账号;2)然后为每个1688应用注册一个应用程序键(App Key) ;3)下载1688API的SDK并掌握基本的API基础知识和调用;4)利用SDK接口和对象,传入AppKey或者必要的时候获取并传入SessionKey来进行程序开发;5)利用1688平台的文档中心和API测试工具,对接口进行测试。从而了解返回信息,方便程序获取1688_1688 一件代发 api

vue-property-decorator使用指南_vue-property-decorator emit update-程序员宅基地

文章浏览阅读3.1k次,点赞2次,收藏12次。在Vue中使用TypeScript时,非常好用的一个库,使用装饰器来简化书写。一、安装npmi-Svue-property-decorator@Prop @PropSync @Provide @Model @Watch @Inject @Provide @Emit @Component(provided byvue-class-component) Mixins(the helper function namedmixinsprovided byvue-cla..._vue-property-decorator emit update

(七)用ChartDirector绘制实时图表-程序员宅基地

文章浏览阅读467次。本示例演示如何用Web图表控件 ChartDirector 绘制一个配置有刷新率的实时图表。在本例中,由一个计时器驱动的随机数生成器生成新的数据值,新产生的值会转换到数据数组中,然后显示在图表上。图表由一个秒表进行更新,这样图表的刷新率可独立于数据率。此外,这个图表支持暂停以方便用户查看,但是后台的数据仍然在继续更新。图表刷新计时器调用CChartViewer.update..._c++ chartdirect updateviewport