霍夫曼编码_文件压缩及解压(Java实现)_java霍夫曼图形压缩和恢复-程序员宅基地

技术标签: 算法  java  霍夫曼树  数据结构与算法  数据结构  

一、明确功能

1、基础功能

将一串字符串"i like like like java do you like a java"利用霍夫曼编码原理进行压缩,并解压(即还原)。

2、扩展功能

进一步引入文件读写操作,对给定的图片或者文本文件,对其进行压缩,并将压缩的文件,重新恢复成原来的文件。

二、算法原理

1、霍夫曼树基本介绍

  • 霍夫曼树定义
    给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,即霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
  • 路径和路径长度
    在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。
  • 结点的权及带权路径长度
    若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度(weighted path length)为:从根结点到该结点之间的路径长度与该结点的权的乘积。如下图三种建树方式,图二实现的带权路径长度最小,wpl为59.
    在这里插入图片描述

2、霍夫曼树的创建思路

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

霍夫曼树的代码实现

要求:将数列 {13, 7, 8, 3, 29, 6, 1}转成一颗赫夫曼树。注意:因为数组是无法直接操作的,因此要先创建树的结点类Node。

package chuchu.huffmantree;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class HuffManTreeDemo {
   
    
    public static void main(String[] args) {
   
    
        int[] arr={
   
    13,7,8,3,29,6,1};
        Node root=huffmantree(arr);
        Preorder(root);//前序遍历
    }

    //将数组传进去,返回来的是搭建好的树的根节点
    public static Node huffmantree(int[] arr){
   
    
        List<Node> nodes=new ArrayList<Node>();
        for(int item:arr){
   
    
            Node cur=new Node(item);
            nodes.add(cur);
        }

        while(nodes.size()>1){
   
    
            Collections.sort(nodes);//先排序
            //System.out.println("nodes"+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;
			//删除旧节点,将新生成的节点加入
            nodes.remove(leftnode);
            nodes.remove(rightnode);
            nodes.add(parent);
        }
        return nodes.get(0);//返回整棵树的根节点

    }
    public static void Preorder(Node root){
   
    
        if(root!=null){
   
    
            root.preOreder();
        }else{
   
    
            System.out.println("空");
        }

    }
}

//为了让Node对象支持排序Collections集合排序,让Node实现Comparable接口
class Node implements Comparable<Node>{
   
    
    int value;//节点权值
    Node left;//左子节点
    Node right;//右子节点
    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;
        //若表示从大到小排序
        //return -(this.value-o.value);
    }

    //二叉树的前序遍历
    public void preOreder(){
   
    
        System.out.println(this);//先输出当前节点
        if(this.left!=null){
   
    
            this.left.preOreder();//处理左子节点
        }
        if(this.right!=null){
   
    
            this.right.preOreder();//处理右子节点
        }

    }
}

3、霍夫曼编码

  1. i like like like java do you like a java // 共40个字符(包括空格)
  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. 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值;
    在这里插入图片描述
  4. 根据赫夫曼树,给各个字符规定编码 ,向左的路径为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
  5. 按照上面的赫夫曼编码,我们的"i like like like java do you like a java" 字符串对应的编码为:
    1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
    长度为 : 133
    说明:原来长度是359 , 压缩了 (359-133) / 359 = 62.9%
    注意:此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性。

三、实现思路

1、实现对字符串的压缩编码

1、首先将字符串转为字节数组byte[],这一步很好实现,用getBytes()方法即可。

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

2、为实现霍夫曼编码,需要创建霍夫曼树。
(1)首先创建节点类:treeNode:

//构建节点类
class treeNode implements Comparable<treeNode>{
   
    
    Byte data;//存放的数据
    int value;//节点权值
    treeNode left;//左子节点
    treeNode right;//右子节点

    public treeNode(Byte data, int value) {
   
    
        this.data = data;
        this.value = value;
    }

    @Override
    public String toString() {
   
    
        return "treeNode{" +
                "data=" + data +
                ", value=" + value +
                '}';
    }

    @Override
    public int compareTo(treeNode o) {
   
    
        //表示从小到大排序
        return this.value-o.value;
        //若表示从大到小排序
        //return -(this.value-o.value);
    }

    //前序遍历
    public void preOreder(){
   
    
        System.out.println(this);
        if(this.left!=null){
   
    
            this.left.preOreder();
        }
        if(this.right!=null){
   
    
            this.right.preOreder();
        }

    }
}

