哈夫曼算法
# 10.哈夫曼编码
# 什么是哈夫曼编码?
假设有一个字符串，其中包含了一些字符，每个字符出现的次数不同，也就是权重不同，所以可以根据哈夫曼树的特点，找到带权路径长度最短的二叉树，来达到无损压缩的目的。
参考： 哈夫曼树的构建 (opens new window) 、哈夫曼编码 (opens new window)
# 举例
定义一个字符：
String str = "I like to learn Java";1转为byte数组，也就是对应的ASCII码
byte[] bytes = str.getBytes();1用一个节点Node[data=ASCII码，weight=出现次数]，转化上面的byte数组，方便构建哈夫曼树；参考 Node.java
构建哈夫曼树
Node.java
import java.util.*; /** * 创建Node,存数据和权值 */ public class Node implements Comparable<Node> { /** * 存放数据(ASCII编码)，比如'a' => 97 ' ' => 32 */ Byte data; /** * 权值, 表示字符出现的次数 */ int weight; Node left; Node right; public Node(Byte data, int weight) { this.data = data; this.weight = weight; } @Override public int compareTo(Node o) { // 从小到大排序 return this.weight - o.weight; } public String toString() { return "Node [data = " + data + ", weight=" + weight + "]"; } //前序遍历 public void preOrder() { System.out.println(this); if (this.left != null) { this.left.preOrder(); } if (this.right != null) { this.right.preOrder(); } } /** * 计算byte出现次数，byte作为节点的date，次数作为节点的权重 * * @param bytes 接收字节数组 * @return 返回 List<Node> 节点列表 */ public static List<Node> bytesToNodes(byte[] bytes) { ArrayList<Node> nodes = new ArrayList<>(); //遍历 bytes , 统计 每一个byte出现的次数->map[key,value] Map<Byte, Integer> counts = new HashMap<>(); for (byte b : bytes) { counts.put(b, counts.getOrDefault(b, 0) + 1); } //转换为Node列表 for (Map.Entry<Byte, Integer> entry : counts.entrySet()) { nodes.add(new Node(entry.getKey(), entry.getValue())); } return nodes; } /** * 构建huffman树 * * @param nodes 节点列表 * @return huffman树 */ public static Node buildHuffmanTree(List<Node> nodes) { if (nodes == null) { return null; } 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.remove(leftNode); nodes.remove(rightNode); //将新的二叉树，加入到nodes nodes.add(parent); } //nodes 最后的结点，就是赫夫曼树的根结点 return nodes.get(0); } }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100获取哈夫曼编码表：key = ASCII码，value=哈夫曼编码（从根节点到每一个叶子节点的路径上，左分支记为0，右分支记为1，将这些0与1连起来即为叶子节点的哈夫曼编码）
/** * 哈夫曼编码表 * eg: "I like to learn Java" => {32=111, 97=101, 101=1101, 73=0010, 105=0011, 74=0100, 107=0101, 108=000, 110=0110, 111=0111, 114=1000, 116=1001, 118=1100} */ static Map<Byte, String> huffmanCodes = new HashMap<>(); /** * 将节点值转换为哈夫曼编码 * * @param root 节点 * @param code 哈夫曼编码 */ public static void huffmanCode(Node root, String code) { if (root.left == null && root.right == null) { if (root.data != null) { huffmanCodes.put(root.data, code); } return; } huffmanCode(root.left, code + "0"); huffmanCode(root.right, code + "1"); }1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23压缩：
实际就是将原先的ASCII码转成哈夫曼所表示的二进制数组（这个二进制数组长度比原先的ASCII表示的二进制数组长度短），再转为十进制的ASCII码保存。
解压：
将压缩后的数组与转为二进制，然后再与之前得到的哈夫曼表进行比较，得到原先的ASCII码。
HuffmanCode.java
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class HuffmanCode {
/**
* 哈夫曼编码表
* eg: "I like to learn Java" => {32=111, 97=101, 101=1101, 73=0010, 105=0011, 74=0100, 107=0101, 108=000, 110=0110, 111=0111, 114=1000, 116=1001, 118=1100}
*/
static Map<Byte, String> huffmanCodes = new HashMap<>();
/**
* 将节点值转换为哈夫曼编码
*
* @param root 节点
* @param code 哈夫曼编码
*/
public static void huffmanCode(Node root, String code) {
if (root.left == null && root.right == null) {
if (root.data != null) {
huffmanCodes.put(root.data, code);
}
return;
}
huffmanCode(root.left, code + "0");
huffmanCode(root.right, code + "1");
}
/**
* 哈夫曼压缩算法
*
* @param bytes 原始的字符串对应的字节数组
* @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
*/
public static byte[] huffmanZip(byte[] bytes) {
// 转化为权值ASCII 节点
List<Node> nodes = Node.bytesToNodes(bytes);
// 根据 nodes 创建的赫夫曼树
Node huffmanTreeRoot = Node.buildHuffmanTree(nodes);
// 得到赫夫曼编码表
huffmanCode(huffmanTreeRoot, "");
// 根据生成的赫夫曼编码表，压缩得到压缩后的赫夫曼编码字节数组
return zip(bytes, huffmanCodes);
}
/**
* 将原始的字节数组根据哈夫曼表进行压缩
*
* @param bytes 原始的字符串对应的 byte[]
* @param huffmanCodes 哈夫曼表
* @return 压缩后的byte[]
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//1.利用哈夫曼编码表将原始字节数组转成赫夫曼编码数组
// （实际就是将原先的ASCII码转成哈夫曼所表示的二进制数组（这个二进制数组长度比原先的长度短，所以就被压缩了））
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
// +7 是为了防止 字符串长度不是 8的倍数，导致最后一个byte不足8位
int len = (stringBuilder.length() + 7) / 8;
byte[] huffmanCodeBytes = new byte[len];
//2. 将赫夫曼编码字符串（0，1组成，每8位对应一个字节）转为int，再转成byte
int index = 0;
// 因为是每8位对应一个byte,所以步长 +8
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if (i + 8 > stringBuilder.length()) {//不够8位
strByte = stringBuilder.substring(i);
} else {
strByte = stringBuilder.substring(i, i + 8);
}
//将strByte 转成一个byte,放入到 huffmanCodeBytes
byte parseInt = (byte) Integer.parseInt(strByte, 2);
huffmanCodeBytes[index] = parseInt;//输入二进制的strByte转为十进制
index++;
}
return huffmanCodeBytes;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/**
* 将一个byte 转成一个二进制的字符串
*
* @param b 传入的 byte
* @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
* @return 是该b 对应的二进制的字符串，（注意是按补码返回）
*/
public static String byteToBitString(boolean flag, byte b) {
//使用变量保存 b
int temp = b; //将 b 转成 int
//如果是正数我们还存在补高位
if (flag) {
temp |= 256; //按位与 256 1 0000 0000 | 0000 0001 => 1 0000 0001
}
String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
if (flag) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
* 解码
*
* @param huffmanCodes 哈夫曼编码表 map
* @param huffmanBytes 哈夫曼编码得到的字节数组
* @return 就是原来的字符串对应的数组
*/
public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
//1. 先得到 哈夫曼编码表 对应的 二进制的字符串 ， 形式 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));
}
//把字符串安装指定的赫夫曼编码进行解码
//把赫夫曼编码表进行调换，因为反向查询 a->100 100->a
Map<String, Byte> map = new HashMap<String, Byte>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
List<Byte> list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length(); ) {
//指针，移动指针取一段字符串去匹配哈夫曼编码对应的ASCII
int pointer = 1;
while (true) {
int end = i + pointer;
// TODO: 按照目前压缩文件的写法最后一组是哈夫曼编码表，所以会有匹配不到的情况
if (end > stringBuilder.length()) {
break;
}
String key = stringBuilder.substring(i, end);
Byte b = map.get(key);
if (b != null) {
//匹配到
list.add(b);
break;
}
pointer++;
}
i += pointer;
}
//把list 中的数据放入到byte[] 并返回
byte[] result = new byte[list.size()];
for (int i = 0; i < result.length; i++) {
result[i] = list.get(i);
}
return result;
}
/**
* 解压文件
*
* @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);
//创建一个和 is关联的对象输入流
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);
//将bytes 数组写入到目标文件
os = new FileOutputStream(dstFile);
//写数据到 dstFile 文件
os.write(bytes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
/**
* 压缩文件
*
* @param srcFile 传入的压缩的文件的全路径
* @param dstFile 压缩文件目录
*/
public static void zipFile(String srcFile, String dstFile) {
//创建输出流
OutputStream os = null;
ObjectOutputStream oos = null;
//创建文件的输入流
FileInputStream is = null;
try {
//创建文件的输入流
is = new FileInputStream(srcFile);
//创建一个和源文件大小一样的byte[]
byte[] b = new byte[is.available()];
//读取文件
is.read(b);
//直接对源文件压缩
byte[] huffmanBytes = huffmanZip(b);
//创建文件的输出流, 存放压缩文件
os = new FileOutputStream(dstFile);
//创建一个和文件输出流关联的ObjectOutputStream
oos = new ObjectOutputStream(os);
//把 赫夫曼编码后的字节数组写入压缩文件
oos.writeObject(huffmanBytes);
//这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
//！！！注意一定要把赫夫曼编码 写入压缩文件
oos.writeObject(huffmanCodes);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
is.close();
oos.close();
os.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
```
# 二进制转十进制
正数：反码补码和原码一样，正常计算
负数：
原码：最高位是1，后面是其绝对值的二进制数
反码：符号位不变，数据位按位取反
补码：在其反码的最后一位+1
计算：最左一位表示负，右面七位按位取反+1
eg: 1010 0101 1101 1010 取反 1101 1011 加1 结果= -911
2
3
4
5
上次更新: 2022/04/02, 19:01:05