Huffman Coding
- 简介
-
- 3种编码原理
- 代码实现
简介
- 赫夫曼编码是可变字长编码(VLC)的一种, 常用于数据文件压缩. 其压缩通常在20%~90%之间
3种编码原理
- 在通信领域中信息的处理方式
- 定长编码:
- 变长编码:
* 变长编码的缺点是编码格式重叠无法避免, 即不能匹配重复的编码
3) 赫夫曼编码:
代码实现
- 字符串解压缩
public class HuffmanCodeApp {
public static void main(String[] args) {
String content = "i like like like java do you like a java";
System.out.println("原数据长度 " + content.length() + ", 内容 " + content);
/** 原数据内容转 bytes*/
byte[] contentBytes = content.getBytes();
System.out.println("原数据转 bytes后的数组长度 " + contentBytes.length + ", 内容 " + Arrays.toString(contentBytes));
/** 把原数据的 bytes数组进行压缩*/
byte[] huffmanCodesBytes= zip(contentBytes);
System.out.println("压缩后的内容长度 " + huffmanCodesBytes.length + ", 内容 " + Arrays.toString(huffmanCodesBytes));
/** 解压(解码)*/
byte[] sourceBytes = unzip(huffmanCodes, huffmanCodesBytes);
System.out.println("解压还原原数据内容 " + new String(sourceBytes));
}
/** Map形式, 生成哈夫曼编码表 {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<>();
/** 采用赫夫曼编码压缩数据的方法
* @param bytes 原数据对应的字节数组(将此字节数组进行压缩)
* @return 采用赫夫曼编码方式处理过的(压缩后的)字节数组*/
private static byte[] zip(byte[] bytes) {
/** 生成节点列表*/
List<Node> nodes = getNodes(bytes);
/** 创建的赫夫曼树*/
Node huffmanTreeRoot = createHuffmanTree(nodes);
/** 开始处理赫夫曼树 root的左子树*/
createHuffmanCode(huffmanTreeRoot.left, "0", null);
/** 开始处理赫夫曼树 root的右子树*/
createHuffmanCode(huffmanTreeRoot.right, "1", null);
/** 将原数据字符对应字节, 按序遍历, 从 huffmanCodes获取每个字节的路径, 拼接成赫夫曼编码*/
StringBuilder _path = new StringBuilder();
for(byte b: bytes) {
_path.append(huffmanCodes.get(b));
}
// _path输出 => 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
// [105(i), 32( ), 108(l), 105(i)... => 101 01 000 101 ... => 也就是拼接后 10101000101...
// 将赫夫曼编码当成字节, 计算长度(每个字节占8位)
// int len = (_path.length() + 7) / 8;
int len;
if(_path.length() % 8 == 0) {
len = _path.length() / 8;
} else {
len = _path.length() / 8 + 1;
}
byte[] huffmanCodeBytes = new byte[len];
int index = 0;
for (int i = 0; i < _path.length(); i += 8) {
String strByte;
if(i + 8 > _path.length()) { /** 最后轮不够8位时*/
strByte = _path.substring(i);
}else{
strByte = _path.substring(i, i + 8);
}
/** 将 strByte转成一个 byte; 转成二进制*/
huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return huffmanCodeBytes;
}
/** @param bytes 接收原数据的字节数组*/
private static List<Node> getNodes(byte[] bytes) {
ArrayList<Node> nodes = new ArrayList<>();
/** 将原数据的字节数组遍历
* - 统计每一个字节出现的次数, map(key字节码, 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);
}
}
/** 在上面统计过相同字节的 map, 将 map.key(字节码)当作节点数据本身, map.value(指定字节的重复次数)当作节点权值, 循环制作节点列表
* 其中字节码会用于赫夫曼*/
for(Map.Entry<Byte, Integer> entry: counts.entrySet()) {
nodes.add(new Node(entry.getKey(), entry.getValue()));
}
/** 此列表用于生成赫夫曼树*/
return nodes;
}
/** 创建的赫夫曼树方法*/
private static Node createHuffmanTree(List<Node> nodes) {
while(nodes.size() > 1) {
/** 从小到大排序*/
Collections.sort(nodes);
/** 取出根节点权值最小的两颗二叉树*/
//(1) 取出权值最小的结点(二叉树)
Node leftNode = nodes.get(0);
//(2) 取出权值第二小的结点(二叉树)
Node rightNode = nodes.get(1);
//(3) 创建一颗新的二叉树, 此树的根节点, 没有 data, 只有权值
Node parent = new Node(null, leftNode.weight + rightNode.weight);
parent.left = leftNode;
parent.right = rightNode;
//(4) 将 parent加到 List中
nodes.add(parent);
//(5) 从 List中删除处理过的二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
}
/** 最后返回制作完成的赫夫曼树的 root结点*/
return nodes.get(0);
}
/** 功能: 将传入的 node节点的所有叶子节点的赫夫曼编码得到，并放入到 huffmanCodes集合
* @param node 传入节点
* @param code 路径: 左子节点是0, 右子节点1
*/
private static void createHuffmanCode(Node node, String code, StringBuilder path) {
if(node != null) {
StringBuilder _path = new StringBuilder(path == null ? "": path.toString());
_path.append(code);
/** 判断当前 node是否为非叶子节点*/
if(node.data == null) {
/** 当前 node为非叶子结点时
* - 继续递归向左右处理*/
createHuffmanCode(node.left, "0", _path);
createHuffmanCode(node.right, "1", _path);
} else {
/** 抵达到叶子节点, 将节点值(原数据的指定字节码)和到达此节点的路径加到 huffmanCodes集合中*/
huffmanCodes.put(node.data, _path.toString());
}
}
}
/* 解码方法
* @param huffmanCodeBytes 赫夫曼编码得到的字节数组
* @return 返回原数据对应的字节数组*/
private static byte[] unzip(Map<Byte, String> huffmanCodes, byte[] huffmanCodeBytes) {
/** 将采用赫夫曼编码生成的赫夫曼编码字节数组(huffmanCodeBytes), 重新解析转成赫夫曼编码字符串*/
StringBuilder _path = new StringBuilder();
for(int i = 0; i < huffmanCodeBytes.length; i++) {
byte b = huffmanCodeBytes[i];
/** 判断是否为最后的字节*/
boolean flag = (i == huffmanCodeBytes.length - 1);
String strByte = byteToBitString(!flag, b);
_path.append(strByte);
}
// _path => 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
/** 将赫夫曼编码表 map, key/vlaue调过来, 为反向查询 {32=01, 97=100... => {01=32, 100=97...*/
Map<String, Byte> map = new HashMap<>();
for(Map.Entry<Byte, String> entry: huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
/** List中存放, 解析后的原始字符的字节码*/
List<Byte> list = new ArrayList<>();
/** 将赫夫曼编码 _path路径字符串, 一个路径字符->一个路径字符...做字符串扫描, 判断 huffmanCodes中是否存在*/
for(int i = 0; i < _path.length();) {
int count = 1; // 小的计数器
boolean flag = true;
Byte b = null;
while(flag) {
/** 赫夫曼编码中每个路径的起始下标 i保持不变, 移动到 count位置, 一一匹配, 判断 huffmanCodes中是否存在*/
String key = _path.substring(i, i+count);
b = map.get(key);
if(b == null) { /** 说明没有匹配到*/
count++;
}else {
/** 匹配到了, 结束此 while, 将匹配到的字节码加到 List, 继续往后扫描*/
flag = false;
}
}
list.add(b);
/** 下次扫描的开始下标是这次结束的下标*/
i += count;
}
/** 将解析后得到的原数据字节 List, 转存到 byte数组中后返回*/
byte b[] = new byte[list.size()];
for(int i = 0;i < b.length; i++) {
b[i] = list.get(i);
}
return b;
}
/** 将传入的 b转成一个二进制的字符串
* @param flag 标志是否需要补高位 如是 true就补高位, 否则不补. 最后一个字节不做补高位操作
* @param b 传入的 byte
* @return 返回 b对应二进制的字符串(按补码返回)*/
private static String byteToBitString(boolean flag, byte b) {
/** 将 b转成 int*/
int temp = b;
if(flag) {
/** 如果是正数, 需要补高位*/
temp |= 256; // 按位与 256 1 0000 0000 | 0000 0001 => 1 0000 0001
/** 例 byte 77 => (temp |= 256) => temp=333*/
}
String str = Integer.toBinaryString(temp); /** 例 int 333 => 101001101*/
if(flag) {
return str.substring(str.length() - 8); /** 例 101001101 => 01001101*/
} else {
return str;
}
}
}
/** 定义结点*/
class Node implements Comparable<Node> {
/** 存放数据本身, 比如 '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 + "]";
}
}
输出:
> 原数据长度 40, 内容 i like like like java do you like a java
> 原数据转 bytes后的数组长度 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]
> 压缩后的内容长度 17, 内容 [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
> 解压还原原数据内容 i like like like java do you like a java
- 文件解压缩
public static void main(String[] args) {
String srcFile = "/Users/quanchunlin/Desktop/test.txt";
String dstFile = "/Users/quanchunlin/Desktop/test.zip";
zipFile(srcFile, dstFile);
System.out.println("压缩文件成功!");
// String zipFile = "/Users/quanchunlin/Desktop/test.zip";
// String dstFile = "/Users/quanchunlin/Desktop/test.txt";
// unZipFile(zipFile, dstFile);
// System.out.println("解压文件成功!");
}
/** 压缩文件方法
* @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()];
/** 读取文件到 byte[] b中*/
is.read(b);
/** 将原文件字节内容进行压缩*/
byte[] huffmanBytes = zip(b);
/** 创建输出流, 存放压缩文件*/
os = new FileOutputStream(dstFile);
/** 创建对象的输出流*/
oos = new ObjectOutputStream(os);
/** 将赫夫曼编码后的字节数组写入压缩文件*/
oos.writeObject(huffmanBytes);
/** 将赫夫曼编码一并写入到压缩文件中*/
oos.writeObject(huffmanCodes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
is.close();
oos.close();
os.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
/** 解压文件方法
* @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);
/** 创建对象的输入流*/
ois = new ObjectInputStream(is);
/** 读取 huffmanCodeBytes*/
byte[] huffmanBytes = (byte[]) ois.readObject();
/** 读取赫夫曼编码表*/
Map<Byte, String> huffmanCodes = (Map<Byte,String>) ois.readObject();
/** 将赫夫曼编码进行解压*/
byte[] bytes = unzip(huffmanCodes, huffmanBytes);
/** 创建输出流, 存放解压后的文件*/
os = new FileOutputStream(dstFile);
/** 将解码后的原数据字节数组写入到 dstFile件中*/
os.write(bytes);
} catch (Exception e) {
System.out.println(e.getMessage());
} finally {
try {
os.close();
ois.close();
is.close();
} catch (Exception e) {
System.out.println(e.getMessage());
}
}
}
如果您觉得有帮助，欢迎点赞哦 ~ 谢谢!!