赫夫曼编码

1. 简介

  • 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法
  • 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
  • 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%~90%之间
  • 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法,称之为最佳编码。

2. 原理

通信领域中信息的处理方式–定长编码

image-20200322203629714

通信领域中信息的处理方式–变长编码

  • 赫夫曼编码

image-20200322203644434

3. 赫夫曼编码实现步骤

3.1 准备工作

  1. 构造节点类
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
/**
* 节点类
* @author DuanChaojie
* @date 2020年3月21日 上午10:54:30
* @version 1.0
*/
class Node implements Comparable<Node>{
Byte data;//存放数据(字符本身),比如‘a’==>97

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;
}


@Override
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();
}
}


}
  1. **private static List<Node> getNodes(byte[] bytes);**把字符数组转换成List [Node[data=97,weight=5],Node[data=xx,weight=x],…..]
  2. private static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();
  3. private static StringBuilder stringBuilder = new StringBuilder();
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
/**
*
* @param bytes 接收的字节数组
* @return 返回的是List [Node[data=97,weight=5],Node[data=xx,weight=x],.....]
*/
private static List<Node> getNodes(byte[] bytes){

//创建一个ArrayList
ArrayList<Node> nodes = new ArrayList<Node>();

//遍历bytes
HashMap<Byte,Integer> counts = new HashMap<>();

for(byte b: bytes) {

Integer count = counts.get(b);
if(count == null) {//map中还没有这个数据
counts.put(b,1);
}else {
counts.put(b,count+1);
}

}

//把每一个键值对转成一个Node对象,并加入到nodes集合中
//遍历map
for(Map.Entry<Byte, Integer> entry:counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;

}

//将生成的赫夫曼编码表存放咋Map中--{32=01,97=100,...}
private static Map<Byte, String> huffmanCodes = new HashMap<Byte,String>();

//生成赫夫曼编码表需要拼接路径,使用StringBuilder储存某个叶子节点的路径
private static StringBuilder stringBuilder = new StringBuilder();

3.2 构成赫夫曼树

  1. 从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树

  2. 取出根节点权值最小的两颗二叉树

  3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

  4. 再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复 1-2-3-4 的步骤,直到数列中,所有的数据都被处理,
    就得到一颗赫夫曼树

  5. image-20200322220130995

  6. 代码实现

    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
       
    /**
    * 通过List创建对应的赫弗曼树
    * @param nodes List<Node>
    * @return
    */
    private static Node createHuffmanTree(List<Node> nodes) {

    while(nodes.size()>1) {

    //排序从小到大
    Collections.sort(nodes);

    //取出第一颗最小的二叉树
    Node leftNode = nodes.get(0);

    //取出第二小的二叉树
    Node rightNode = nodes.get(1);

    //创建一颗新的二叉树,它的根节点没有data只有权值
    Node parentNode = new Node(null, leftNode.weight+rightNode.weight);

    parentNode.left = leftNode;
    parentNode.right = rightNode;

    //将已经处理的两颗二叉树从nodes删除
    nodes.remove(leftNode);
    nodes.remove(rightNode);

    //将新的二叉树加入到nodes
    nodes.add(parentNode);

    }

    //nodes最后的节点,就是赫夫曼树的根节点
    return nodes.get(0);

    }

3.3 获得赫夫曼编码

根据赫夫曼树,给各个字符,规定编码 (前缀编码), 向左的路径为 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
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

/**
* 将传入的node结点的所有子节点的赫夫曼编码得到,并放入到huffmanCodes集合
*
* @param node 传入节点
* @param code 路径:左节点是0 右节点1
* @param stringBuilder 用于拼接路径
*/
private static void getCodes(Node node,String code,StringBuilder stringBuilder) {

StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
//将code加入到stringBuilder2
stringBuilder2.append(code);

//如果node==null不处理
if(node != null) {
//判断当前node是叶子节点还是非叶子节点
if(node.data == null) {//非叶子节点
//向左递归
getCodes(node.left,"0", stringBuilder2);

//向右递归
getCodes(node.right, "1", stringBuilder2);
}else {//说明是一个叶子节点

//找到了某个叶子节点的最后
huffmanCodes.put(node.data, stringBuilder2.toString());
}

}
}

//为了调用方便,我们重载getCodes
private static Map<Byte, String> getCodes(Node root){

if(root == null) {
return null;
}
//处理root的左子树
getCodes(root.left,"0",stringBuilder);

//处理右子树
getCodes(root.right,"1",stringBuilder);

return huffmanCodes;
}

  • 按照上面的赫夫曼编码,我们的”i like like like java do you like a java” 字符串对应的编码为 (注意这里我们使用的无损压缩)
  • 1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
  • 通过赫夫曼编码处理 长度为 133,原来长度是 359 , 压缩了 (359-133) / 359 = 62.9%
  • 此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案(NB)

注意:这个赫夫曼树根据 排序方法不同,也可能不太一样,这样对应的 赫夫曼编码也不完全一样,但是 wpl 是
一样的,都是最小的, 最后生成的赫夫曼编码的长度是一样。

3.4 完成压缩–生成赫夫曼编码

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
/**
* 通过生成的赫夫曼编码表huffmanCodes
* @param bytes 传入之前的contentBytes
* @return 压缩后的byte[] 是一个 赫夫曼编码
*/
private static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes2) {
//利用huffmanCodes将bytes转成赫夫曼编码 对应的字符串
StringBuilder stringBuilder = new StringBuilder();

//遍历bytes数组
for (byte b : bytes) {
stringBuilder.append(huffmanCodes2.get(b));
}

//System.out.println("测试zip方法中的赫夫曼编码对应的二进制字符串:" + stringBuilder );
//System.out.println("压缩后的哈弗曼编码的长度"+stringBuilder.length());

//将二进制(赫夫曼编码对应的字符串)转成byte[]
//int len = stringBuilder.length()/8 + 1;
int len;
if(stringBuilder.length()%8 == 0) {
len = stringBuilder.length()/8;
}else {
len = stringBuilder.length()/8 + 1;
}


//创建储存压缩后的byte 数组
byte[] huffmanCodeBytes = new byte[len];

//记录是第几个byte
int index = 0;
//因为每八位对应一个byte,所以步长是8
for (int i = 0; i < stringBuilder.length(); i += 8) {
String strByte;
if(i+8 > stringBuilder.length()) {
strByte = stringBuilder.substring(i);
}else {
strByte = stringBuilder.substring(i,i+8);
}

//将strByte 转成一个byte放入到huffmanCodeBytes中
//2 表示二进制
//System.out.println("二进制对应的字符串"+strByte);
huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte,2);
//System.out.println("赫夫曼编码字节数组:"+huffmanCodeBytes[index]);
index++;
}

