首先对于赫夫曼编码有个大概的理解：赫夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。
赫夫曼编码，主要目的是根据使用频率来最大化节省字符（编码）的存储空间。(举例来说，对于一个字符串中"i like java do you like a java"中有多个重复字符，我们可以存储一次一个字符对应的编码即可，可以节省存储空间) ；网上大多数用的是char来进行字符个数的查询以及 编码和解码，其实赫夫曼编码初衷就是可以用来压缩图片等，具体在百度百科上有介绍，下文也有链接。如果用char[] 就限制到了字符串是没有体现出来的；此博客用byte数组来进行编码解码和存储；
哈夫曼编码大致过程:
将字符串转换为byte数组
检查byte数组中字符的出现次数，将字符的byte和字符出现次数保存为节点，放入集合中
构建哈夫曼树（最小带权二叉树）
设左路径为0 右路径为1 计算字符的哈夫曼编码值，存入Map集合中（以便我们用map集合来找变长编码对应的值，但是这种方式会造成一定的问题后边说）
参照Map集合，将byte数组转换为byte字符串，将其对照Map集合逐一处理，由于数据量较大，所以八位一组进行数据压缩
步骤对应的动画演示为：
对于各个步骤对应的代码加注释如下：
package binaryTree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import org.junit.Test;
/***
*
* 没有实现文件压缩和解压，只需要对byte[]进行一下写入就可以了（最好用ObjectOutputStream 直接写入对象）
* 这个实现byte类型转换成对应二进制string的方法不太好而且网上方法还没有这个好
* @author 杰夫·王盖茨
*
*/
public class HuffmanCode {
private Map<Byte,String> huffManCodes ;
private StringBuilder sb;
public HuffmanCode() {
huffManCodes = new HashMap<>();
sb = new StringBuilder();
}
public static void main(String[] args) {
String s = "i like like like java do you like a java";
byte[] bytes = s.getBytes();
HuffmanCode huffmanCode = new HuffmanCode();
/*
* WeightNode root = huffmanCode.getRoot(huffmanCode.getWeightNode(bytes)); //
* root.preList(); huffmanCode.getHuffmanCode(root, "", huffmanCode.sb);
* Iterator<Entry<Byte, String>> iterator =
* huffmanCode.huffManCodes.entrySet().iterator(); while(iterator.hasNext()) {
* Entry<Byte, String> next = iterator.next(); System.out.println(next); }
* huffmanCode.gethuffmanCode(root); Iterator<Entry<Byte, String>> iterator1 =
* huffmanCode.huffManCodes.entrySet().iterator(); while(iterator.hasNext()) {
* Entry<Byte, String> next = iterator1.next(); System.out.println(next); }
*/
byte[] zip = huffmanCode.zip(bytes);
System.out.println(Arrays.toString(zip));
byte[] unZip = huffmanCode.unZip(zip, huffmanCode.huffManCodes);
System.out.println(new String(unZip));
}
/**
* 将byte【】 统计重复byte之后得到对应的data和权重并且将他们包装成list
* @param bytes
* @return
*/
public List<WeightNode> getWeightNode(byte[] bytes) {
HashMap<Byte, Integer> hashMap = new HashMap<>();
for(byte b : bytes) {
if(hashMap.get(b)==null) {
hashMap.put(b, 1);
}else {
hashMap.replace(b, hashMap.get(b)+1);
}
}
ArrayList<WeightNode> arrayList = new ArrayList<>();
Iterator<Entry<Byte, Integer>> iterator = hashMap.entrySet().iterator();
while(iterator.hasNext()) {
Entry<Byte, Integer> next = iterator.next();
arrayList.add(new WeightNode(next.getKey(),next.getValue()));
}
return arrayList;
}
/**
* 将包装成的list生成一个赫夫曼树
* @param arrayList
* @return
*/
public WeightNode getRoot(List<WeightNode> arrayList) {
while(arrayList.size() > 1) {
Collections.sort(arrayList);
WeightNode weightLeft = arrayList.get(0);
WeightNode weightRight = arrayList.get(1);
WeightNode parent = new WeightNode(weightLeft.weight+weightRight.weight);
parent.left = weightLeft;
parent.right = weightRight;
arrayList.remove(weightRight);
arrayList.remove(weightLeft);
arrayList.add(parent);
}
return arrayList.get(0);
}
public Map<Byte,String> gethuffmanCode(WeightNode root){
getHuffmanCode(root,"",sb);
//这个sb还是""没有变
System.out.println(sb.toString());
System.out.println(huffManCodes);
return huffManCodes;
}
/**
* 将给定结点下的所有叶子结点的对应的编码号作为string放入huffManCodes中
* @param node 结点
* @param code 是向左遍历还是向右遍历“0”是向左，“1”是向右
* @param sb 截止到上个结点处他的String
*/
public void getHuffmanCode(WeightNode node,String code,StringBuilder sb) {
if(node == null) return;
StringBuilder sb2 = new StringBuilder(sb);
sb2.append(code);
if(node.data == null) {
//向左递归
getHuffmanCode(node.left,"0",sb2);
//向右递归
getHuffmanCode(node.right,"1",sb2);
}else {
huffManCodes.put(node.data, sb2.toString());
System.out.print(sb2.toString());
}
}
/**
* 给我一个最原始的byte数组我返回给你一个赫夫曼byte
* (这个byte是将原来byte排序后转换成相应的赫夫曼编码的数组之后再将八位一个转换成byte而形成的数组)
* @param bytes 最原始的byte数组
* @return 赫夫曼编码形成之后转byte的byte数组
*/
public byte[] zip(byte[] bytes) {
StringBuilder strb = new StringBuilder();
Map<Byte, String> gethuffmanCode = gethuffmanCode(getRoot(getWeightNode(bytes)));
Iterator<Entry<Byte, String>> iterator = gethuffmanCode.entrySet().iterator();
while(iterator.hasNext()) {
Entry<Byte, String> next = iterator.next();
System.out.println(next);
}
for(byte b:bytes) {
strb.append(gethuffmanCode.get(b));
}
int len = (strb.length()+7) / 8;
byte[] huffManBytes = new byte[len];
int index = 0;
for(int i=0;i<strb.length();i += 8) {
if(i+8<strb.length())
huffManBytes[index] = (byte)Integer.parseInt(strb.substring(i, i+8),2);
else huffManBytes[index] = (byte)Integer.parseInt(strb.substring(i),2);
index++;
}
return huffManBytes;
}
/**
* 将一个byte 转成一个二进制的字符串
* @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
* @param byteOne 传入的 byte
* @return 是该b 对应的二进制的字符串，（注意是按补码返回）
*/
public String huffManBinaryTonomarl(boolean flag,byte byteOne) {
int temp = byteOne;
String str;
if(flag) {
temp |= 256;
}
str = Integer.toBinaryString(temp);
if (flag&&temp<0) {
return str.substring(str.length() - 8);
} else {
return str;
}
}
/**
* 给我一个最终存储形式的数组之后，我可以返回给你需要的做string 的byte数组；
* @param source 最终存储形式的byte数组
* @param huffManCodes 你的对应的赫夫曼编码集
* @return 解码后的byte数组，可以用来new string 来还原了；
*/
public byte[] unZip(byte[] source,Map<Byte,String> huffManCodes) {
StringBuilder sb = new StringBuilder();
//遍历数组中的每一个byte 得到用byte存储前的赫夫曼数组
for(int i=0;i<source.length;i++) {
byte b = source[i];
if(i==source.length-1)
sb.append(huffManBinaryTonomarl(false,b));
else sb.append(huffManBinaryTonomarl(true,b));
}
//用一个新的map将之前的key和val反过来
Map<String,Byte> result = new HashMap<>();
for(Map.Entry<Byte, String> entry:huffManCodes.entrySet()) {
result.put(entry.getValue(), entry.getKey());
}
//这是整个通过这赫夫曼的数组拿到编码成赫夫曼之前的数组
Byte byteOne;
boolean flag = true;
ArrayList<Byte> arr = new ArrayList<>();
System.out.println(sb.length());
for(int i=0;i<sb.length();) {
int count = 1;
flag = true;
while(flag) {
byteOne = result.get(sb.substring(i,i+count));
if(byteOne==null) {
count++;
}else {
arr.add(byteOne);
flag = false;
}
}
i += count;
}
byte[] b = new byte[arr.size()];
for(int i=0;i<arr.size();i++) {
b[i] = arr.get(i);
}
return b;
}
}
class WeightNode implements Comparable<WeightNode>{
public Byte data; //这个才是对应的数据
public WeightNode left;
public WeightNode right;
public int weight; //权重就是出现了几次
public WeightNode(int weight) {
this.weight = weight;
}
public WeightNode(byte data, int weight) {
this.data = data;
this.weight = weight;
}
public void preList() {
System.out.println(this);
if(this.left!=null) left.preList();
if(this.right!=null) right.preList();
}
@Override
public int compareTo(WeightNode o) {
//使node可以排序，这边的逻辑如果换了对应的上边的get也是需要换的；
return this.weight-o.weight;
}
@Override
public String toString() {
return "Node: ["+weight+"]";
}
}
=============================================================
插句话：怎么打印二叉树结构类似这种
点击这里：https://blog.csdn.net/weixin_45127611/article/details/105668479
这里继续：
其中需要注意的：
Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 186
at java.lang.AbstractStringBuilder.substring(AbstractStringBuilder.java:933)
at java.lang.StringBuilder.substring(StringBuilder.java:76)
at binaryTree.HuffmanCode.unZip(HuffmanCode.java:211)
at binaryTree.HuffmanCode.main(HuffmanCode.java:44)
原因我们一步一步分析： 按理说，我们给出的赫夫曼编码形式的（java中byte存储的是对应的补码）
000001000110001110110010111001101011011111001110101110111111
在我们的map中能够找到唯一的与之对应的key并且在循环的时候总是能够到最后一个位置完全匹配完成
32=01
97=100
100=111010
101=1111
104=111011
105=101
106=00111
107=1100
108=000
111=0010
114=00110
117=11010
118=11011
121=11100
对他进行编码 [-88, -71, -24, -71, -24, -71, -23, -26, -29, -47, 60, 45, 34, -25, -79, 60, -36, 120, 90, 97, -67, 23, -71, 1]
可是这里我们可以发现，当最后不足8个字符的时候我们进行编码例如01得到的是 1 再将1进行解码得到的结果也是 1 而正确的应该是 01，所以得到的结果跟我们想要的不一致；这样就找到了问题的来源，如果解决呢，这里我提供两个思路：
Integer.toBinaryString((byteOne & 0xFF) + 0x100).substring(1)，如果看不懂可以参考文章：点击这里
但是我没有用java实现第二种方式，不知道有没有问题，下面贴出第一种解决办法的代码：
package binaryTree;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import org.junit.Test;
/***
* 这不是一个完整的赫夫曼编码（解码不太正确）
* 没有实现文件压缩和解压（主要是因为解码有时候会报错）
* 这个实现byte类型转换成对应二进制string的方法不太好而且网上方法还没有这个好
* @author 杰夫·王盖茨
*
*/
public class HuffmanCode {
private Map<Byte,String> huffManCodes ;
private StringBuilder sb;
private int leng; //用来记录如果最后一个byte不满八位具体是多少位
public HuffmanCode() {
huffManCodes = new HashMap<>();
sb = new StringBuilder();
}
public static void main(String[] args) {
String s = "i like like like java do you like a java you are lihai";
byte[] bytes = s.getBytes();
HuffmanCode huffmanCode = new HuffmanCode();
/*
* WeightNode root = huffmanCode.getRoot(huffmanCode.getWeightNode(bytes)); //
* root.preList(); huffmanCode.getHuffmanCode(root, "", huffmanCode.sb);
* Iterator<Entry<Byte, String>> iterator =
* huffmanCode.huffManCodes.entrySet().iterator(); while(iterator.hasNext()) {
* Entry<Byte, String> next = iterator.next(); System.out.println(next); }
* huffmanCode.gethuffmanCode(root); Iterator<Entry<Byte, String>> iterator1 =
* huffmanCode.huffManCodes.entrySet().iterator(); while(iterator.hasNext()) {
* Entry<Byte, String> next = iterator1.next(); System.out.println(next); }
*/
byte[] zip = huffmanCode.zip(bytes);
System.out.println(Arrays.toString(zip));
byte[] unZip = huffmanCode.unZip(zip, huffmanCode.huffManCodes);
System.out.println(new String(unZip));
}
/**
* 将byte【】 统计重复byte之后得到对应的data和权重并且将他们包装成list
* @param bytes
* @return
*/
public List<WeightNode> getWeightNode(byte[] bytes) {
HashMap<Byte, Integer> hashMap = new HashMap<>();
for(byte b : bytes) {
if(hashMap.get(b)==null) {
hashMap.put(b, 1);
}else {
hashMap.replace(b, hashMap.get(b)+1);
}
}
ArrayList<WeightNode> arrayList = new ArrayList<>();
Iterator<Entry<Byte, Integer>> iterator = hashMap.entrySet().iterator();
while(iterator.hasNext()) {
Entry<Byte, Integer> next = iterator.next();
arrayList.add(new WeightNode(next.getKey(),next.getValue()));
}
return arrayList;
}
/**
* 将包装成的list生成一个赫夫曼树
* @param arrayList
* @return
*/
public WeightNode getRoot(List<WeightNode> arrayList) {
while(arrayList.size() > 1) {
Collections.sort(arrayList);
WeightNode weightLeft = arrayList.get(0);
WeightNode weightRight = arrayList.get(1);
WeightNode parent = new WeightNode(weightLeft.weight+weightRight.weight);
parent.left = weightLeft;
parent.right = weightRight;
arrayList.remove(weightRight);
arrayList.remove(weightLeft);
arrayList.add(parent);
}
return arrayList.get(0);
}
public Map<Byte,String> gethuffmanCode(WeightNode root){
getHuffmanCode(root,"",sb);
//这个sb还是""没有变
System.out.println(sb.toString());
System.out.println(huffManCodes);
return huffManCodes;
}
/**
* 将给定结点下的所有叶子结点的对应的编码号作为string放入huffManCodes中
* @param node 结点
* @param code 是向左遍历还是向右遍历“0”是向左，“1”是向右
* @param sb 截止到上个结点处他的String
*/
public void getHuffmanCode(WeightNode node,String code,StringBuilder sb) {
if(node == null) return;
StringBuilder sb2 = new StringBuilder(sb);
sb2.append(code);
if(node.data == null) {
//向左递归
getHuffmanCode(node.left,"0",sb2);
//向右递归
getHuffmanCode(node.right,"1",sb2);
}else {
huffManCodes.put(node.data, sb2.toString());
System.out.print(sb2.toString());
}
}
/**
* 给我一个最原始的byte数组我返回给你一个赫夫曼byte
* (这个byte是将原来byte排序后转换成相应的赫夫曼编码的数组之后再将八位一个转换成byte而形成的数组)
* @param bytes 最原始的byte数组
* @return 赫夫曼编码形成之后转byte的byte数组
*/
public byte[] zip(byte[] bytes) {
StringBuilder strb = new StringBuilder();
Map<Byte, String> gethuffmanCode = gethuffmanCode(getRoot(getWeightNode(bytes)));
Iterator<Entry<Byte, String>> iterator = gethuffmanCode.entrySet().iterator();
while(iterator.hasNext()) {
Entry<Byte, String> next = iterator.next();
System.out.println(next);
}
for(byte b:bytes) {
strb.append(gethuffmanCode.get(b));
}
int len = (strb.length()+7) / 8;
byte[] huffManBytes = new byte[len];
int index = 0;
leng = strb.length() % 8;
for(int i=0;i<strb.length();i += 8) {
if(i+8<strb.length())
huffManBytes[index] = (byte)Integer.parseInt(strb.substring(i, i+8),2);
else {System.out.println("这里"+i+strb.substring(i));huffManBytes[index] = (byte)Integer.parseInt(strb.substring(i),2);}
index++;
}
return huffManBytes;
}
/**
* 将一个byte 转成一个二进制的字符串
* @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
* @param byteOne 传入的 byte
* @return 是该b 对应的二进制的字符串，（注意是按补码返回）
*/
public String huffManBinaryTonomarl(boolean flag,byte byteOne) {
int temp = byteOne;
String str;
if(flag) {
temp |= 256;
}
str = Integer.toBinaryString(temp);
if(temp<0) return str.substring(str.length() - 8);
if (flag) {
return str.substring(str.length() - 8);
} else {
while(str.length()<leng) {
str = "0" + str;
}
return str;
}
}
/**
* 给我一个最终存储形式的数组之后，我可以返回给你需要的做string 的byte数组；
* @param source 最终存储形式的byte数组
* @param huffManCodes 你的对应的赫夫曼编码集
* @return 解码后的byte数组，可以用来new string 来还原了；
*/
public byte[] unZip(byte[] source,Map<Byte,String> huffManCodes) {
StringBuilder sb = new StringBuilder();
//遍历数组中的每一个byte 得到用byte存储前的赫夫曼数组
for(int i=0;i<source.length;i++) {
byte b = source[i];
if(i==source.length-1)
sb.append(huffManBinaryTonomarl(false,b));
else sb.append(huffManBinaryTonomarl(true,b));
}
//用一个新的map将之前的key和val反过来
Map<String,Byte> result = new HashMap<>();
for(Map.Entry<Byte, String> entry:huffManCodes.entrySet()) {
result.put(entry.getValue(), entry.getKey());
}
//这是整个通过这赫夫曼的数组拿到编码成赫夫曼之前的数组
Byte byteOne;
boolean flag = true;
ArrayList<Byte> arr = new ArrayList<>();
System.out.println(sb.length());
for(int i=0;i<sb.length();) {
int count = 1;
flag = true;
while(flag) {
byteOne = result.get(sb.substring(i,i+count));
if(byteOne==null) {
count++;
}else {
arr.add(byteOne);
flag = false;
}
}
i += count;
}
byte[] b = new byte[arr.size()];
for(int i=0;i<arr.size();i++) {
b[i] = arr.get(i);
}
return b;
}
}
class WeightNode implements Comparable<WeightNode>{
public Byte data; //这个才是对应的数据
public WeightNode left;
public WeightNode right;
public int weight; //权重就是出现了几次
public WeightNode(int weight) {
this.weight = weight;
}
public WeightNode(byte data, int weight) {
this.data = data;
this.weight = weight;
}
public void preList() {
System.out.println(this);
if(this.left!=null) left.preList();
if(this.right!=null) right.preList();
}
@Override
public int compareTo(WeightNode o) {
//使node可以排序，这边的逻辑如果换了对应的上边的get也是需要换的；
return this.weight-o.weight;
}
@Override
public String toString() {
return "Node: ["+weight+"]";
}
}
解决方式二对应的动画演示，快速版
制作不易，欢迎点赞