(2)遍历byte[]数组,统计每个字符出现的次数,并将“字符->次数”作为键值(data->weight)转化为treeNode类型,并存入nodes集合中。

public static List<treeNode> getList(byte[] contentbytes){
   
    
        ArrayList<treeNode> nodes=new ArrayList<treeNode>();
        //遍历bytes,统计每个byte出现的次数
        Map<Byte,Integer>counts=new HashMap<>();
        for(byte item:contentbytes){
   
    
            Integer count=counts.get(item);//寻找Map中item对应的value
            if(count==null){
   
    //说明这个count还不存在
                counts.put(item,1);
            }else {
   
    
                counts.put(item,count+1);
            }
        }
        //把每对键值转化为treeNode并存入nodes集合中
        //遍历Map
        for(Map.Entry<Byte,Integer>entry:counts.entrySet()){
   
    
            nodes.add(new treeNode(entry.getKey(),entry.getValue()));
        }
        return nodes;

    }

(3)构建赫夫曼树,原理上面已经讲过,这里有必要注意的是:非叶子节点是没有存放数据的,即data为null。

//构建霍夫曼树
    public static treeNode createhuffmantree(List<treeNode> nodes){
   
    
        while(nodes.size()>1){
   
    
            Collections.sort(nodes);
            treeNode leftNode=nodes.get(0);
            treeNode rightNode=nodes.get(1);
            treeNode parentNode=new treeNode(null,leftNode.value+rightNode.value);//非叶子节点只有权重,没有data
            parentNode.left=leftNode;
            parentNode.right=rightNode;
            nodes.remove(0);
            nodes.remove(0);
            nodes.add(parentNode);
        }
        return nodes.get(0);
    }

(4)将霍夫曼树转为霍夫曼编码,并将每个字符和它对应的霍夫曼编码存入Map中。

