总目录：地址如下看总纲
前置知识：关于原码补码反码
1、赫夫曼编码介绍
1、赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法
2、赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
3、赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间，重复次数越多，压缩率越高
4、赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码
2、 通讯领域中信息处理方式
1、方式一：定长处理
- i like like like java do you like a java // 共40个字符(包括空格)
- 105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97
//对应Ascii码
- 01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001
//对应的二进制【总的长度是 359 (包括空格)】
2、方式二：变长处理
- i like like like java do you like a java // 共40个字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9 // 各个字符对应的个数
- 0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d// 特殊规定编码
- 说明：按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如 空格出现了9 次， 编码为0 ,其它依次类推
按照上面给各个字符规定的编码，则我们在传输 "i like like like java do you like a java" 数据时，特殊编码就是
image.png
- 字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码， 即不能匹配到重复的编码
3、方式三：赫夫曼编码
- i like like like java do you like a java // 共40个字符(包括空格)
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 空格:9 // 各个字符对应的个数
- 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
- 构成赫夫曼树的步骤：
1、从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
2、取出根节点权值最小的两颗二叉树
3、组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
4、再将这颗新的二叉树，以根节点的权值大小 再次排序
5、不断重复以上四个步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树
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- 按照上面的赫夫曼编码，字符串 "i like like like java do you like a java" 字符串对应的编码为 (无损压缩)：
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110（长度：133）- 小结：
1.原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
2.此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性- 图：
image.png
5、注意事项：
这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是wpl 是一样的，都是最小的, 比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:
image.png
3、赫夫曼编码实现数据压缩和解压缩代码：参考步骤走
/**
* title: 赫夫曼编码(字符串数据压缩与解压)
* @author 阿K
* 2021年1月10日 下午9:49:33
*/
public class HuffmanCode {
public static void main(String[] args) {
/* 第一大步骤测试 ：步骤一 至三，主要实现 通过字符串的字节数组构建赫夫曼数*/
String content = "i like like like java do you like a java";
byte[] contentBytes = content.getBytes();
List<Node> nodes = getNodes(contentBytes);
// System.out.println("有效节点个数为：" + nodes.size());// 12 个有效节点
Node root = createHuffmanTree(nodes);
// System.out.println("前序遍历当前赫夫曼树：");
perOrder(root);
/* 第二大步测试 ：步骤四 ，主要实现 通过赫夫曼树生成对应的赫夫曼编码表 */
Map<Byte,String> codes = getCodes(root);
System.out.println(codes);
/* 第三大步测试 ：步骤五 主要实现，压缩字符串，生成赫夫曼规则的字节数组 */
// System.out.println(Arrays.toString(zip(contentBytes, huffmanCodes)));;
byte[] huffmanBytes = huffmanZip(contentBytes);
System.out.println(Arrays.toString(huffmanBytes));
/* 第四大步测试 ：步骤六至 七 ，主要实现，解压缩字符串，逆向操作 */
byte[] sourceStr = decode(huffmanCodes, huffmanBytes);
System.out.println(new String(sourceStr));
}
// 步骤七内容-----------------------------------------------------
// 字符串解压思路：
// 1.将huffmanCodeBytes [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
//先转成赫夫曼编码对应的二进制的字符串 "1010100010111..."
// 2.再将 此二进制字符串 对照赫夫曼编码表(反向) 转成 最初字符串的二进制字节数组
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes) {
//1. 先得到 huffmanBytes 对应的 二进制的字符串 ， 形式 1010100010111...
StringBuilder stringBuilder = new StringBuilder();
// 将 byte 数组转成 二进制字符串
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
// 判断是否为最后一个字节
boolean flag = ( i == huffmanBytes.length-1);
stringBuilder.append(byteToBitString(!flag, b));
}
// 2.把字符串按照指定的赫夫曼编码进行解码
// 把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
Map<String,Byte> map = new HashMap<>();
for(Map.Entry<Byte, String> entry:huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
// 3.创建用于存放 byte的集合
List<Byte> list = new ArrayList<>();
// 其中 i 在这里充当索引，用于扫描 stringBuilder
for (int i = 0; i < stringBuilder.length();) {
int count = 1;// 微型计算器，用于记录内部的 while循环,与 i相辅相成
boolean flag = true;// 用于控制 while
Byte b = null;// 记录要存放的字节
while(flag) {
// 1010100010111...
// 递增的取出 key 1 ,没有再移动 10 ，101 以此类推
String key = stringBuilder.substring(i,i+count);// i不动，count移动，指定匹配到一个字符(0或1)
b = map.get(key);
if(b == null) {
// 说明没有匹配到
count++;
}else {
// 匹配到
flag = false;
}
}
list.add(b);
i += count; // i 直接移动到 count(若 while 中 符合条件的次数 count 达到则 退出，次数 i也没必要移动，此处 i才是辅助)
}
// 4.以上循环结束后，说明已经解码结束
byte[] bytes = new byte[list.size()];
for (int i = 0; i < list.size(); i++) {
bytes[i] = list.get(i);
}
return bytes;
}
// 步骤六内容-----------------------------------------------------
public static String byteToBitString(boolean flag,byte b) {
// 将 b 转成 int
int temp = b;
// 若是正数，则需要补高位,转换需要 int 类型
if(flag) {
// 按位与 256 1 0000 0000 | 0000 0001 => 1 0000 0001
temp |=256;
}
// 返回的是 temp 对应的二进制补码
String str = Integer.toBinaryString(temp);
if(flag) {
return str.substring(str.length()-8);
}
// 若不是正数直接返回
return str;
}
// 封装以下步骤(1-5)所有关于压缩字符串的代码
public static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
// 根据 nodes 创建的赫夫曼树
Node huffmanTreeRoot = createHuffmanTree(nodes);
// 对应的赫夫曼编码(根据 赫夫曼树)
Map<Byte,String> huffmanCodes = getCodes(huffmanTreeRoot);
// 根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
return zip(bytes,huffmanCodes);
}
// 步骤五内容-----------------------------------------------------
/**
* 将 原始数据(字符串)，通过赫夫曼编码表，压缩 成新的字节数组返回
*
* eg：huffmanCodeBytes[0] = 10101000(补码) => byte [推导 10101000=> 10101000 - 1 => 10100111(反码)=> 11011000= -88 ]
* @param bytes 原始数据(字符串)对用的字节数组
* @param huffmanCodes 原始数据生成的赫夫曼编码表
* @return 返回压缩处理后的字节数组
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes) {
// 用于记录压缩后的新字节数据(既 通过huffmanCodes 将 bytes 转成字符串)
StringBuilder stringBuilder = new StringBuilder();
for(Byte b:bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//
// System.out.println(stringBuilder.toString());
// 计算 huffmanCodeBytes 的长度
// 以下推导出的公式 int len = (stringBuilder.length() + 7)/8
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;// 记录是第几个 byte
for (int i = 0; i < stringBuilder.length(); i+=8) {// 因为每位 8 位对应一个 byte，所有步长 为8
String strByte;
if(i+8>stringBuilder.length()) {// 不够8位( 若 i 是 1到7,说明它不够)
strByte = stringBuilder.substring(i);
}else {
strByte = stringBuilder.substring(i,i+8);
}
// 将 strByte 转成 一个byte，放入到huffmanCodeBytes
// 二进制的补码 ---》 反码 ---》 原码
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
// 步骤五内容-----------------------------------------------------
// 步骤四内容-----------------------------------------------------
// 步骤四：生成赫夫曼树对应的赫夫曼编码
// 思路：1、将赫夫曼编码表存放到 Map<Byte,String>
// eg：生成的赫夫曼编码表{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
static Map<Byte,String> huffmanCodes = new HashMap<>();
// 思路：2、在生成赫夫曼编码时，需要记录路径(拼接路径),定义StringBuilder,用于存储某叶子节点路径
static StringBuilder huffmanRoute = new StringBuilder();
/**
* 根据传入的 node 节点的所有叶子节点的赫夫曼编码得到，并存入 huffmanCodes 哈希表中
* @param node 获取编码表的节点
* @param code 路径：规定 左子节点为 0，右子节点为 1
* @param huffmanRoute 用于拼接的路径
*/
private static void getCodes(Node node,String code,StringBuilder huffmanRoute) {
// 辅助、递归的时候不会改变原始路径拼接
StringBuilder stringBuilder = new StringBuilder(huffmanRoute);
// 将 code 拼接到 stringBuilder
stringBuilder.append(code);
if(node!=null) {// 若为节点null，不处理
// 判断当前节点，是叶子节点 还是非叶子节点
if(node.data==null) {// 非叶子节点
// 向左递归
getCodes(node.left, "0", stringBuilder);
// 向右递归
getCodes(node.right, "1", stringBuilder);
}
else {// 说明是一个叶子节点
// 说明已经找到某个叶子节点的最后
huffmanCodes.put(node.data, stringBuilder.toString());
}
}
}
// 重载 getCodes ，方便调用
public static Map<Byte, String> getCodes(Node root) {
if(root==null) {
return null;
}
// 处理 root 的左子树
getCodes(root.left, "0", huffmanRoute);
// 处理 root 的右子树
getCodes(root.right, "1", huffmanRoute);
return huffmanCodes;
}
// 步骤四内容-----------------------------------------------------
// 步骤三：通过 节点集合，构建出赫夫曼树
public static Node createHuffmanTree(List<Node> nodes) {
// 循环四步骤，知道最终只有一个 root节点
while (nodes.size() > 1) {
// 从小到大排序
Collections.sort(nodes);
// 取出第一颗最小的二叉树（若是大到小，取第一颗最大）
Node leftNode = nodes.get(0);
// 取出第二颗最小的二叉树（若是大到小，取第二颗最大）
Node rightNode = nodes.get(1);
// 构建一颗新的二叉树，为以上两树的根节点(此树没有data,只有权值)
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
// 将处理完毕后的两颗二叉树，从 nodes 集合中删除
// 并让 新构建出的二叉树，加入到 nodes 集合中，---循环中。。。
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
return nodes.get(0);
}
// 步骤二：将 字节数组 byte[] 转为 节点集合 List，用于后面构建赫夫曼树
public static List<Node> getNodes(byte[] bytes) {
// 创建一个要返回的节点集合
List<Node> nodes = new ArrayList<Node>();
// 遍历 bytes，统计每一个字节出现的次数,用 map<Byte,Integer>接收
// key 为 Ascll 码值，value 为出现的次数
Map<Byte, Integer> counts = new HashMap<>();
for (byte b : bytes) {
Integer count = counts.get(b);
if (count == null) {
// 当前是第一次进来，还没有这个数的次数（初始化）
counts.put(b, 1);
} else {
counts.put(b, count + 1);
}
}
// 将每个键值对，以 Node 节点对象的方式存储 到List集合中
for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
// 返回
return nodes;
}
// 调用节点自身的前序遍历
public static void perOrder(Node root) {
if (root == null) {
System.out.println("抱歉，我TM无法遍历没有内容的根节点");
} else {
root.perOrder();
}
}
}
// 步骤一：创建Node节点(数据，权值，排序)
class Node implements Comparable<Node> {
protected Byte data; // 存放数据(字符)本身，比如'a' => 97 ' ' => 32
protected int weight; // 权值, 表示字符出现的次数
protected Node left; // 左子树(默认null)
protected Node right; // 右子树(默认null)
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
public Node(Byte data, int weight) {
super();
this.data = data;
this.weight = weight;
}
@Override
public String toString() {
return "Node [data=" + data + ", weight=" + weight + "]";
}
// 前序遍历
public void perOrder() {
System.out.println(this);
if (this.left != null) {
this.left.perOrder();
}
if (this.right != null) {
this.right.perOrder();
}
}
}
4、赫夫曼编码实现文件压缩与解压
package com.kk.datastructure.tree.availabletree;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Map;
//import static com.kk.datastructure.tree.availabletree.HuffmanCode;
/**
* title: 赫夫曼实现文件压缩，解压
* @author 阿K
* 2021年1月16日 下午9:05:10
*/
public class HuffmanFileZipDemp {
public static void main(String[] args) {
String s1 = "J:\\caolaoshi.avi";
String s2 = "J:\\caolaoshi.zip";
String s3 = "J:\\caolaoshi(1).avi";
zipFile(s1, s2);
unzipFile(s2,s3);
}
/**
* 文件的解压
* @param unzipFile
* @param dstFile
*/
public static void unzipFile(String unzipFile,String dstFile) {
// 定义流
FileOutputStream os = null;
FileInputStream is = null;
ObjectInputStream ois = null;
try {
// 初始化
is = new FileInputStream(unzipFile);
// 初始化对象输入流 --- 用于读入 赫夫曼表和源文件数组
ois = new ObjectInputStream(is);
byte[] huffmanBytes = (byte[])ois.readObject();
Map<Byte,String> huffmanCodes = (Map<Byte,String>)ois.readObject();
// 解码
byte[] bytes = HuffmanCode.decode(huffmanCodes, huffmanBytes);
// 将bytes 数组写入到目标文件
os = new FileOutputStream(dstFile);
os.write(bytes);
} catch (Exception e) {
e.printStackTrace();
}finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e2) {
System.out.println(e2.getMessage());
}
}
}
/**
* 文件压缩方法
* @param srcFile 准备压缩的源文件路径
* @param dstFile 压缩后输出的文件李静
*/
public static void zipFile(String srcFile, String dstFile) {
// 定义流，这里核心使用的是对象流
FileInputStream is = null;
FileOutputStream os = null;
ObjectOutputStream oos = null;
try {
// 初始化流
is = new FileInputStream(srcFile);
// 创建一个和源文件大小一致的 byte数组
byte[] b = new byte[is.available()];
// 将文件读取到字节数组中
is.read(b);
// 对源文件字节数组进行压缩,得到赫夫曼编码压缩文件
byte[] huffmanBytes = HuffmanCode.huffmanZip(b);
// 初始化输出流，用于输出到指定路径
os = new FileOutputStream(dstFile);
// 创建输出的对象流，方便后续解压，毕竟 byte 数组 就是一个对象
oos = new ObjectOutputStream(os);
oos.writeObject(huffmanBytes);
// 注意：编码表也要输入，后续要对照这个进行解压
oos.writeObject(HuffmanCode.huffmanCodes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
oos.close();
os.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
}
5、关于文件压缩性能须知
1、如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件
2、赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件)
3、如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显
6、无聊的测试
image.png
网友评论