哈夫曼编码——Huffman Coding——数据文件压缩——最佳编码
基本介绍
- 赫夫曼编码也翻译为哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法。
- 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
- 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在20%～90%之间。哈夫曼编码进行压缩时主要针对有大量重复数据的文件，重复数据越多，压缩率越高。
- 赫夫曼码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，称之为最佳编码。
通信领域中信息的处理方式
- 定长编码
- 变长编码
- 赫夫曼编码
定长编码
就是直接拿ASCII码对应的二进制编码来传递信息，就是定长编码。
定长编码的缺点是数据量大，优点是数据完整。
前缀编码
字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码， 即不能匹配到重复的编码。
哈夫曼编码就属于前缀编码。
变长编码
变长编码的原则是出现次数越多的，则编码越小。其优点是数据量小，节约空间，但缺点是在解码时因为不符合前缀编码原则会有二意性。这种就需要约定一个解码的分隔码来判断到哪里进行分隔。
赫夫曼编码——无损压缩
哈夫曼编码属于前缀编码，字符的编码都不能是其他字符编码的前缀。哈夫曼编码是无损压缩，也就是原来是什么样解压完就是什么样，不会造成精度或者清晰度什么的问题。
注意：哈夫曼编码根据排序的方法不同，对应的哈夫曼编码也不完全一样，因为相同权值的字符会因为排序导致位置的不同，而位置的不同对应的二进制编码就会不一样，但是wpl是一样的，都是最小的。相同的值最好放在最右边，这样平均编码长度的方差最小。
PS:方差公式是一个数学公式，是数学统计学中的重要公式，应用于生活中各种事情，方差越小，代表这组数据越稳定，方差越大，代表这组数据越不稳定
哈夫曼编码思路分析
哈夫曼编码每次生产新的二叉树权值总数排在相同权值的最后一个对应的二叉树：
赫夫曼编码压缩文件注意事项
- 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件 [举例压一个 .ppt]
- 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml文件]
- 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显.
压缩解压文件代码示例
//节点
public class HuffmanNode implements Comparable<HuffmanNode> {
//存放数据本身，比如'a'=97
private Byte value;
//权值，表示字符出现的次数
private int weight;
private HuffmanNode left;
private HuffmanNode right;
public HuffmanNode(Byte value, int weight) {
this.value = value;
this.weight = weight;
}
public Byte getValue() {
return value;
}
public void setValue(Byte value) {
this.value = value;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public HuffmanNode getLeft() {
return left;
}
public void setLeft(HuffmanNode left) {
this.left = left;
}
public HuffmanNode getRight() {
return right;
}
public void setRight(HuffmanNode right) {
this.right = right;
}
@Override
public int compareTo(HuffmanNode o) {
//排序比较用
return this.weight-o.weight;
}
@Override
public String toString() {
return "HuffmanNode{" +
"value=" + value +
", weight=" + weight +
'}';
}
//前序遍历
public void preOrder(){
if (this == null) {
System.out.println("没有数据存在！");
return;
}
System.out.println(this);
if (this.getLeft() != null){
this.getLeft().preOrder();
}
if (this.getRight()!=null){
this.getRight().preOrder();
}
}
}
//哈夫曼编码压缩解压
public class HuffmanCode {
public static Map<Byte, String> huffmanCodes = new HashMap<>();
public static void main(String[] args) {
zipFile("D:\\111.txt", "D:\\1.zip");
unZipFile("D:\\1.zip", "D:\\恢复1.txt");
// zipFile("D:\\弹钢琴.mp4", "D:\\pic.zip");
// unZipFile("D:\\pic.zip", "D:\\pic.mp4");
}
/**
* 压缩文件
*
* @param srcFile 待压缩文件位置
* @param destFile 文件压缩完存放的位置
*/
public static void zipFile(String srcFile, String destFile) {
FileInputStream is = null;
ObjectOutputStream os = null;
try {
is = new FileInputStream(srcFile);
//os.available()返回文件的大小
byte[] bytes = new byte[is.available()];
is.read(bytes);
byte[] zipBytes = huffmanZip(bytes);
//已对象流的形式写入，方便恢复源文件时使用
os = new ObjectOutputStream(new FileOutputStream(destFile));
os.writeObject(zipBytes);
//写入哈夫曼编码表
os.writeObject(huffmanCodes);
System.out.println("压缩文件成功！");
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
os.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 解压文件
*
* @param zipFile 待解压的文件
* @param destFile 文件解压完存放的位置
*/
public static void unZipFile(String zipFile, String destFile) {
ObjectInputStream is = null;
FileOutputStream os = null;
try {
is = new ObjectInputStream(new FileInputStream(zipFile));
//读取文件字节数组
byte[] zipBytes = (byte[]) is.readObject();
//读取哈夫曼编码表
Map<Byte, String> codes = (Map<Byte, String>) is.readObject();
byte[] unZioBytes = unZip(zipBytes, codes);
os = new FileOutputStream(destFile);
os.write(unZioBytes);
System.out.println("解压文件成功！");
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
os.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
/**
* 测试字符串压缩解压缩
*/
public static void testStrZipUnZip() {
String target = "i like like like java do you like a java";
byte[] targetBytes = target.getBytes();
//原始数组长度
System.out.println("原始数组长度:" + targetBytes.length);//原始数组长度:40
HuffmanNode root = HuffmanTree.createHuffmanTree(targetBytes);
//因为根节点是没有code值的，所有传入空字符串
// createHuffmanCode(root,"",new StringBuilder());
createHuffmanCode(root);
System.out.println("哈夫曼编码表：");
System.out.println(huffmanCodes);
//哈夫曼编码表：
//{32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
// String zipStr = zip(targetBytes, huffmanCodes);
// System.out.println(zipStr);
//1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
byte[] zip = zip(targetBytes, huffmanCodes);
System.out.println("压缩后的byte数组:" + Arrays.toString(zip));
//[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
huffmanZip(targetBytes);
System.out.println("解压字符串：" + new String(unZip(zip, huffmanCodes)));
/**
* 原始数组长度:40
* 哈夫曼编码表：
* {32=01, 97=100, 100=11000, 117=11001, 101=1110, 118=11011, 105=101, 121=11010, 106=0010, 107=1111, 108=000, 111=0011}
* 压缩后zipBytes数组长度：17
* 压缩后的byte数组:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
* 压缩后zipBytes数组长度：17
* 压缩数据成功！
* 还原后的压缩二进制字符串：1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
* 解码哈夫曼编码表:{000=108, 01=32, 100=97, 101=105, 11010=121, 0011=111, 1111=107, 11001=117, 1110=101, 11000=100, 11011=118, 0010=106}
* 解压字符串：i like like like java do you like a java
*/
}
/**
* 解压方法
*
* @param zipBytes 带解压字节数组
* @param huffmanCodes 哈夫曼编码表
* @return 解压后的字节数组
*/
public static byte[] unZip(byte[] zipBytes, Map<Byte, String> huffmanCodes) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < zipBytes.length; i++) {
if (i == zipBytes.length - 1) {
String temp = byteToBitString(false, zipBytes[i]);
sb.append(temp);
} else {
String temp = byteToBitString(true, zipBytes[i]);
sb.append(temp);
}
}
// System.out.println("还原后的压缩二进制字符串：" + sb.toString());
//获取解码哈夫曼编码表
Map<String, Byte> unZipHuffmanCodes = new HashMap<>(huffmanCodes.size());
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
unZipHuffmanCodes.put(entry.getValue(), entry.getKey());
}
// System.out.println("解码哈夫曼编码表:" + unZipHuffmanCodes);
int i = 0;//当前字符串匹配的位置，从0匹配到字符串最后一位
//因为我们并不知道解码后的字节数组的长度，所以先用ArrayList存储起来
ArrayList<Byte> list = new ArrayList<>();
String temp = "";
int len = 1;//用于移动匹配到能匹配的值，再把i移动到这个位置
while (i < sb.length()) {
temp = sb.substring(i, i + len);
if (unZipHuffmanCodes.containsKey(temp)) {
list.add(unZipHuffmanCodes.get(temp));
temp = "";
i = i + len;
len = 1;
} else{
//不加else则len往下走会变成2导致每次都从2位开始截取
len += 1;
}
}
byte[] originBytes = new byte[list.size()];
int index = 0;
for (Byte aByte : list) {
originBytes[index] = aByte;
index++;
}
// System.out.println(new String(originBytes));
//i like like like java do you like a java
return originBytes;
}
/**
* 将一个byte字节转成一个8位的二进制字符串
*
* @param b 待处理的byte字节
* @param flag 标记是否需要高位补0，true 需要，false 不需要 ,也就是说flag是给最后一个字节用的，不补高位
* @return
*/
private static String byteToBitString(boolean flag, byte b) {
int temp = b;
if (flag) {
temp |= 256;//按位或 1 0000 0000 | 0000 0011 = 1 0000 0011
}
//这入参b要求是int，会自动把byte封装为int类型进行运算
String str = Integer.toBinaryString(temp);
//正数需要补位到8位，负数需要截取最后8位，因为正数高位不返回，负数返回int类型32位的负数，所以只截取最后8位
//flag为false表示最后一个数
if (flag) {
return str.substring(str.length() - 8);
} else {
//最后一位截取掉补1的情况
str = str.replaceFirst("1","");
}
return str;
}
/**
* 封装哈夫曼压缩方法
*
* @param bytes 原始byte[]数组
* @return 压缩后的byte[]数组
*/
public static byte[] huffmanZip(byte[] bytes) {
//创建哈夫曼树
HuffmanNode root = HuffmanTree.createHuffmanTree(bytes);
//获取哈夫曼编码
createHuffmanCode(root);
//根据哈夫曼编码生成对应的压缩字节byte[]数组
byte[] zipBytes = zip(bytes, huffmanCodes);
System.out.println("压缩数据成功！");
return zipBytes;
}
/**
* 根据哈夫曼编码表压缩原始数据
*
* @param bytes 原始数据对应的byte[]数组
* @param huffmanCodes 哈夫曼编码表
* @return 压缩后的byte[]数组，8位对应一个byte，放入到压缩后的byte[]数组中
* 注意：byte[]数组中存放的数据是二进制数据的补码
* 补码 = 原码取反 +1 原码 = 补码-1 再取反
* 这里要注意是因为我们直接存放的是二进制的值，我们把这个值直接存放进去，而在计算机中byte[]中存放的是补码，也就是说我们存放的其实是二进制的补码值，
* 而当我们要打印出来查看的时候就要注意打印出来的时候计算机会把补码的值转化为原码打印出来给我们看，也就是说打印出来的是我们存放的数据的补码对应的原码值
*/
public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
StringBuilder sb = new StringBuilder();
//根据哈夫曼编码表将原始数组转化为压缩字符串
for (byte aByte : bytes) {
sb.append(huffmanCodes.get(aByte));
}
//(sb.length() + 7) / 8 是为了最后不足8位是要多加一个位置给剩余的位数，取巧的方法是+7再去除8
//初始化压缩后byte数组
byte[] zipBytes = new byte[(sb.length() + 7) / 8];
System.out.println("压缩后zipBytes数组长度：" + zipBytes.length);//压缩后zipBytes数组长度：17
//记录字符串sb遍历位置下标
int i = 0;
//存放截取的子字符串临时变量
String code = "";
//记录要填充的byte[]数组下标
int index = 0;
while (i < sb.length()) {
//每8位对应一个byte
if (i + 8 < sb.length()) {
//截取8位
code = sb.substring(i, i + 8);
} else {
code = sb.substring(i, sb.length());
//在最后一位数时往数据前面加1，放在0011这种数据在存入byte数组中丢失了0，这样解压出来就会导致角标越界
code = "1" + code;
// code = sb.substring(i);
}
//按二进制把字符串转为int类型，然后再强转为byte类型
zipBytes[index] = (byte) Integer.parseInt(code, 2);
index++;
i += 8;
code = "";
}
return zipBytes;
//
// return sb.toString();
}
/**
* 重载哈夫曼编码表生成方法
*
* @param root
* @return
*/
public static Map<Byte, String> createHuffmanCode(HuffmanNode root) {
if (root == null) {
System.out.println("哈夫曼树不存在");
return null;
}
StringBuilder sb = new StringBuilder();
//分别处理root节点的左右子树递归处理，不需要，直接调用原来的方法即可
createHuffmanCode(root, "", sb);
return huffmanCodes;
}
/**
* 生成哈夫曼树对应的哈夫曼编码表map，将传入的的node节点的所有叶子节点的哈夫曼编码得到保存在map中，
*
* @param node 传入的节点，默认传入是root节点
* @param code 路径 规定左节点路径为0，右节点路径为1
* @param sb 用于拼接路径
*/
public static void createHuffmanCode(HuffmanNode node, String code, StringBuilder sb) {
StringBuilder sb2 = new StringBuilder(sb);
sb2.append(code);
//不为空则表示是具体存在的字符（叶子节点），保存他的路径值
if (node.getValue() != null) {
huffmanCodes.put(node.getValue(), sb2.toString());
}
//非叶子节点继续遍历创建
if (node.getLeft() != null) {
createHuffmanCode(node.getLeft(), "0", sb2);
}
if (node.getRight() != null) {
createHuffmanCode(node.getRight(), "1", sb2);
}
}
}
扩展：原码、补码、反码的关系
1、机器数
一个数在计算机中的二进制表示形式, 叫做这个数的机器数。机器数是带符号的，在计算机用一个数的最高位存放符号, 正数为0, 负数为1.
比如，十进制中的数 +3 ，计算机字长为8位，转换成二进制就是00000011。如果是 -3 ，就是 10000011 。
那么，这里的 00000011 和 10000011 就是机器数。
2、真值
因为第一位是符号位，所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011，其最高位1代表负，其真正数值是 -3 而不是形式值131（10000011转换成十进制等于131）。所以，为区别起见，将带符号位的机器数对应的真正数值称为机器数的真值。
例：0000 0001的真值 = +000 0001 = +1，1000 0001的真值 = –000 0001 = –1
二. 原码, 反码, 补码的基础概念和计算方法.
补码用于方便计算机进行负数的计算，因为计算机不像人一样可以识别正负符号，为了运算规则简单，对加减运行统一为加法运算，不过加的是负数，如10+（-1）,这样就需要通过补码来解决。
在探求为何机器要使用补码之前, 让我们先了解原码, 反码和补码的概念.对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式.
1. 原码
原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:
[+1]原 = 0000 0001
[-1]原 = 1000 0001
第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:
[1111 1111 , 0111 1111]
即
[-127 , 127]
原码是人脑最容易理解和计算的表示方式.
2. 反码
反码的表示方法是:
正数的反码是其本身
负数的反码是在其原码的基础上, 符号位不变，其余各个位取反.
[+1] = [00000001]原 = [00000001]反
[-1] = [10000001]原 = [11111110]反
可见如果一个反码表示的是负数, 人脑无法直观的看出来它的数值. 通常要将其转换成原码再计算.
3. 补码
补码的表示方法是:
正数的补码就是其本身
负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)
[+1] = [00000001]原 = [00000001]反 = [00000001]补
[-1] = [10000001]原 = [11111110]反 = [11111111]补
对于负数, 补码表示方式也是人脑无法直观看出其数值的. 通常也需要转换成原码在计算其数值.
三. 为何要使用原码, 反码和补码
在开始深入学习前, 我的学习建议是先"死记硬背"上面的原码, 反码和补码的表示方式以及计算方法.
现在我们知道了计算机可以有三种编码方式表示一个数. 对于正数因为三种编码方式的结果都相同:
[+1] = [00000001]原 = [00000001]反 = [00000001]补
所以不需要过多解释. 但是对于负数:
[-1] = [10000001]原 = [11111110]反 = [11111111]补
可见原码, 反码和补码是完全不同的. 既然原码才是被人脑直接识别并用于计算表示方式, 为何还会有反码和补码呢?
首先, 因为人脑可以知道第一位是符号位, 在计算的时候我们会根据符号位, 选择对真值区域的加减. (真值的概念在本文最开头). 但是对于计算机, 加减乘数已经是最基础的运算, 要设计的尽量简单. 计算机辨别"符号位"显然会让计算机的基础电路设计变得十分复杂! 于是人们想出了将符号位也参与运算的方法. 我们知道, 根据运算法则减去一个正数等于加上一个负数, 即: 1-1 = 1 + (-1) = 0 , 所以机器可以只有加法而没有减法, 这样计算机运算的设计就更简单了.
于是人们开始探索 将符号位参与运算, 并且只保留加法的方法. 首先来看原码:
计算十进制的表达式: 1-1=0
1 - 1 = 1 + (-1) = [00000001]原 + [10000001]原 = [10000010]原 = -2
如果用原码表示, 让符号位也参与计算, 显然对于减法来说, 结果是不正确的.这也就是为何计算机内部不使用原码表示一个数.
为了解决原码做减法的问题, 出现了反码:
计算十进制的表达式: 1-1=0
1 - 1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原= [0000 0001]反 + [1111 1110]反 = [1111 1111]反 = [1000 0000]原 = -0
发现用反码计算减法, 结果的真值部分是正确的. 而唯一的问题其实就出现在"0"这个特殊的数值上. 虽然人们理解上+0和-0是一样的, 但是0带符号是没有任何意义的. 而且会有[0000 0000]原和[1000 0000]原两个编码表示0.
于是补码的出现, 解决了0的符号以及两个编码的问题:
1-1 = 1 + (-1) = [0000 0001]原 + [1000 0001]原 = [0000 0001]补 + [1111 1111]补 = [0000 0000]补=[0000 0000]原
这样0用[0000 0000]表示, 而以前出现问题的-0则不存在了.而且可以用[1000 0000]表示-128:
(-1) + (-127) = [1000 0001]原 + [1111 1111]原 = [1111 1111]补 + [1000 0001]补 = [1000 0000]补
-1-127的结果应该是-128, 在用补码运算的结果中, [1000 0000]补 就是-128. 但是注意因为实际上是使用以前的-0的补码来表示-128, 所以-128并没有原码和反码表示.(对-128的补码表示[1000 0000]补算出来的原码是[0000 0000]原, 这是不正确的)
使用补码, 不仅仅修复了0的符号以及存在两个编码的问题, 而且还能够多表示一个最低数. 这就是为什么8位二进制, 使用原码或反码表示的范围为[-127, +127], 而使用补码表示的范围为[-128, 127].
因为机器使用补码, 所以对于编程中常用到的32位int类型, 可以表示范围是: [-231, 231-1] 因为第一位表示的是符号位.而使用补码表示时又可以多保存一个最小值.
参考文献
[图形化数据结构](https://www.cs.usfca.edu/~galles/visualization/Algorithms
