关于java:我所知道的算法之哈夫曼编码

上一篇文章中提到数据结构：哈夫曼树，明天接着学习由哈夫曼提出编码方式，一种程序算法。简称：哈夫曼编码

在线转码工具: https://www.mokuge.com/tool/a...

一、什么是哈夫曼编码？

与哈夫曼树一样，会不会有小伙伴对哈夫曼编码很生疏，有纳闷

问题纳闷

1.哈夫曼编码是做什么的？有什么用？
2.为什么要应用哈夫曼编码？应用别的编码行不行？

哈夫曼编码是做什么的？有什么用？

哈夫曼（Huffman）编码算法

它是基于二叉树构建编码压缩构造的，它是数据压缩中经典的一种算法：依据文本字符呈现的频率，从新对字符进行编码

那么就会有小伙伴说：什么是数据压缩？什么是字符编码？

字符编码压缩介绍

在咱们的世界里，咱们能够看到丑陋的图像、好听的声音、震撼的视频等等这些精彩内容。然而对于计算机说，它的世界里只有二进制的 0 和 1。

因而在数字电子电路中，逻辑门的实现间接利用了二进制，因而古代的计算机和依赖计算机的设施里都用到二进制。

那么在二进位电脑系统中，存储的单位有：bit、kb、mb、gb

bit 电脑记忆体中最小的单位，每一bit 只代表0 或 1 的数位讯号

Byte由八个 bits 所组成，可代表：字元(A~Z)、数字(0~9)、或符号(,.?!%&+-*/)

当记忆体容量过大时，位元组（byte）这个单位就不够用，因而就有千位元组的单位KB呈现，以下乃个记忆体计算单位之间的相关性：

1 Byte = 8 Bits
1 KB = 1024 Bytes
1 MB = 1024 KB
1 GB = 1024 MB

咱们当初在计算机上看到的所有的图像、声音、视频等内容，都是由二进制的形式进行存储的

简略来讲，咱们把信息转化为二进制的过程能够称之为编码

编码方式从长度上来分大抵能够分为两个大类：

定长编码表明：段与段之间长度雷同，没阐明是多长。
变长编码表明：段与段之间的长度不雷同，不定义具体有多长。

`请留神！这里并没有表明是多长！这会导致无奈辨别编码信息与文件内容的拆散！造成乱码!`

自然语言的分隔问题

民可使由之不可使知之 ——_出自《论语第八章泰伯篇》_

这么一串十个字要如何去分隔并解释呢？

断法解释一：

民可使由之，不可使知之。
解释：你能够去驱使你的民众，但不可让他们晓得为什么（不要去教他们常识）

断法解释二：

民可，使由之；不可，使知之。
解释：民众能够做的，撒手让他们去做；不会做的，教会他们如何去做（又或：不能够去做的，让他们明确为何不能够）

显然，以上的文字是以某种定长或变长的形式组合在一起的，然而对于它们如何分隔的信息则被抛弃了，于是在解释时就存在产生歧义可能了。

举个栗子，如果咱们对「pig」进行自定义编码，应用定长编码，为了不便，采纳了十进制，原理与二进制是一样的。

假如咱们当初有文件，内容是：00080008

如果定长 2 位是惟一的编码方案，用它去解码就会失去：「pipi」
如果定长 4 位是惟一的编码方案，用它去解码就会失去：「ii」

如果文件的内容并没有暗示它应用了何种编码！就会呈现解释时存在产生歧义。

这就好比孔夫子写下“民可使由之不可使知之”时

并没有暗示它是5|5分隔（民可使由之|不可使知之）

还是暗示它是2|3|2|3分隔（民可|使由之|不可|使知之）。

其实当咱们有字节这一根本单位后，咱们就能够说得更具体：如定长一字节或者定长二字节。

比如说ASCII码它是最早也是最简略的一种字符编码方案：应用定长一字节来示意一个字符

示例编码意识差别

其实当初咱们的计算机的世界里编码总曾经有很多种格局

比方常见的： ASCII 、 Unicode 、 GBK 、 GB2312 、 GB18030 、 UTF-8 、 UTF-16 等等。

ASCII编码介绍

咱们都晓得在计算机的世界里只有二进制0和1，通过不同的排列组合，能够应用 0 和 1 就能够示意世界上所有的货色。

是不是有咱们中国"太极"的感觉。

——“太极生两仪，两仪生四象，四象生八卦

而在计算机中：一字节 = 八位二进制数(二进制有0和1两种状态)
因而一字节能够组合出二百五十六种状态。

如果这二百五十六种状态每一个都对应一个符号，就能通过一字节的数据表示二百五十六个字符。

美国人于是就制订了一套编码（其实就是个字典），形容英语中的字符和这八位二进制数的对应关系，这被称为 ASCII 码。

