最佳实践-数据压缩(创建赫夫曼树)
将给出的一段文本，比如 "i like like like java do you like a java" ， 根据前面的讲的赫夫曼编码原理，对其进行数据压缩处理 ，形式如 "1010100110111101111010011011110111101001101111011110100001100001110011001111000011001111000100100100110111101111011100100001100001110
"
步骤1：根据赫夫曼编码压缩数据的原理，需要创建 "i like like like java do you like a java" 对应的赫夫曼树.
思路：前面已经分析过了，而且我们已然讲过了构建赫夫曼树的具体实现。
功能： 根据赫夫曼编码压缩数据的原理，需要创建 "i like like like java do you like a java" 对应的赫夫曼树
思路:
(1) Node { data (存放数据)， weight (权值)， left 和 right }
(2) 得到 "i like like like java do you like a java" 对应的 byte[] 数组
(3) 编写一个方法，将准备构建赫夫曼树的Node 节点放到 List , 形式 [Node[date=97 ,weight = 5], Node[]date=32,weight = 9]......], 体现 d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9
(4) 可以通过List 创建对应的赫夫曼树
生成赫夫曼树对应的赫夫曼编码 , 如下表:=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
代码实现：
package cn.icanci.datastructure.haffmantree.haffmancode;
import java.util.*;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.haffmantree.haffmancode
* @Date: Created in 2020/3/15 21:04
* @ClassAction: 哈夫曼编码
*/
public class HuffmanCode {
public static void main(String[] args) {
String str = "i like like like java do you like a java";
byte[] bytes = str.getBytes();
byte[] bytes1 = huffmanZip(bytes);
System.out.println(Arrays.toString(bytes1));
}
/**
* @param bytes 需要压缩的
* @return 压缩之后的
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
Node huffmanTree = createHuffmanTree(nodes);
preOrder(huffmanTree);
getCodes(huffmanTree);
byte[] zip = zip(bytes, huffmanCodes);
return zip;
}
/**
* 编写一个方法 将字符串对应的Byte数组 通过生成的哈夫曼编码表
*
* @param bytes
* @param huffmanCodes
* @return 对应的 byte数组
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//先利用 huffmanCodes 将 bytes 转成 哈夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//将字符串转成 byte数组
//统计返回的 长度
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//创建存储压缩后的数组
byte[] by = new byte[len];
int index = 0;
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);
}
by[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return by;
}
//生成赫夫曼树的对应的赫夫曼编码
//思路分析:
//1.将赫夫曼编码存放着在 Map<Byte,String>
//2.在生成哈夫曼编码表的时候 需要去拼接路径
static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
static StringBuilder sb = new StringBuilder();
private static void getCodes(Node root) {
if (root == null) {
System.out.println("空");
} else {
getCodes(root, "", sb);
}
}
/**
* 功能:将传入的node节点的所有叶子节点的赫夫曼编码得到 并放入huffmanCodes集合
*
* @param node 传入节点
* @param code 传入;路径 左 0 右1
* @param stringbuilder 拼接路径的
*/
private static void getCodes(Node node, String code, StringBuilder stringbuilder) {
StringBuilder stringBuilder = new StringBuilder(stringbuilder);
stringBuilder.append(code);
if (node != null) {
//判断当前Node是叶子节点还是非叶子节点
if (node.data == null) {
getCodes(node.left, "0", stringBuilder);
getCodes(node.right, "1", stringBuilder);
} else {
//是叶子节点 找到了叶子节点的最后
huffmanCodes.put(node.data, stringBuilder.toString());
}
}
}
//前序遍历
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("空");
}
}
/**
* 接收字节数组
*
* @param bytes 需要转换的字节数组
* @return 返回
*/
private static List<Node> getNodes(byte[] bytes) {
//创建一个ArrayList
List<Node> nodes = new ArrayList<>();
//编译bytes 统计
HashMap<Byte, Integer> hashMap = new HashMap<>();
for (byte b : bytes) {
Integer count = hashMap.get(b);
if (count == null) {
hashMap.put(b, 1);
} else {
hashMap.put(b, count + 1);
}
}
//把每个键值对 转成一个Node对象
for (Map.Entry<Byte, Integer> entry : hashMap.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);
Node left = nodes.get(0);
Node right = nodes.get(1);
//创建一个新的二叉树 没有根节点 只有权值
Node parent = new Node(null, left.weight + right.weight);
parent.left = left;
parent.right = right;
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
}
//创建Node
class Node implements Comparable<Node> {
//存放数据本身
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;
}
@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();
}
}
}
测试
Node{data=null, weight=40}
Node{data=null, weight=17}
Node{data=null, weight=8}
Node{data=108, weight=4}
Node{data=null, weight=4}
Node{data=106, weight=2}
Node{data=111, weight=2}
Node{data=32, weight=9}
Node{data=null, weight=23}
Node{data=null, weight=10}
Node{data=97, weight=5}
Node{data=105, weight=5}
Node{data=null, weight=13}
Node{data=null, weight=5}
Node{data=null, weight=2}
Node{data=100, weight=1}
Node{data=117, weight=1}
Node{data=null, weight=3}
Node{data=121, weight=1}
Node{data=118, weight=2}
Node{data=null, weight=8}
Node{data=101, weight=4}
Node{data=107, weight=4}
[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
最佳实践-数据解压(使用赫夫曼编码解码)
使用赫夫曼编码来解码数据，具体要求是
前面我们得到了赫夫曼编码和对应的编码�byte[] , 即:[-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"
思路：解码过程，就是编码的一个逆向操作。
代码实现：
package cn.icanci.datastructure.haffmantree.haffmancode;
import org.springframework.context.annotation.Bean;
import java.util.*;
/**
* @Author: icanci
* @ProjectName: AlgorithmAndDataStructure
* @PackageName: cn.icanci.datastructure.haffmantree.haffmancode
* @Date: Created in 2020/3/15 21:04
* @ClassAction: 哈夫曼编码
*/
public class HuffmanCode {
public static void main(String[] args) {
String str = "i like like like java do you like a java";
byte[] bytes = str.getBytes();
byte[] bytes1 = huffmanZip(bytes);
System.out.println(Arrays.toString(bytes1));
byte[] decode = decode(huffmanCodes, bytes1);
for (byte b : decode) {
System.out.print((char) b);
}
System.out.println();
System.out.println(Arrays.toString(decode));
}
/**
* 数据解码
*
* @param huffmanCodes 编码表
* @param bytes 赫夫曼编码得到的字节数组
* @return
*/
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] bytes) {
//1.先得到 bytes 对应的二进制字符串
StringBuilder stringBuilder = new StringBuilder();
//2.将byte数组
for (int i = 0; i < bytes.length; i++) {
boolean flag = (i == bytes.length - 1);
stringBuilder.append(byteToString(!flag, bytes[i]));
}
//把字符串按照指定的赫夫曼编码进行节码
//把赫夫曼编码进行调换 反响查询
Map<String, Byte> map = new HashMap<String, Byte>();
for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
//创建一个集合
ArrayList<Byte> list = new ArrayList<>();
for (int i = 0; i < stringBuilder.length();) {
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
//取出一个 1 0
String key = stringBuilder.substring(i, i + count);
b = map.get(key);
if (b == null) {
count++;
} else {
flag = false;
}
}
list.add(b);
i += count;
}
//把list数组放在 byte数组中
byte[] by = new byte[list.size()];
for (int i = 0; i < list.size(); i++) {
by[i] = list.get(i);
}
return by;
}
//数据的解压
//重新转成字符串 然后在转为 二进制字符串
private static String byteToString(boolean flag, byte b) {
int temp = b;
//如何是证数 需要补位
//按位与
if (flag) {
temp |= 256;
}
//返回的是temp 的对应的补码
String string = Integer.toBinaryString(temp);
if (flag) {
return string.substring(string.length() - 8);
} else {
return string;
}
}
/**
* @param bytes 需要压缩的
* @return 压缩之后的
*/
private static byte[] huffmanZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
Node huffmanTree = createHuffmanTree(nodes);
preOrder(huffmanTree);
getCodes(huffmanTree);
byte[] zip = zip(bytes, huffmanCodes);
return zip;
}
/**
* 编写一个方法 将字符串对应的Byte数组 通过生成的哈夫曼编码表
*
* @param bytes
* @param huffmanCodes
* @return 对应的 byte数组
*/
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
//先利用 huffmanCodes 将 bytes 转成 哈夫曼编码对应的字符串
StringBuilder stringBuilder = new StringBuilder();
for (byte b : bytes) {
stringBuilder.append(huffmanCodes.get(b));
}
//将字符串转成 byte数组
//统计返回的 长度
int len;
if (stringBuilder.length() % 8 == 0) {
len = stringBuilder.length() / 8;
} else {
len = stringBuilder.length() / 8 + 1;
}
//创建存储压缩后的数组
byte[] by = new byte[len];
int index = 0;
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);
}
by[index] = (byte) Integer.parseInt(strByte, 2);
index++;
}
return by;
}
//生成赫夫曼树的对应的赫夫曼编码
//思路分析:
//1.将赫夫曼编码存放着在 Map<Byte,String>
//2.在生成哈夫曼编码表的时候 需要去拼接路径
static Map<Byte, String> huffmanCodes = new HashMap<Byte, String>();
static StringBuilder sb = new StringBuilder();
private static void getCodes(Node root) {
if (root == null) {
System.out.println("空");
} else {
getCodes(root, "", sb);
}
}
/**
* 功能:将传入的node节点的所有叶子节点的赫夫曼编码得到 并放入huffmanCodes集合
*
* @param node 传入节点
* @param code 传入;路径 左 0 右1
* @param stringbuilder 拼接路径的
*/
private static void getCodes(Node node, String code, StringBuilder stringbuilder) {
StringBuilder stringBuilder = new StringBuilder(stringbuilder);
stringBuilder.append(code);
if (node != null) {
//判断当前Node是叶子节点还是非叶子节点
if (node.data == null) {
getCodes(node.left, "0", stringBuilder);
getCodes(node.right, "1", stringBuilder);
} else {
//是叶子节点 找到了叶子节点的最后
huffmanCodes.put(node.data, stringBuilder.toString());
}
}
}
//前序遍历
private static void preOrder(Node root) {
if (root != null) {
root.preOrder();
} else {
System.out.println("空");
}
}
/**
* 接收字节数组
*
* @param bytes 需要转换的字节数组
* @return 返回
*/
private static List<Node> getNodes(byte[] bytes) {
//创建一个ArrayList
List<Node> nodes = new ArrayList<>();
//编译bytes 统计
HashMap<Byte, Integer> hashMap = new HashMap<>();
for (byte b : bytes) {
Integer count = hashMap.get(b);
if (count == null) {
hashMap.put(b, 1);
} else {
hashMap.put(b, count + 1);
}
}
//把每个键值对 转成一个Node对象
for (Map.Entry<Byte, Integer> entry : hashMap.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);
Node left = nodes.get(0);
Node right = nodes.get(1);
//创建一个新的二叉树 没有根节点 只有权值
Node parent = new Node(null, left.weight + right.weight);
parent.left = left;
parent.right = right;
nodes.remove(left);
nodes.remove(right);
nodes.add(parent);
}
return nodes.get(0);
}
}
//创建Node
class Node implements Comparable<Node> {
//存放数据本身
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;
}
@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();
}
}
}
测试
Node{data=null, weight=40}
Node{data=null, weight=17}
Node{data=null, weight=8}
Node{data=108, weight=4}
Node{data=null, weight=4}
Node{data=106, weight=2}
Node{data=111, weight=2}
Node{data=32, weight=9}
Node{data=null, weight=23}
Node{data=null, weight=10}
Node{data=97, weight=5}
Node{data=105, weight=5}
Node{data=null, weight=13}
Node{data=null, weight=5}
Node{data=null, weight=2}
Node{data=100, weight=1}
Node{data=117, weight=1}
Node{data=null, weight=3}
Node{data=121, weight=1}
Node{data=118, weight=2}
Node{data=null, weight=8}
Node{data=101, weight=4}
Node{data=107, weight=4}
[-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
[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]
