- 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式, 属于一种程序算法。
- 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一。
- 赫夫曼编码广泛地用于数据文件压缩。其压缩率通常在 20%～90%之间
- 赫夫曼码是可变字长编码(VLC)的一种。Huffman 于 1952 年提出一种编码方法，称之为最佳编码
通信领域中信息的处理方式-----赫夫曼编码
步骤如下：
传输的字符串 i like like like java do you like a java
- i like like like java do you like a java
- d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9（空格:9） // 各个字符对应的个数
- 按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值
步骤：
构成赫夫曼树的步骤：
-
从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树
-
取出根节点权值最小的两颗二叉树
-
组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
-
再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树。
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（空格:01） -
按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注
意这里我们使用的无损压缩)
1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110 通过赫夫曼编码处理 长度为 133 -
长度为 ： 133
说明:如果不压缩转换成二进制的长度是 359 , 压缩了 (359-133) / 359 = 62.9%
此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性赫夫曼编码是无损处理方案
注意事项
注意, 这个赫夫曼树根据排序方法不同，也可能不太一样，这样对应的赫夫曼编码也不完全一样，但是 wpl 是一样的，都是最小的, 最后生成的赫夫曼编码的长度是一样，比如: 如果我们让每次生成的新的二叉树总是排在权值相同的二叉树的最后一个，则生成的二叉树为:
将给出的一段文本，比如 “i like like like java do you like a java” ， 根据前面的讲的赫夫曼编码原理，对其进行数据 压 缩 处 理 ， 形 式 如:
“1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110”
步骤 1：根据赫夫曼编码压缩数据的原理，需要创建 “i like like like java do you like a java” 对应的赫夫曼树。
思路：前面已经分析过了。
代码：（为了防止混乱，赫夫曼编码代码和下面的解码代码放在一起）
我们已经生成了 赫夫曼树, 下面我们继续完成任务
- 生成赫夫曼树对应的赫夫曼编码 , 如下表: =01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
- 使用赫夫曼编码来生成赫夫曼编码数据 ,即按照上面的赫夫曼编码，将"i like like like java do you like a java" 字符串生成对应的编码数据, 形式如:下：1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
- 思路：前面已经分析过了。
赫夫曼编码实现文件的压缩和解压代码也在里面
import java.io.*;
import java.util.*;
public class HuffmanCode {
public static void main(String[] args) {
// 测试Huffman文件压缩
// String srcFile = "E:\11.jpg";
// String dstFile = "E:\11.zip";
// zipFile(srcFile,dstFile);
// 测试Huffman文件解压
String srcFile = "E:\11.zip";
String dstFile = "E:\22.jpg";
unZip(srcFile,dstFile);
}
// TODO ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓中间代码为huffman文件压缩和解码的相关方法↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
public static void zipFile(String srcFile, String dstFile){
InputStream is = null;
OutputStream os = null;
ObjectOutputStream oos = null;
try {
is = new FileInputStream(srcFile);
byte[] b = new byte[is.available()];
is.read(b);
os = new FileOutputStream(dstFile);
oos = new ObjectOutputStream(os);
// huffman压缩
//把 赫夫曼编码后的字节数组写入压缩文件
byte[] huffmanBytes = huffmanZip(b);
oos.writeObject(huffmanBytes);
//这里我们以对象流的方式写入 赫夫曼编码，是为了以后我们恢复源文件时使用
//注意一定要把赫夫曼编码 写入压缩文
oos.writeObject(huffmanCode);
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
if (is != null){
try {
is.close();
} catch (IOException e) {
e.printStackTrace();
}
}
if (oos!=null){
try {
oos.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
public static void unZip(String zipFile,String dstFile){
InputStream is = null;
ObjectInputStream ois = null;
OutputStream os = null;
try {
is = new FileInputStream(zipFile);
ois = new ObjectInputStream(is);
byte[] huffmanBytes = (byte[]) ois.readObject();
Map huffmanCode = (Map) ois.readObject();
byte[] bytes = decode(huffmanCode, huffmanBytes);
os = new FileOutputStream(dstFile);
os.write(bytes);
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} catch (ClassNotFoundException e) {
e.printStackTrace();
}finally {
if (ois!=null){
try {
ois.close();
} catch (IOException e) {
e.printStackTrace();
}
}
if (os!=null){
try {
ois.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
// TODO ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑中间代码为huffman文件压缩和解码的相关方法↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
// TODO ↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓中间代码为huffman解码的相关方法↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
//编写一个方法，完成对压缩数据的解码
private static byte[] decode(Map huffmanCodes, byte[] huffmanBytes){
// 获得huffmanBytes 数组对应的二进制字符串
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < huffmanBytes.length; i++) {
byte b = huffmanBytes[i];
boolean flag = (i==huffmanBytes.length-1);
String string = byteToBitString(b, !flag);
stringBuilder.append(string);
}
// 把huffmanCodes 反过来 接下来进行解码
HashMap map = new HashMap<>();
for (Map.Entry byteStringEntry : huffmanCodes.entrySet()) {
map.put(byteStringEntry.getValue(),byteStringEntry.getKey());
}
// 把解码的数据先存放到list
ArrayList list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length();) {
boolean flag = true;
int count = 1;
Byte b = null;
while (flag){
// 截取字符串范围 start(包括) end(不包括)
String str = stringBuilder.substring(i, i+count);
b = map.get(str);
if (b==null){
count++;
}else {
list.add(b);
flag = false;
}
}
i += count;
}
// 把list集合的数据放到 byte数组
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(byte b,boolean flag){
int temp = b;
if (flag){
temp |= 256; //按位与 256 1 0000 0000 | 0000 0001 => 1 0000 000
}
String str = Integer.toBinaryString(temp);
if (flag){
return str.substring(str.length()-8);
}else {
return str;
}
}
// TODO↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑中间代码为huffman解码的相关方法↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
public static byte[] huffmanZip(byte[] bytes){
List nodes = huffmanTreeList(bytes);
Node huffmanTreeRoot = createHuffmanTree(nodes);
Map huffmanCode = getHuffmanCode(huffmanTreeRoot);
return zip(bytes, huffmanCode);
}
public static byte[] zip(byte[] bytes,Map huffmanCode){
// 1.利用huffmanCode 将bytes 转换成huffmanCode对应的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCode.get(b));
}
//统计返回byte[] huffmanCodeBytes 长度
int len = 0;
if (stringBuilder.length() % 8==0){
len = stringBuilder.length() / 8;
}else {
len = stringBuilder.length() / 8 + 1;
}
// 创建存储压缩后的bytes[]
byte[] huffmanCodeBytes = new byte[len];
int index = 0;
for (int i = 0; i < stringBuilder.length(); i+=8) {
String substring;
if (i+8>stringBuilder.length()){
substring = stringBuilder.substring(i);
}else {
substring = stringBuilder.substring(i,i+8);
}
huffmanCodeBytes[index] = (byte) Integer.parseInt(substring,2);
index++;
}
return huffmanCodeBytes;
}
// 为了方便调用 重载getHuffmanCode()方法
public static Map getHuffmanCode(Node root){
if (root !=null){
getHuffmanCode(root,"",stringBuilder);
}else {
System.out.println("root node is null");
}
return huffmanCode;
}
// 储存生成的哈夫曼编码
static Map huffmanCode = new HashMap<>();
// 生成哈夫曼编码过程中拼接字符串
static StringBuilder stringBuilder = new StringBuilder();
public static void getHuffmanCode(Node node, String code, StringBuilder stringBuilder) {
StringBuilder stringBuilder1 = new StringBuilder(stringBuilder);
stringBuilder1.append(code);
if (node != null) {
if (node.data == null) { //非叶子节点
//递归处理
//向左递归
if (node.left!=null){
getHuffmanCode(node.left,"0",stringBuilder1);
}
//向右递归
if (node.right!=null){
getHuffmanCode(node.right,"1",stringBuilder1);
}
} else { // 叶子节点
huffmanCode.put(node.data,stringBuilder1.toString());
}
}
}
// 前序遍历huffmanTree
public static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("root is null");
}
}
public static Node createHuffmanTree(List nodeList) {
while (nodeList.size() > 1) {
Collections.sort(nodeList);
Node leftNode = nodeList.get(0);
Node rightNode = nodeList.get(1);
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
nodeList.add(parent);
nodeList.remove(leftNode);
nodeList.remove(rightNode);
}
return nodeList.get(0);
}
public static List huffmanTreeList(byte[] bytes) {
List nodes = new ArrayList<>();
Map map = new HashMap<>();
for (byte b : bytes) {
Integer count = map.get(b);
if (count == null) {
map.put(b, 1);
} else {
map.put(b, count + 1);
}
}
Set> entries = map.entrySet();
for (Map.Entry entry : entries) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
return nodes;
}
}
class Node implements Comparable {
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 void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
@Override
public String toString() {
return "Node{" +
"data=" + data +
", weight=" + weight +
'}';
}
}
11.3.9 赫夫曼编码压缩文件注意事项
- 如果文件本身就是经过压缩处理的，那么使用赫夫曼编码再压缩效率不会有明显变化, 比如视频,ppt 等等文件【举例：压缩一个ppt】
- 赫夫曼编码是按字节来处理的，因此可以处理所有的文件(二进制文件、文本文件) [举例压一个.xml 文件]
- 如果一个文件中的内容，重复的数据不多，压缩效果也不会很明显