随着时代的倒退，不仅美国人要对他们的英文进行编码，咱们中国人也要对汉字进行编码。

而晚期的 ASCII 码的计划只有一个字节，对咱们汉字文化而言是远远不够的

编码的倒退

这点可怜的空间拿到中国来，它能编码的汉字量也就小学一年级的程度。

这也就导致了不同的需要推动了倒退，各种编码方案都进去了，彼此之间的转换也带来了诸多的问题。采纳某种对立的规范就势在必行了，于是乎天上一声霹雳，Unicode退场！

Unicode晚期是作为定长二字节计划进去的。它的实践编码空间一下达到了64k

不过对于能够只须要应用到一个字节的ASCII 码就能够示意的美国人来讲，让他们应用 Unicode ，多少还是不是很违心的。

比方「he」两个字符，用 ASCII 只须要保留成 6865 ( 16 进制)，当初则成了 00680065 ，后面多的那两个 0 （用作站位）。

基本上能够说是毫无意义，用 Unicode 编码的文本，原来可能只有 1KB 大小，当初要变成 2KB ，体积成倍的往上涨。

可是更蹩脚的事还在后头，咱们中文可是字符集外面的大头。

1.“茴字有四种写法”——上小孩儿孔乙己
2.据说有些早先整顿的汉语字典收录的汉字数量曾经高达10万级别！

如果还是定长的计划，眼瞅着就要奔着四字节而去了，容量与效率的矛盾在这时候开始激化。

容量与效率的矛盾

所谓容量，这里指用几个字节示意一个字符，显然用的字节越多，编码空间越大，能示意更多不同的字符，也即容量越大。
所谓效率，当示意一个字符用的字节越多，所占用的存储空间也就越大，换句话说，存储（乃至检索）的效率升高了。

如果说效率是阴，那么容量就是阳。
（_我没还没遗记自小学语文老师就开始教诲的，写作文要一唱一和_）

莫尔斯电码图

看如图所示你就会发现，字母e只用了一个点（dot）来编码

其它字母可能感觉不偏心，为啥咱们就要录入那么多个点和划（dash）才行呢？这外面其实是有统计法则撑持的。e呈现的概率是最大的

z你能想到什么？

zoo大略很多人能想到，厉害一点可能还能想到zebra（斑马），Zuckerberg（扎克伯格），别翻字典！你还能想到更多不？

e你能想到什么？

含有的e的单词则多了去了。zebra中不就有个e吗，Zuckerberg中还两个e呢

所以咱们心愿频率越高的词，编码越短，这样最终能力最大化压缩存储文本数据的空间。

为什么要应用哈夫曼编码？应用别的编码行不行？

下面提到常见的信息处理形式：定长编码与变长编码

假如以后有一句话：i like like like java do you like a java（共40个字符，包含空格）

那么依照定长编码解决，那么会变成什么呢？

咱们发现最初存在计算机中（二进制）长度是：三百五十九

那么依照变长编码解决，那么会变成什么呢？

假如咱们将这串10010110100...发给他人，然而没有阐明解码的形式，这时就会呈现解释时存在产生歧义。

比如说可能翻译成："a a a aa a "，所以咱们须要阐明字符编码不能是其余字符编码的前缀，即不能匹配反复的编码。

那么依照哈夫曼解决，那么会变成什么呢？

相比定长编码二进制的长度：三百五十九，哈夫曼二进制长度为：一百三十三

那么相比定长编码二进制的长度优化了多少呢？：(359-133)/359=62.9%

咱们再将哈夫曼二进制转码对应的byte字符

那么相比原字符长度优化了多少呢？：(40-17)/40 = 57.5%

一下将原字符40位变成17位，这样的状况下，是不是咱们想要的

二、解析哈夫曼编码执行思路与过程

下面咱们采纳"i like like like java do you like a java"，做例子剖析，那么咱们当初剖析剖析哈夫曼编码思路

将字符串里的字符进行统计个数并转为Byte[]数组
依据字符的呈现次数构建一颗哈夫曼树、次数为权值
依据哈夫曼树进行自定义哈夫曼编码实现
将原字符的所有哈夫曼编码构建成编码串
依据编码串进行补码->反码->原码构建新字符

三、统计字符呈现次数并构建哈弗曼树

图解思路剖析

获取传输的字符串："i like like like java do you like a java"
获取各个字符对应的个数：d:1 y:1 u:1 j:2 v:2 0:2 l:4 k:4 e:4 i:5 a:5 (空格):9
依照下面的字符呈现的次数构建成一颗哈夫曼树，呈现的个数作为权值

构建哈夫曼树的步骤思路

