您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

赫夫曼编码解码(图文)

第十三双眼睛2023-10-20【数据结构与算法】人已围观

简介赫夫曼编码解码

赫夫曼编码解码

package com.xingchen.day012;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class HuffManCode {
public static void main(String[] args) {
String s = "i like like like java do you like a java";
byte[] bytes = s.getBytes();
//System.out.println(bytes.length);
//List<Node> nodes = getNodes(bytes);
//System.out.println(nodes);
//Node huffManTree = createHuffManTree(nodes);
//Map<Byte, String> codeMap = getCodes(huffManTree, "", stringBuilder);
//byte[] zip = zip(bytes, codeMap);
byte[] zip = huffManZip(bytes);
//System.out.println(Arrays.toString(zip));
byte[] decode = decode(codeMap, zip);
System.out.println(Arrays.toString(decode));
System.out.println(new String(decode));
}
public static byte[] huffManZip(byte[] bytes) {
List<Node> nodes = getNodes(bytes);
Node huffManTree = createHuffManTree(nodes);
Map<Byte, String> codeMap = getCodes(huffManTree, "", stringBuilder);

byte[] zip = zip(bytes, codeMap);
return zip;
}
public static byte[] decode(Map<Byte,String> codeMap, byte[] bytes) {
StringBuilder stringBuilder1 = new StringBuilder();
for (int i=0;i < bytes.length;i ++) {
boolean flag = (bytes.length - 1) == i;
stringBuilder1.append(byte2BitString(!flag,bytes[i]));
}
System.out.println(stringBuilder1.toString());
Map<String,Byte> map = new HashMap<>();
for (Map.Entry<Byte,String> entry: codeMap.entrySet()) {
map.put(entry.getValue(), entry.getKey());
}
List<Byte> list = new ArrayList<>();
for (int i=0;i<stringBuilder1.length();) {
int count = 1;
boolean flag = true;
Byte b = null;
while (flag) {
String key = stringBuilder1.substring(i, i + count);
b = map.get(key);
if (b == null) {
count +=1;
} else {
flag = false;
}
}
list.add(b);
i += count;
}
byte[] b = new byte[list.size()];
for (int i = 0; i<b.length; i++) {
b[i] = list.get(i);
}
return b;
}
// 文件的压缩
public static void zipFile(String srcFile,String destFile) {
FileInputStream inputStream = null;
FileOutputStream outputStream = null;
ObjectOutputStream objectOutputStream = null;
try {
inputStream = new FileInputStream(srcFile);
byte[] b = new byte[inputStream.available()];
inputStream.read(b);
byte[] bytes = huffManZip(b);
outputStream = new FileOutputStream(destFile);
objectOutputStream = new ObjectOutputStream(outputStream);
objectOutputStream.writeObject(bytes);
objectOutputStream.writeObject(codeMap);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
inputStream.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
public static void unzip(String zipFile,String destFile) {
InputStream inputStream = null;
OutputStream outputStream = null;
ObjectInputStream objectInputStream = null;
try {
inputStream = new FileInputStream(zipFile);
objectInputStream = new ObjectInputStream(inputStream);
byte[] b = (byte[]) objectInputStream.readObject();
Map<Byte,String> codeMap = (Map)objectInputStream.readObject();
byte[] decode = decode(codeMap, b);
outputStream = new FileOutputStream(destFile);
outputStream.write(decode);
} catch (Exception e) {
e.printStackTrace();
}
}
public static String byte2BitString(boolean flag,byte b) {
int temp = b;
if (flag) {
temp |= 256;
}
String binaryString = Integer.toBinaryString(temp);
if (flag) {
return binaryString.substring(binaryString.length() - 8);
}
return binaryString;
}
public static byte[] zip(byte[] bytes, Map<Byte,String> codeMap) {
StringBuilder builder = new StringBuilder();
for (byte b :bytes) {
builder.append(codeMap.get(b));
}
int length = 0;
if (builder.length()%8 == 0) {
length = builder.length()/8;
} else {
length = builder.length()/8 + 1;
}
int index = 0;
byte[] by = new byte[length];
for (int i = 0 ;i< builder.length();i+=8) {
String bystring = "";
if (i+ 8 >builder.length()) {
bystring = builder.substring(i);
} else {
bystring = builder.substring(i,i + 8);
}
by[index] = (byte) Integer.parseInt(bystring, 2);
index ++;
}
return by;
}
public static List<Node> getNodes(byte[] arr) {
List<Node> list = new ArrayList<>();
//存储每一个字符出现的次数
Map<Byte, Integer> map = new HashMap<>();
for (byte b : arr) {
Integer count = map.get(b);
if (count == null) {
map.put(b, 1);
} else {
map.put(b, count + 1);
}
}
//将每一个键值堆转换成Node
for (Map.Entry<Byte,Integer> entry : map.entrySet()) {
list.add(new Node(entry.getKey(),entry.getValue()));
}
return list;
}
public static Node createHuffManTree(List<Node> list) {
while (list.size() > 1) {
Collections.sort(list);
//取出最小的
Node left = list.get(0);
Node right = list.get(1);
//创建一个新的节点，，没有data
Node parent = new Node(null,left.weight + right.weight);
parent.left = left;
parent.right = right;
list.remove(left);
list.remove(right);
list.add(parent);
}
return list.get(0);
}
static Map<Byte,String> codeMap = new HashMap<>();
static StringBuilder stringBuilder = new StringBuilder();
public static Map<Byte,String> getCodes(Node node,String code,StringBuilder stringBuilder) {
StringBuilder builder2 = new StringBuilder(stringBuilder);
builder2.append(code);
if (code != null) {
if (node.data == null) {
//向左递归
getCodes(node.left,"0",builder2);
//向右递归
getCodes(node.right,"1",builder2);
} else {
codeMap.put(node.data,builder2.toString());
}
}
return codeMap;
}
}
class Node implements Comparable<Node>{
public Byte data;
public int weight;
public Node left;
public Node right;
public Node(Byte data, int weight) {
this.data = data;
this.weight = 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();
}
}
@Override
public int compareTo(Node o) {
return this.weight - o.weight;
}
}

Tags：

很赞哦！ ()

上一篇：赫夫曼树(图文)

下一篇：二叉排序树的创建(图文)