return huffmanCodeBytes;

}

3.5 整合压缩方法–方便调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 将前面的方法封装到这一个方法中,就可以直接调用
* @param bytes 原始的字符串对应的字节数组
* @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
*/
public static byte[] huffmanZip(byte[] bytes) {
//得到对应的List [Node[data=97,weight=5],Node[data=xx,weight=x],.....]
List<Node> nodes = getNodes(bytes);
//System.out.println("对应的List "+nodes.toString());

Node huffmanRootNode = createHuffmanTree(nodes);
//System.out.println("对应赫夫曼树的根节点"+huffmanRootNode);

//{32=01, 97=100, 100=11000, ....}
Map<Byte, String> huffmanCodes = getCodes(huffmanRootNode);
//System.out.println("得到的赫夫曼编码表:"+huffmanCodes.toString());

byte[] huffmanCodeBytes= zip(bytes, huffmanCodes);
//System.out.println("赫夫曼编码字节数组:"+Arrays.toString(huffmanCodeBytes));
return huffmanCodeBytes;
}

3.6 数据解压

  1. 前面我们得到了赫夫曼编码表和对应的编码 byte[] , 即:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
  2. 现在要求使用赫夫曼编码表和编码, 进行解码,又重新得到原来的字符串”i like like like java do you like a java”
  3. 思路:解码过程,就是编码的一个逆向操作。
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/**补高位??????????
* 数据解压的操作,这个是辅助方法,是将字节转成对应的二进制字符串
* 解压需要buffmanCodes和huffmanCodeBytes
* 将huffmanCodeBytes转成二进制字符串
* @param flag 表示是否需要补高位
* @param b 传入的 byte
* @return
*/
private static String byteToString(boolean flag,byte b) {

//使用变量保存b
//将byte转成int 向上转型不需要强转
int temp = b;

//如果是正数我们还存在补高位
if(flag) {
//按位与 256 == 1 0000 0000
temp |= 256;
}
//返回的是temp对应的二进制补码
String str = Integer.toBinaryString(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) {

//先得到huffmanBytes 对应的二进制字符串
StringBuilder stringBuilder = new StringBuilder();

//将byte数组转成二进制的字符串
byte bs;
for (int i = 0; i < huffmanBytes.length; i++) {
bs = huffmanBytes[i];

//判断是不是最后一个字节
boolean flag = (i == huffmanBytes.length -1);

//不是最后一位才补高位
stringBuilder.append(byteToString(!flag,bs));

}

//把字符串按照指定的赫夫曼编码进行解码
//把赫夫曼编码表进行调换,因为反向查询
Map<String,Byte> map = new HashMap<String,Byte>();

for(Map.Entry<Byte,String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(),entry.getKey());
}

//创建要给的集合,存放byte
List<Byte> list = new ArrayList<Byte>();

// i 可以理解为就是索引,扫描stringBuilder
for (int i = 0; i < stringBuilder.length();) {

int count = 1;//小的计数器

boolean flag = true;

Byte b = null;

String key = "";

while(flag) {

//递增的取出key
if ((i+count)>stringBuilder.length()-1) {
key =stringBuilder.substring(i);
break;
}else {
key = stringBuilder.substring(i,i+count);
}


b = map.get(key);

if(b == null) {
count++;
}else {
//匹配到
flag = false;
}
}

list.add(b);
//i 直接移动到 count
i += count;

}

//当for循环结束后,我们直接将list中所存放的所有字符 "i like like like ...."
byte[] bytes = new byte[list.size()];

//这个地方为什么要bytes.lenth-1 ???????????????
for (int i = 0; i < bytes.length-1; i++) {

bytes[i] = list.get(i);

}

return bytes;

}