1.将数列进行从小到大排序
2.新数列的每个数看成最简略根节点的二叉树
3.取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和
4.将新二叉树以跟节点的权重值再次从小到大排序，一直反复步骤

构建哈夫曼树的代码思路

Node{data：存放数据，weight：权重，left和right}
失去"i like like like java do you like a java"对应byte[]数组
编写办法，将筹备构建赫夫曼树的Node节点放到List：Node[data=97, weight= 5],Node[data=32,weight = .....
通过List创立对应的哈夫曼树

体现获取各个字符对应的个数：d:1 y:1 u:1 j:2 v:2 0:2 l:4 k:4 e:4 i:5 a:5 (空格):9

比如说字符：a 应该是Node[data='a', weight= 5]，data为什么会是97而不是a？

因为底层：字母等于ASCII数字

构建哈夫曼树的代码实现

那么第一步：创立节点Node{data：存放数据，weight：权重，left和right}

class Nodedata implements Comparable<Nodedata>{    Byte data; //存放数据（字符）自身，比方'a' =>97 '' =>32    int weight; //权值，示意字符呈现的次数    Nodedata left;    Nodedata right;    public Nodedata(Byte data, int weight) {        this.data = data;        this.weight = weight;    }    @Override    public int compareTo(Nodedata o) {        return this.weight - o.weight;    }    @Override    public String toString() {        return "Nodedata[" +"data=" + data + ", weight=" + weight +']';    }}

第二步：失去"i like like like java do you like a java"对应byte[]数组

public static void main(String[] args) {          //失去`"i like like like java do you like a java"`对应byte[]数组     String content = "i like like like java do you like a java";     byte[] contentBytes = content.getBytes();     System.out.println(contentBytes.length);}

第三步：编写办法，将筹备构建赫夫曼树的Node节点放到List

private static List<Nodedata> getNodes(byte[] bytes){    //1.创立一个ArrayList    List<Nodedata> nodeslist = new ArrayList<Nodedata>();    //2.遍历bytes，统计每一个byte呈现的次数->map[key,value]    Map<Byte,Integer> map = new HashMap<>();    for(byte b :bytes){        Integer items = map.get(b);        if(items == null){            map.put(b,1);        }else{            map.put(b, items + 1);        }    }    //3.把每个键值对转为Node 对象，并放入nodeslist汇合里    for(Map.Entry<Byte,Integer> temp :map.entrySet()){        nodeslist.add(new Nodedata(temp.getKey(),temp.getValue()));    }    return nodeslist;}

第四步：通过List创立对应的哈夫曼树

private static Nodedata createHaffman(List<Nodedata> nodedataList){    while(nodedataList.size() >1){        //排序从小到大         Collections.sort(nodedataList);         /**         *  操作思路          *  1.取出两个权值最小的节点二叉树          *  2.依据两个权值最小的二叉树构建成一个新的二叉树         *  3.删除原先两个权值最小的节点二叉树         *  4.将新的二叉树放入队列，并构建新的队列         *  5.新的队列进行从小到大排序         */         //取出第一个权值最小的二叉树         Nodedata leftNode = nodedataList.get(0);         //取出第二个权值最小的二叉树         Nodedata rightNode = nodedataList.get(1);         //依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯         Nodedata parentNode  = new Nodedata(null,leftNode.weight + rightNode.weight);         parentNode.left = leftNode;         parentNode.right = rightNode;         //删除原先两个权值最小的节点二叉树         nodedataList.remove(leftNode);         nodedataList.remove(rightNode);         //将新的二叉树放入队列，并构建新的队列         nodedataList.add(parentNode);     }    return nodedataList.get(0);}

测试查看是否满足代码思路

查看是否Byte[]长度：40

public static void main(String[] args) {          //失去`"i like like like java do you like a java"`对应byte[]数组     String content = "i like like like java do you like a java";     byte[] contentBytes = content.getBytes();     System.out.println("byte[]数组长度为:"+contentBytes.length);}运行后果如下：byte[]数组长度为:40

查看字符个数：d:1 y:1 u:1 j:2 v:2 0:2 l:4 k:4 e:4 i:5 a:5 (空格):9

public static void main(String[] args) {          //将筹备构建哈弗曼树的Node节点放到List：Node[data=97, weight= 5],Node[data=32,weight = .....    List<Nodedata> datalist = getNodes(contentBytes);    for(Nodedata data : datalist){        System.out.println(data);    }}运行后果如下：Nodedata[data=32, weight=9]Nodedata[data=97, weight=5]Nodedata[data=100, weight=1]Nodedata[data=101, weight=4]Nodedata[data=117, weight=1]Nodedata[data=118, weight=2]Nodedata[data=105, weight=5]Nodedata[data=121, weight=1]Nodedata[data=106, weight=2]Nodedata[data=107, weight=4]Nodedata[data=108, weight=4]Nodedata[data=111, weight=2]

Nodedata 节点增加前序遍历，增加哈弗曼树办法

class Nodedata implements Comparable<Nodedata>{     //省略实体类代码     //前序遍历办法     public void preOrder(){        System.out.println(this);        if(this.left != null){           this.left.preOrder();        }        if(this.right != null){           this.right.preOrder();        }    }}

private static void preOrder(Nodedata root){    if(root != null){        root.preOrder();    }else{        System.out.println("哈弗曼树为空！");    }}

查看前序遍历哈弗曼树，查看是否图统一：40->17->8->4->4->2->2->9...

public static void main(String[] args) {          //获取哈弗曼树的根节点     Nodedata root = createHaffman(datalist);     //遍历哈弗曼树     preOrder(root);}运行后果如下：Nodedata[data=null, weight=40]Nodedata[data=null, weight=17]Nodedata[data=null, weight=8]Nodedata[data=108, weight=4]Nodedata[data=null, weight=4]Nodedata[data=106, weight=2]Nodedata[data=111, weight=2]Nodedata[data=32, weight=9]Nodedata[data=null, weight=23]Nodedata[data=null, weight=10]Nodedata[data=97, weight=5]Nodedata[data=105, weight=5]Nodedata[data=null, weight=13]Nodedata[data=null, weight=5]Nodedata[data=null, weight=2]Nodedata[data=100, weight=1]Nodedata[data=117, weight=1]Nodedata[data=null, weight=3]Nodedata[data=121, weight=1]Nodedata[data=118, weight=2]Nodedata[data=null, weight=8]Nodedata[data=101, weight=4]Nodedata[data=107, weight=4]

那么咱们后面剖析了如何将字符转为哈弗曼树的思路与代码

上面看看如何将依据哈夫曼树进行形成自定义哈夫曼编码。

四、依据哈夫曼树自定义哈夫曼编码

依据哈夫曼树咱们来自定义编码规定：向左为0、向右为1
这样依据下面如图所示，定义的字符编码如下：[o: 0011 u: 11001 d: 11000 y: 11010 i: 101 a: 100 k: 1111 e: 1110 j: 0010 V: 11011 I: 000 (空格):01]

有没有发现哈弗曼树的节点编码它是前缀编码：不是是其余字符编码的前缀，即匹配不到反复的编码。

依据哈夫曼树自定义哈夫曼编码代码思路剖析

应用StringBuilder记录所通过的门路:'a'的门路是:1->1->0
应用Key:Value 键值的形式寄存对应的字符：门路;比方：(a:1000)、(j:0010)、(o:0011)
字符特点：data !=null （属于叶子节点)
假如查问字符v的门路，发现左递归不合乎后还须要进行右递归判断

依据哈夫曼树自定义哈夫曼编码代码实现

//将哈夫曼编码以Key：Vale模式寄存//比如说32->01 97->100 100->11000 等等[模式]static Map<Byte,String> huffmanCodes = new HashMap<Byte,String>();//2.在生成赫夫曼编码表示，须要去拼接门路，定义一个StringBuilder 存储某个叶子结点的门路static StringBuilder stringBuilder = new StringBuilder();/** * 1.性能:将传入的node结点的所有叶子结点的赫夫曼编码失去，并放入到huffmanCodes汇合 * @param node 传入节点 * @param code 门路：左节点是0 右节点是1 * @param stringBuilder 用于拼接门路 */ private static void getCodes(Nodedata node,String code,StringBuilder stringBuilder){    StringBuilder str = new StringBuilder(stringBuilder);    //将code退出到str 总    str.append(code);    if(node!=null){        //字符特点：`data !=null `（属于叶子节点)        if(node.data ==null){//（属于非叶子节点)         //向左递归         getCodes(node.left,"0",str);         //向右递归         getCodes(node.right,"1",str);    }else{         //`应用Key:Value 键值`的形式寄存对应的`字符：门路;`比方：`(a:110)、(j:0000)、(o:1000)`         huffmanCodes.put(node.data,str.toString());     }  }    }

咱们优化一下代码，实现传入根节点就能够返回哈夫曼编码

private static Map<Byte,String> getCodes(Nodedata node){     //根节点为空则不做解决     if(node == null){        return null;     }     //向左递归     getCodes(node.left,"0",stringBuilder);     //向右递归     getCodes(node.right,"1",stringBuilder);     return huffmanCodes;}

咱们进行运行测试看看，是否欲思路统一生成编码

public static void main(String[] args) {    //将哈夫曼树生成哈夫曼编码    //getCodes(root,"",stringBuilder);        //执行优化代码    getCodes(root);}运行后果如下：生成的哈夫曼编码表：{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}

`留神:不同的排序形式会生成不同的哈弗曼树，所造成的哈夫曼编码也不一样，但WPL是统一`

五、将原字符的所有哈夫曼编码构建成编码串

咱们将"i like like like java do you like a java"字符串，即生成对应的哈夫曼编码数据(如下)

将原字符串转为编码串思路剖析

将字符串"i like like like java do you like a java"转为对应的Byte[]数组
应用StringBuilder追加存储byte字符的对应字符门路

将原字符串转为编码串思路剖析代码实现

private static void zip(byte[] bytes, Map<Byte, String> huffmanCodes) {     //1.利用huffmanCodes将bytes 转成赫夫曼编码对应的字符串     StringBuilder stringBuilder = new StringBuilder();     //遍历bytes数组     for(byte b: bytes) {        stringBuilder.append(huffmanCodes.get(b));     }     System.out.printf("stringBuilder=" + stringBuilder.toString());     System.out.print("\n stringBuilder的长度=" + stringBuilder.length());}

代码测试

public static void main(String[] args) {    //失去`"i like like like java do you like a java"`对应byte[]数组    String content = "i like like like java do you like a java";    byte[] contentBytes = content.getBytes();    System.out.println("byte[]数组长度为:"+contentBytes.length);    //将筹备构建哈弗曼树的Node节点放到List：Node[data=97, weight= 5],Node[data=32,weight = .....    List<Nodedata> datalist = getNodes(contentBytes);    //获取哈弗曼树的根节点    Nodedata root = createHaffman(datalist);    //将哈夫曼树生成哈夫曼编码Key:Value    getCodes(root);    //将Byte[]数组转为自定义的哈夫曼编码字符门路    zip(contentBytes,huffmanCodes);}运行后果如下：byte[]数组长度为:40stringBuilder=1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100stringBuilder的长度=133

咱们将"i like like like java do you like a java"

转为编码串相比之前定长编码优化了多少呢？：(359-133)/359=62.9%

六、将编码串进行补码->反码->原码构建新字符

那么如何将长度一百三十三的二进制串转为新的字符呢？

在讲编码串进行补码->反码->原码构建新字符前，先解释理解理解不同的进制

雷同的数字有不同的样子

在计算机的世界中就分两种人：意识二进制和不意识二进制

下面咱们介绍到咱们看到的丑陋的图像、好听的声音、震撼的视频等等这些精彩内容。然而对于计算机说，它的世界里只有二进制的 0 和 1。

所有数字在计算机底层都以二进制模式存在
对于整数有不同表达方式：二进制、十进制、八进制、十六进制

二进制与十进制的阐明

咱们应用Byte字符的二进制做演示，首先咱们直观一点举例负数阐明

以此类推....那么十进制转二进制该怎么做呢？来看看法则

有没有发现？从右开始往左是2^0(二的零次方)、2^1（二的一次方）、2^2（二的平方）、2^3（二的三次方）

依据后面知识点，你晓得：01101110的十进制是多少么？

那么咱们说Byte示意 -128 ~127 ，那么0和1 是怎么示意负数和正数的呢？

咱们当初晓得二进制的最高位：0 负数 1-正数 ，那么对于整数还要提提三个码：原码、反码、补码

那么咱们思考一下：在计算机中： -14 是什么样的呢？

接下来看看正数的解析图:十进制：14、二进制：00001110

那么咱们当初反推一下：10111011 转为十进制是多少呢？

咱们刚刚提到计算机底层都以补码形式存储
咱们刚刚察看晓得最高位： 0 - 负数、1-正数
而正数则是补码的模式，那么思路反推：补码->反码->原码

接下来我置信大家都理解了什么是原码、反码、补码了

下面咱们将字符串"i like like like java do you like a java" 转为了自定义的哈弗曼编码串

接下来咱们创立Byte[] huffmanCodeBytes，解决哈夫曼编码串，以八位为一组对应一个Byte 放入huffmanCodeBytes中

转为新字符代码的思路剖析

每八位对应一个Byte，所以133 % 8，应用循环每次 i + 8
因为每次 i + 8 所以须要应用变量index 记录对应的第几位Byte
应用（byte）Integer.parInt(string,radix)转码

转为新字符代码的代码实现

private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {    //1.利用huffmanCodes将bytes 转成赫夫曼编码对应的字符串     StringBuilder stringBuilder = new StringBuilder();     //遍历bytes数组     for(byte b: bytes) {        stringBuilder.append(huffmanCodes.get(b));     }     //2.1010100010111111...思路：补码->反码->原码->转成Byte     int len;     if(stringBuilder.length() %8 == 0){         len = stringBuilder.length() /8;     }else{         len = stringBuilder.length() /8 + 1;     }     //3.创立存储压缩后的byte数组     byte[] huffmanCodeBytes = new byte[len];     int index = 0;//记录是第几个byte     for (int i = 0; i < stringBuilder.length(); i += 8) { //因为是每8位对应一个byte,所以步长+8         String strByte;         if(i+8 > stringBuilder.length()) {//不够8位            strByte = stringBuilder .substring(i);         }else {            strByte = stringBuilder .substring(i, i + 8);         }         //将strByte转成一个byte ,放入到huffmanCodeBytes         huffmanCodeBytes[index] = (byte)Integer .parseInt(strByte, 2);         index++;    }    return huffmanCodeBytes;}

public static void main(String[] args) {    //失去`"i like like like java do you like a java"`对应byte[]数组    String content = "i like like like java do you like a java";    byte[] contentBytes = content.getBytes();    System.out.println("byte[]数组长度为:"+contentBytes.length);        //将筹备构建哈弗曼树的Node节点放到List：Node[data=97, weight= 5],Node[data=32,weight = .....    List<Nodedata> datalist = getNodes(contentBytes);        //获取哈弗曼树的根节点    Nodedata root = createHaffman(datalist);        //将哈夫曼树生成哈夫曼编码    getCodes(root);        byte[] huffmanCodeBy =zip(contentBytes,huffmanCodes);    System.out.println(Arrays.toString(huffmanCodeBy));}运行后果如下：byte[]数组长度为:40[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]

那么相比原字符长度优化了多少呢？：(40-17)/40 = 57.5%

一下将原字符40位变成17位

七、封装间接返回新符号Byte[]办法

依据后面的剖析，咱们调用的办法比拟多也比拟臃肿，每次测试须要

将字符串转为Byte数组，并统计个数
依据字符呈现次数作为权重，构建哈弗曼树
依据哈弗曼树生成自定义哈弗曼编码
将原字符的所有哈夫曼编码构建成编码串
依据编码串进行补码->反码->原码构建新字符

当初呢，咱们将封装这些办法不便咱们调用，咱们的目标是获取到新字符组

//应用一个办法将须要的办法疯转起来，不便调用private static  byte[] haffmanZip(byte[] bytes){    //将筹备构建哈弗曼树的Node节点放到List：Node[data=97, weight= 5],Node[data=32,weight = .....     List<Nodedata> datalist = getNodes(bytes);     //依据字符呈现次数作为权重，构建哈弗曼树     //获取哈弗曼树的根节点      Nodedata root = createHaffman(datalist);     //依据哈夫曼树进行自定义哈夫曼编码实现     Map<Byte,String> huffmanCodes = getCodes(root);     //将原字符的所有哈夫曼编码构建成编码串     //依据编码串进行补码->反码->原码构建新字符     byte[] huffmanCodeBy =zip(bytes,huffmanCodes);     return huffmanCodeBy;}

public static void main(String[] args) {    String content = "i like like like java do you like a java";    byte[] contentBytes = content.getBytes();    System.out.println("byte[]数组长度为:"+contentBytes.length);    byte[] huffmanCodeBy =haffmanZip(contentBytes);    System.out.println(Arrays.toString(huffmanCodeBy));    System.out.println("压缩后的byte[]数组长度为:"+huffmanCodeBy.length);}

运行后果如下：byte[]数组长度为:40[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]压缩后的byte[]数组长度为:17

八、将新字符解码转为原字符串

咱们曾经将"i like like like java do you like a java"包含空格在内的四十个字符

压缩成[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]只有十七位的新字符。

那么如果咱们将这串新字符发给对方

对方如何解码成"i like like like java do you like a java"呢？

[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]是怎么来的？

将长度为133的编码串 % 8 再进行补码->反码->原码

那么咱们当初获取到新字符后须要应用逆向思维获取原补码

咱们能够应用Integer.toBinaryString()办法将byte转成二进制

/** *将一个byte转成-个二进制的字符串  * @param b * @return */private static String byteToBitString(byte b) {    //应用变量保留b     int temp = b;//将b转成int     String str = Integer.toBinaryString(temp);     return str;}

咱们应用 -1 进行测试这个办法看看

//测试一把byteToBitString办法System.out.println(byteToBitString((byte)-1));运行后果如下：str=11111111111111111111111111111111

很遗憾，咱们发现返回的是int 的32位补码。留神是：补码

按理说咱们应该是从133 % 8获取的新字符，当初应该也是转为8位的补码，而不是32位

/** *将一个byte转成-个二进制的字符串 * @param b * @return */private static String byteToBitString(byte b) {    //应用变量保留b int temp = b;//将b转成int String str = Integer.toBinaryString(temp); return str.substring(str.length() -8);}

那么当初就能够了吗？其实并不然还有一个补位的问题！比如说我当初输出 1

当是负数的时候，以后stu =1 则须要补位、否则是无奈实现截取操作的

/** *将一个byte转成-个二进制的字符串 * @param b * @return */private static String byteToBitString(byte b) {     //应用变量保留b     int temp = b;//将b转成int     //如果是负数咱们还存在补高位     temp |= 256;     String str = Integer.toBinaryString(temp);     return str.substring(str.length() -8);}运行后果如下：00000001

？？？

可能会有小伙伴会问到 temp |=256 是什么意思？？？为什么要|=256

这就波及到知识点二进制的运算符了，两个二进制对应位为0时该位为0，否则为1

这样咱们输出十进制：1 的时候，能力进行截取长度，否则不满足

/** *将一个byte转成-个二进制的字符串 * @param flag 标记是否须要补高位、如果是最初一个字节则无需补高位 * @param b 传入的byte * @return 返回b对应的二进制串（按补码返回） */ private static String byteToBitString(boolean flag,byte b) {     //应用变量保留b     int temp = b;//将b转成int     if(flag){        //如果是负数咱们还存在补高位        temp |= 256;     }     String str = Integer.toBinaryString(temp);     if(flag){       return str.substring(str.length() -8);     }else{       return str;     }}

依据八位为一组的思路，就会发现最初一个byte字节就无需补高位

将新字符解码转为原字符串思路剖析

找到记录原字符byte转为自定义哈夫曼编码Map
应用StringBuilder记录新字符组的补码
依据自定义哈夫曼编码Map反获取(编码:字符)组成新map
依据StringBuilder匹配新map获取对应字符

第一步：应用StringBuilder记录新字符组的补码

/** *  @param huffmanCodes 哈夫曼编码表map * @param huffmanBytes 哈夫曼失去的字节数组 * @return就是原来的字符串对应的数组 */private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){    //1.应用StringBuilder记录新字符组的补码    StringBuilder stringBuilder =new StringBuilder();    //循环记录    for (int i=0;i<huffmanBytes.length;i++){         byte b = huffmanBytes[i];         //最初一个字符无需补位         boolean flag = (i == huffmanBytes.length -1?true:false);         stringBuilder.append(byteToBitString(!flag,b));     }     System.out.println("新字符组的补码串:"+stringBuilder.toString());     System.out.println("新字符组的补码串长度:"+stringBuilder.length());     return null; }

public static void main(String[] args) {    /失去`"i like like like java do you like a java"`对应byte[]数组    String content = "i like like like java do you like a java";    byte[] contentBytes = content.getBytes();    System.out.println("原byte[]数组长度为:"+contentBytes.length);    byte[] huffmanCodeBy =haffmanZip(contentBytes);    System.out.println("n开始进行哈夫曼编码压缩==============================n");    System.out.println("压缩后的新字符数组:"+Arrays.toString(huffmanCodeBy));    System.out.println("压缩后的byte[]数组长度为:"+huffmanCodeBy.length);    decode(huffmanCodes,huffmanCodeBy);}运行后果如下：原byte[]数组长度为:40原字符数组通过自定义编码后的编码串:1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100原字符数组通过自定义编码后的编码串长度:133开始进行哈夫曼编码压缩==============================压缩后的新字符数组:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]压缩后的byte[]数组长度为:17新字符组的补码串:1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100新字符组的补码串长度:133

第二步：找到记录原字符byte转为自定义哈夫曼编码Map、依据自定义哈夫曼编码Map反获取(编码:字符)组成新map

/** * * @param huffmanCodes 哈夫曼编码表map * @param huffmanBytes 哈夫曼失去的字节数组 * @return就是原来的字符串对应的数组 */private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){     //1.应用StringBuilder记录新字符组的补码     StringBuilder stringBuilder =new StringBuilder();     //循环记录     for (int i=0;i<huffmanBytes.length;i++){        byte b = huffmanBytes[i];        //最初一个字符无需补位        boolean flag = (i == huffmanBytes.length -1?true:false);        stringBuilder.append(byteToBitString(!flag,b));     }     //找到记录原字符byte转为自定义哈夫曼编码Map、依据自定义哈夫曼编码Map反获取原字符     Map<String,Byte> map =new HashMap<String, Byte>();     for(Map.Entry<Byte,String> item:huffmanCodes.entrySet()){          map.put(item.getValue(),item.getKey());     }     System.out.println("依据自定义哈夫曼编码Map反获取(编码:字符)组成新map = "+map);     return null; } 运行后果如下：依据自定义哈夫曼编码Map反获取(编码:字符)组成新map = {000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106}

第三步：依据StringBuilder匹配新map获取对应字符

/** * * @param huffmanCodes 哈夫曼编码表map * @param huffmanBytes 哈夫曼失去的字节数组 * @return就是原来的字符串对应的数组 */private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){    //1.应用StringBuilder记录新字符组的补码     StringBuilder stringBuilder =new StringBuilder();     //循环记录     for (int i=0;i<huffmanBytes.length;i++){        byte b = huffmanBytes[i];        //最初一个字符无需补位        boolean flag = (i == huffmanBytes.length -1?true:false);        stringBuilder.append(byteToBitString(!flag,b));     }        //找到记录原字符byte转为自定义哈夫曼编码Map、依据自定义哈夫曼编码Map反获取原字符     Map<String,Byte> map =new HashMap<String, Byte>();     for(Map.Entry<Byte,String> item:huffmanCodes.entrySet()){         map.put(item.getValue(),item.getKey());     }        //依据StringBuilder匹配新map获取对应字符     List<Byte> list =new ArrayList<>();     for (int j=0;j<stringBuilder.length();){            int count = 1;        boolean flag = true;        Byte b = null;        while(flag){          String key =stringBuilder.substring(j,j+count);          b = map.get(key);          if(b == null){               count++;          }else{               flag = false;          }        }        list.add(b);        j +=count;     }      //当for循环完结后，list就寄存了字符串"i like like like java do you like a java"的所有字符     //把汇合里的数据放入byte[]中返回 byte[] b = new byte[list.size()];     for (int k =0;k<b.length; k++){            b[k]=list.get(k);     }     return b;}

public static void main(String[] args) {    /失去`"i like like like java do you like a java"`对应byte[]数组    String content = "i like like like java do you like a java";    byte[] contentBytes = content.getBytes();    System.out.println("原byte[]数组长度为:"+contentBytes.length);    byte[] huffmanCodeBy =haffmanZip(contentBytes);    System.out.println("n开始进行哈夫曼编码压缩==============================n");    System.out.println("压缩后的新字符数组:"+Arrays.toString(huffmanCodeBy));    System.out.println("压缩后的byte[]数组长度为:"+huffmanCodeBy.length);    byte[] source = decode(huffmanCodes,huffmanCodeBy);    System.out.println("新字符数组通过依据新map获取对应字符："+new String(source));}运行后果如下：依据自定义哈夫曼编码Map反获取(编码:字符)组成新map = {000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106}新字符数组通过依据新map获取对应字符：i like like like java do you like a java

九、最佳实际文件压缩与解压

咱们将这个图片文件，进行压缩实际看看

思路：读取文件-->失去哈夫曼编码表-->实现压缩

/** *@paramsrcFile 心愿压缩文件的全门路 *@param dstFile 压综后将文件放到哪个目录*/public static void zipFile(String srcFile, String dstFile) {     //创立输入流     OutputStream os = null;     //对象输入流     ObjectOutputStream oos;     //创立文件的输出流     FileInputStream is = null;     try {            //创立文件的输出流         is = new FileInputStream(srcFile);         //创立一个和源文 件大小一样的byte[ ]         byte[] b = new byte[is.available()];         //读取文件         is.read(b);         //间接对文件压缩         byte[] bytes = haffmanZip(b);         //创立文件的输入流，寄存压缩文件         os = new FileOutputStream(dstFile);         //创立一个和文件流关联的ObjectOutputStream;         oos = new ObjectOutputStream(os);         //以对象流的方写入哈夫曼编码，为了不便复原         oos.writeObject(huffmanCodes);     } catch (Exception e) {            System.out.println(e.getMessage());     } finally {         try {            is.close();            oos.close();            os.close();         }catch (Exception e) {            System.out.println(e.getMessage());         }    }}

public static void main(String[] args) {    //测试压编文件    String srcFile = "d://src. bmp";    String dstFile = "d://dst.zip";    zipFile(srcFile, dstFile);    System. out . println("压编文件ok~~");}

会呈现无奈关上并解压的形式，为什么呢？

因为咱们自定义属于本人的的压缩形式，所以解压也要用咱们本人的形式去解压

源文件大小：598kb
压缩后的文件大小：76kb

那么接下来咱们编写本人的解压形式把

思路：读取压缩文件(数据和哈弗曼编码表)-->实现解压

//编写一个办法，实现对压缩文件的解压/** * @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);         //创立一个和文件流关联的ObjectOutputStream;         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);         //将复原的原byte数组写入文件         os = new FileOutputStream(dstFile);         os.write(bytes);     } catch (Exception e) {            System.out.println(e.getMessage());     } finally {         try {            os.close();            ois.close();            is.close();         }catch (Exception e) {            System.out.println(e.getMessage());         }    }}

public static void main(String[] args) {        //测试解压文件    String zipFile = "d://dst. zip";    String dstFile = "d://src2. bmp";    unZipFile(zipFile, dstFile) ;}