/*
 * 功能描述:将霍夫曼树转为霍夫曼编码并存入Map中
 * @param: node:传入节点
 * @param: curcode:当前节点的路径
 * @param: stringBuilder:用于字符串拼接
*  @return void
        */
    public static void getCodes(treeNode node,String curcode,StringBuilder stringBuilder){
   
    
        StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
        stringBuilder2.append(curcode);
        if(node!=null){
   
    //如果node为空则不处理
            //判断是否为叶子节点
            if(node.data==null){
   
    //说明为非叶子节点
                getCodes(node.left,"0",stringBuilder2);
                getCodes(node.right,"1",stringBuilder2);
            }else{
   
    //是叶子节点
           
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41203254/article/details/104622131

智能推荐

c语言中a lt b a b是什么意思,C语言中c=a<b?a:b是什么意思-程序员宅基地

文章浏览阅读1.6k次。问: ^ 在C语言中是什么意思?答:这是C语言的逻辑运算符:异或这个网站讲的非常详细,我摘抄了一些,详细的你看以看看。有很例子,好懂!逻辑运算符把各个运算的变量(或常量)连接起来组成一个逻辑表达式。逻辑运算符有4个,它们分别是: !(逻辑非)、 ||(逻辑或)、&&(逻辑与) ^(异或)。在位运算里面还有 &(位与)、|(位或)的运算。 什么是逻辑运算--逻辑运算用来判断一件事情是“对”的还是“错..._c语言中c=a

IE浏览器常见的9个css Bug以及解决办法_在ie9上写css的一些bug-程序员宅基地

文章浏览阅读507次。我们在浏览网页的时候经常看见这样的现象:某个网页在IE6浏览器中打开很正常,但是在IE8里面打开可能完全变形了。或者也有可能出现完全相反的现象。这让Web程序员及设计师往往为了其CSS在各个IE版本下表现怪异而痛苦不已,有时候需要通过专为IE6或者IE8设计单独的定义。IE浏览器则因此被公认为Web程序员的毒药,虽然在微软官网上并没有提供相关的解决方案,但是IE浏览器的兼容性存在的问题却是Web程_在ie9上写css的一些bug

求java用人民币来转换美元,NJUPT JAVA语言 综合图形界面程序设计-程序员宅基地

文章浏览阅读873次。一、实验目的和要求学习和理解JAVASWING中的容器,部件,布局管理器和部件事件处理方法。通过编写和调试程序,掌握JAVA图形界面程序设计的基本方法。实验内容:设计和编写一个用于将人民币转换为等值的美元的程序,界面要求可以输入人民币的金额并可以得到转换后的结果。附:程序使用的人民币外汇牌价参考每100元美元等值买入人民币数:619.72(2015/5/23数据)二、实验代码package..._java jframe做货币转换

【JUnit4.10源码分析】3.4 Description与測试树-程序员宅基地

文章浏览阅读43次。Description使用组合模式描写叙述一个測试树。组合模式中全部元素都是Composite对象。Description有成员变量private final ArrayList<Description>fChildren= newArrayList<Description>(); //无元素保存其子结点。fChildren非空,所以不论什么子结点都是一个C...

找到第k个最小元----快速选择-程序员宅基地

文章浏览阅读166次。此算法借用快速排序算法。这个快速选择算法主要利用递归调用,数组存储方式。包含3个文件,头文件QuickSelect.h,库函数QuickSelect.c,测试文件TestQuickSelect。其中Cutoff可以自己给定,这个当开始给定的数组(或者递归调用产生的子数组)的元素个数<=20个时,采用插入排序。一般认为当元素个数<=20时,插入排序更快。这个20不是固定..._快速选择算法寻找第k小元素

C语言qsort库函数使用说明_c语言中调用库函数的原理-程序员宅基地

文章浏览阅读1.2k次,点赞2次,收藏12次。C语言qsort_c语言中调用库函数的原理

随便推点

Java2HTML改造手记(7)-程序员宅基地

文章浏览阅读227次。<!--google_ad_client = "pub-2947489232296736";/* 728x15, 创建于 08-4-23MSDN */google_ad_slot = "3624277373";google_ad_width = 728;google_ad_height = 15;//--><script type="text/javascript"

组件管理工具Bit_bit js 组件管理-程序员宅基地

文章浏览阅读3.2k次,点赞3次,收藏5次。对比Git你就知道Bit是什么了‘Bit loves Git’对,这是官方文档的原话。Git大家再熟悉不过了,世界上最先进的分布式版本控制系统,没有之一,‘近朱者赤’,大概这就是Bit喜欢Git的原因了。开个玩笑,其实是因为Bit的工作流和Git很相似,也是一个分布式工具。Git是管理源文件、源代码的,Bit也是用来管理代码,但不同的是Git不管你代码的语义结构,而Bit是将代码分..._bit js 组件管理

史上最全的机器学习资料(下)-程序员宅基地

文章浏览阅读165次。推荐:史上最全的机器学习资料(上)机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。机器学习牵涉的编程语言十分之广,包括了MATLAB、Julia、R、P..._stft stms

SpringBoot实战之增删改查_springboot实现增删改查-程序员宅基地

文章浏览阅读6.4w次,点赞13次,收藏189次。首先我们需要使用IDEA新建一个javaweb项目,步骤图示如下选择File菜单中的Project子菜单,弹出如下图所示窗口在右侧菜单中选择Spring Initial,如上图所示选择JDK的版本,此处为JDK1.8。弹出如下如所示的窗口 如上图所示输入包名、选择Maven构建项目,选择java语言,项目打包方式,选择Java JDK的版本,输入项目名称。点击Next弹出..._springboot实现增删改查

用ssh,往数据库插入中文时,出错,不是中文时,能正确插入数据库. 解决方法_ssh无法添加中文数据-程序员宅基地

文章浏览阅读1.1k次。1、问题:用ssh,往数据库插入中文时,出错,不是中文时,能正确插入数据库.即出现 ORA-01461: can bind a LONG value only for insert into a LONG column 解决方法:将原来用的是ojdbc14.jar 10.1.0.2.0,去下了一个ojdbc14.jar 10.2.0.3.0换上,立马就好了。来源: http://ww_ssh无法添加中文数据

bootstraptable冻结列无效_bootstrap-table-冻结列样例-程序员宅基地

文章浏览阅读217次。【实例简介】【实例截图】【核心代码】Fixed ColumnsFixed Columnsif you like bootstrap-table-fixed-columns - help:src="http://ghbtns.com/github-btn.html?user=wenzhixin&repo=bootstrap-table-fixed-columns&type=watch..._table 合并列 冻结列不生效

推荐文章

热门文章

相关标签