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

52次阅读

共计 21870 个字符，预计需要花费 55 分钟才能阅读完成。

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

在线转码工具: 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[]数组长度为:40
stringBuilder=1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
stringBuilder 的长度 =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) ;
}

正文完
java
发表至： java
2020-09-22
 0
关于java:线程管理
Spring-FORM-标签库
SpringBoot2X版本war包
关于java:Java零基础系列教程10Java抽象与封装