3.7 实现文件的压缩

  1. 我们学习了通过赫夫曼编码对一个字符串进行编码和解码, 下面我们来完成对文件的压缩和解压
  2. 具体要求:给你一个图片文件,要求对其进行无损压缩, 看看压缩效果如何。
  3. 思路:读取文件-> 得到赫夫曼编码表 -> 完成压缩
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
/**
* 将一个文件进行压缩
* 读取文件 ---> 得到赫夫曼编码表 ---> 完成压缩
* @param srcFile 传入的压缩的文件的全路径
* @param destFile 压缩后的文件存放的地方
*/
public static void zipFile(String srcFile,String destFile) {

//创建输出流
OutputStream os = null;
ObjectOutputStream oos = null;

//创建文件输入流
FileInputStream fis = null;

try {
//创建文件的输入流
fis = new FileInputStream(srcFile);

//创建一个和源文件大小一样的byte[]
byte[] b = new byte[fis.available()];

//读取文件
fis.read(b);

//直接对源文件进行压缩
byte[] huffmanBytes = huffmanZip(b);

//创建文件输出流,存放压缩文件
os = new FileOutputStream(destFile);

//创建一个和文件输出流关联的ObjectOutputStream
oos = new ObjectOutputStream(os);


//把赫夫曼编码后的字节数组写入压缩文件
//我们以对象流的方式写入 赫夫曼编码,是为了我们回复源文件时使用
oos.writeObject(huffmanBytes);

//同时写入赫夫曼编码表
oos.writeObject(huffmanCodes);





} catch (Exception e) {
//这两个有什么区别????
e.printStackTrace();
System.out.println(e.getMessage());
}finally {
try {
fis.close();
oos.close();
os.close();
} catch (Exception e2) {
e2.getStackTrace();
}
}

}

3.8 实现文件解压

  1. 具体要求:将前面压缩的文件,重新恢复成原来的文件。
  2. 思路:读取压缩文件(数据和赫夫曼编码表)-> 完成解压(文件恢复)
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

/**
* 完成对文件的解压
* @param zipFile
* @param destFile
*/
public static void unZipFile(String zipFile,String destFile) {
//定义文件输入流
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(destFile);

//写数组到destFile文件
os.write(bytes);


} catch (Exception e) {
e.printStackTrace();
}finally {

try {
os.close();
ois.close();
is.close();
} catch (Exception e2) {
e2.printStackTrace();
}

}
}

3.8 测试结果

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
/**
* 注意泛型不能有空格
* @author DuanChaojie
* @date 2020年3月21日 上午12:31:48
* @version 1.0
*/
public class HuffmanCode {
public static void main(String[] args) {


/*此处是测试压缩"i like like like java do you like a java"

String content = "i like like like java do you like a java";

byte[] contentBytes = content.getBytes();
//System.out.println("原数据的长度是:"+contentBytes.length);

byte[] bytes = huffmanZip(contentBytes);
System.out.println("压缩后的赫夫曼编码数组:"+Arrays.toString(bytes));

byte[] decode = decode(huffmanCodes,bytes);
System.out.println("解码后的赫夫曼编码数组"+Arrays.toString(decode));
System.out.println("解码后的字符串=" + new String(decode));
*/

//测试压缩文件
//String srcFile = "E:/file/NGC002.jpg";
//String destFile = "E:/file/testRes.zip";
//zipFile(srcFile, destFile);
//System.out.println("压缩成功");

//测试解压文件
String zipFile = "E:/file/testRes.zip";
String destFile = "E:/file/test3.jpg";
unZipFile(zipFile,destFile);
System.out.println("解压成功");


}
}