共计 11002 个字符，预计需要花费 28 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、赫夫曼编码字节
1、1 赫夫曼编码字节数组
1、2 赫夫曼编码压缩后的字节数组转换成二进制编码
1、3 赫夫曼解码
1、赫夫曼编码字节
1、1 赫夫曼编码字节数组
本篇文章是在 Java 版赫夫曼编码这篇文章的根底上写的，在 Java 版赫夫曼编码这篇文章中，咱们用“the virus mutated and became weaker and weaker”这句话生成了对应它的赫夫曼编码，再通过它的赫夫曼编码生成了对应的二进制编码：10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100（Java 版赫夫曼编码这篇文章通过赫夫曼编码取出的二进制编码算法有些谬误，所以 Java 版赫夫曼编码这篇文章取出的二进制编码不对）。“the virus mutated and became weaker and weaker”这句话如果间接转换为字节数组的话，那么字节数组的长度是 46；如果生成它对应的赫夫曼编码，再通过它的赫夫曼编码生成对应的二进制编码，通过它的二进制编码转换成字节数组的话，字节数组的长度又是多少呢？好，咱们先把
10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100
这一串二进制编码当作一串字符放进记事本统计它们的字符数，如图 1 所示；
图片
图 1
看图 1，字符串的长度是 173 个，咱们晓得一个字节占 8 位，所以咱们按 8 位二进制码压缩成一个整数，看能压缩多少个整数；173 / 8 = 21.625，就算它们是 22 个整数，当到第 168 个二进制码的时候，刚好能压缩到 21 个整数，当到第 169 个二进制码的时候，有余 8 位，只有 5 位，所以独自用 5 位二进制码压缩成一位整数；所以“the virus mutated and became weaker and weaker”这句话的赫夫曼编码字节数组的长度是 22。
好，咱们用代码验证“the virus mutated and became weaker and weaker”这句话的赫夫曼编码字节数组的长度是不是 22？
（1）写一个节点类 Node：
/**
- Node 实现 Comparable 是为了让 Node 对象继续排序 Collections 汇合排序
*/
public class Node implements Comparable<Node>{
private Byte data;// 寄存十进制的 Ascill 码，比 ‘a’ 字符，那么 Ascill 码就是 97
private int weight;// 权值
private Node left;// 左孩子
private Node right;// 右孩子
@Override
public int compareTo(Node arg0) {
// 从小到大排序
return this.weight - arg0.weight;}
public Node(Byte data, int weight) {
super();
this.data = data;
this.weight = weight;}
public Byte getData() {
return data;}
public Node getLeft() {
return left;}
public void setLeft(Node left) {
this.left = left;}
public Node getRight() {
return right;}
public void setRight(Node right) {
this.right = right;}
public int getWeight() {
return weight;}
}
（2）创立一个实现将一大串二进制编码压缩成字节数组的类 Test :
public class Test {
Node root;
// 保留”通过赫夫曼树编码表取出的二进制编码“String s;
// 拼接赫夫曼树的节点的门路，节点的左门路用“0”示意，右门路用“1”示意
StringBuilder sb = new StringBuilder();
Map<Byte,String> huffumanCodes = new HashMap<Byte,String>();
public static void main(String[] args) {
String s = "the virus mutated and became weaker and weaker";
byte[] bs = s.getBytes();
Test test = new Test();
byte[] bytes = test.huffumanZip(bs);
System.out.println("压缩后的字节数组：" + Arrays.toString(bytes));
System.out.println("压缩后的字节数组长度：" + bytes.length);}
private byte[] huffumanZip(byte[] bs) {
List<Node> list = getNode(bs);
// 创立赫夫曼树
root = createHuffmanTree(list);
// 生成赫夫曼编码表，将 赫夫曼编码表 寄存到 huffumanCodes 中
getCodes(root, "", sb);
/**
* 该办法通过赫夫曼编码失去对应的二进制编码，* 最初通过压缩二进制编码失去 对应的赫夫曼编码字节数组
*/
byte[] bytes = zip(bs,huffumanCodes);
// 对应的赫夫曼编码字节数组
return bytes;}
/**
- 该办法通过赫夫曼编码失去对应的二进制编码，
- 最初通过压缩二进制编码失去 对应的赫夫曼编码字节数组
- */
private byte[] zip(byte[] bytes,Map<Byte, String> heffumanCodes) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < bytes.length; i++) {byte b = bytes[i];
sb.append(heffumanCodes.get(b));
}
s = sb.toString();
System.out.println("s =" + s);
int length = 0;
if (sb.length() % 8 == 0) {length = sb.length() / 8;
} else {length = sb.length() / 8 + 1;
}
/**
* 创立压缩后的 byte 数组
*/
byte[] bytes2 = new byte[length];
/**
* 记录 bytes2 的索引
*/
int num = 0;
for (int i = 0; i < sb.length(); i += 8) {
String stringByte ;
if (i + 8 >= sb.length()) {stringByte = sb.substring(i,sb.length());
} else {stringByte = sb.substring(i,i + 8);
}
bytes2[num] = (byte) Integer.parseInt(stringByte, 2);
num++;
}
return bytes2;}
// 生成赫夫曼编码表
/**
- @param node 传入的节点
- @param code 节点的左门路用“0”示意，右门路用“1”示意
- @param sb 拼接 code
- @return
*/
private void getCodes(Node node,String code,StringBuilder sb) {
StringBuilder sb2 = new StringBuilder(sb);
// 将 code 退出到 sb2 中
sb2.append(code);
if (node != null) {
// 非叶子节点
if (node.getData() == null) {
// 向左递归解决
getCodes(node.getLeft(), "0", sb2);
// 向右递归解决
getCodes(node.getRight(), "1", sb2);
// 是叶子节点
} else {huffumanCodes.put(node.getData(), sb2.toString());
}
}}
private List<Node> getNode(byte[] bs) {
ArrayList<Node> list = new ArrayList<Node>();
// 统计 byte 呈现的次数
Map<Byte,Integer> map = new HashMap<Byte,Integer>();
for (int i = 0; i<bs.length; i++) {Integer count = map.get(bs[i]);
// 第一次寄存该字节
if (count == null) {map.put(bs[i],1);
} else {map.put(bs[i], count + 1);
}
}
for (Map.Entry<Byte, Integer> entry : map.entrySet()) {Byte data = entry.getKey();
int weight = entry.getValue();
Node node = new Node(data,weight);
list.add(node);
}
return list;}
// 创立赫夫曼树
private Node createHuffmanTree(List<Node> list) {
while (list.size() > 1) {
// 排序，从小到大排序
Collections.sort(list);
// System.out.println("list =" + list);
/**
* 这个肯定是权值最小的节点
*/
Node minNode = list.get(0);
/**
* 除了 minNode 节点，该节点就是权值最小的节点，只是该节点比 minNode 节点大，比其余节点都小
*/
Node secondMinNode = list.get(1);
/**
* 构建一棵新的二叉树
*/
Node parentNode = new Node(null,minNode.getWeight()
+ secondMinNode.getWeight());
parentNode.setLeft(minNode);
parentNode.setRight(secondMinNode);
/**
* 从 list 汇合中删除 2 棵曾经构建成一棵二叉树的 2 个节点
*/
list.remove(minNode);
list.remove(secondMinNode);
/**
* 将新的二叉树的父节点退出到 list 汇合中
*/
list.add(parentNode);
}
/**
* 构建完哈夫曼树后，list 汇合中的第一个节点必定是根节点
*/
return list.get(0);
}
}
日志打印如下所示：
图片
果然，“the virus mutated and became weaker and weaker”这句话的赫夫曼编码字节数组的长度是 22；这里咱们说一下程序的大略思路：先将 “the virus mutated and became weaker and weaker” 这句话间接转换成字节数组（我给它取名叫 B1），B1 中元素的 int 值就是 Ascill 码的十进制数，通过 HashMap 来统计 B1 中元素呈现的次数，也就是每个字节元素的 Ascill 码呈现的次数；统计完后，就将每个字节元素的 Ascill 码呈现的次数作为节点的权值创立节点，并将节点保留到 ArrayList 中；再通过 ArrayList 中的数据创立一棵赫夫曼树，用赫夫曼树生成对应的赫夫曼编码表（就是一个 Map 汇合，key 是字符十进制的 Ascill 码，value 是叶子节点的二进制模式的权值），又再通过赫夫曼编码表取出叶子节点二进制模式的权值并拼接成一串字符串，用 8 位为一个单位（将字符按 8 串取余，余数如果大于 0 小于 8，那么将余数独自作为一个字节）的模式将字符串压缩成一个字节数组；最初赫夫曼编码字节数组的压缩就功败垂成了，这样就节俭了字节数组的空间。
1、2 赫夫曼编码压缩后的字节数组转换成二进制编码
在下面的案例中，咱们将“the virus mutated and became weaker and weaker”这句话最终转变成了赫夫曼编码压缩后的字节数组 {-108, 122, -92, -31, 46, -20, -91, -49, -118, -11, 20, -36, -17, 126, -113, 97, -14, -67, 69, 30, -61, 28}；咱们这里将赫夫曼编码压缩后的字节数组转换成二进制编码，也就是将赫夫曼编码压缩后的字节数组 {-108, 122, -92, -31, 46, -20, -91, -49, -118, -11, 20, -36, -17, 126, -113, 97, -14, -67, 69, 30, -61, 28} 转换成原先通过赫夫曼编码失去的一大串的二进制编码
10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100
赫夫曼编码压缩后的字节数组转换成二进制编码的思路是这样的；
（1）用 for 循环遍历压缩后的字节数组，将每个字节转换成对应的长度为 8 的字符串，字符串外面的内容肯定是 0 和 1；当然字符串的长度不肯定是 8，当最初一个字节转换成字符串的时候长度有可能比 8 还小。
（2）字节转换成字符串的过程中，如果不是最初一个字节，每个字节的 10 进制 Ascill 码必须或上 256，至于为什么要或上 256，能够看代码实现的正文。
（3）字节转换成字符串的过程中，如果不是最初一个字节，将切割字符串的后 8 位进去并返回；如果是最初一个字节且最初一个字节的 10 进制 Ascill 码大于 0，不必切割字符串，间接把字符串返回。
（4）每个字节转成字符串后，将每个字符串拼接起来，这样就将压缩后的字节数组转换成一大串的二进制编码。
好，咱们在下面案例的根底上实现一把代码；
（1）在 Test 类中增加 decodeBinaryStr(byte[] encodeBytes) 办法和 decodeDecimal(boolean isNeedSub, int encodeByte) 办法：
/**
- 将压缩后的字节数组反编译为二进制数字串
- @param encodeBytes
- @return 二进制数字串
*/
private String decodeBinaryStr(byte[] encodeBytes) {
StringBuilder sb = new StringBuilder();
boolean isNeedSub = true;
for (int i = 0; i < encodeBytes.length; i++) {if (i == encodeBytes.length - 1 && encodeBytes[i] > 0) {isNeedSub = false;}
sb.append(decodeDecimal(isNeedSub, encodeBytes[i]));
}
return sb.toString();}
/**
- 转换
- @param isNeedSub 是否须要截取
- @param encodeByte 以后须要转换的数据
- @return
*/
private String decodeDecimal(boolean isNeedSub, int encodeByte) {
String str = "";
/*1、为什么要 encodeByte |= 256？当 encodeByte 是正数的时候，Integer.toBinaryString(encodeByte) 失去的是 32 位的字符串
能够执行 str.substring(str.length() - 8) 不报错；当 encodeByte 是负数的时候，Integer.toBinaryString(encodeByte) 失去不肯定是
大于等于 8 位的字符串，执行 str.substring(str.length() - 8) 就有可能报错，就比方负数 7，执行 Integer.toBinaryString(7)就失去
"111"，"111".substring("111".length() - 8)就会报错；如果 7 |= 256 就等于 363，再执行 Integer.toBinaryString(363) 就失去
"100000111"，再执行 "100000111".substring("100000111".length() - 8) 就失去 "00000111"，目标是 7 转换成二进制的时候，如果不够 8 位，就用 0 在后面补够 8 位嘛
2、256 的二进制为: 1 0000 0000, 无论工作数字与 256 进行或运算后, 相对能保障第九位的 1, 则后八位无效
转换实现后, 截取后八位作为无效数据
3、留神: 最初一位须要解决的数据不肯定满 8 位, 所以不满八位的状况下肯定为负数, 须要原样解决, 所以 isNeedSub 为 false
*/
if (isNeedSub) {encodeByte |= 256;}
// 返回 encodeByte 对应的二进制补码
str = Integer.toBinaryString(encodeByte);
if (isNeedSub) {str = str.substring(str.length() - 8);
}
return str;}
（2）在 Test 类中程序入口增加相应的代码：
public static void main(String[] args) {
String s = "the virus mutated and became weaker and weaker";
byte[] bs = s.getBytes();
Test test = new Test();
byte[] bytes = test.huffumanZip(bs);
System.out.println("压缩后的字节数组：" + Arrays.toString(bytes));
System.out.println("压缩后的字节数组长度：" + bytes.length);
String decodeBinaryStr = test.decodeBinaryStr(bytes);
String result = test.s.equals(decodeBinaryStr) ? "雷同" : "不雷同";
System.out.println("通过赫夫曼编码表取出的二进制编码与解压后的二进制编码是否雷同？" + result);}
日志打印如下所示：
图片
咱们看到，通过赫夫曼编码表取出的二进制编码与字节数组转换成二进制编码是雷同的，证实压缩后的字节数组转换成二进制编码胜利。
1、3 赫夫曼解码
咱们在本篇文章的“赫夫曼编码压缩后的字节数组转换成二进制编码”案例中，将赫夫曼编码压缩后的字节数组 {-108, 122, -92, -31, 46, -20, -91, -49, -118, -11, 20, -36, -17, 126, -113, 97, -14, -67, 69, 30, -61, 28}，转换成原先通过赫夫曼编码失去的一大串的二进制编码
10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100
咱们要用原先通过赫夫曼编码失去的一大串的二进制编码 10010100011110101010010011100001001011101110110010100101110011111000101011110101000101001101110011101111011111101000111101100001111100101011110101000101000111101100001111100 解码成相应的文本内容，也就是赫夫曼解码。
它的实现思路是这样的：
（1）将赫夫曼编码表（映射关系是 <Byte,String>）的映射关系反过来并保留在另外一个汇合中（我叫它 gather 吧，gather 的映射关系是 <String,Byte>）。
（2）用 for 循环遍历字节数组解压进去的二进制编码字符串，遍历进去的二进制编码字符串昨为 gather 的 key，gather 通过 key 取出失去一个 Byte，如果这个 Byte 不为空，证实拿到这个解码的字符的字节胜利，就将其保留到一个 List 汇合中。
（3）将 List 汇合中的 Byte 元素保留到一个 byte 数组中。
（4）将 byte 数组转换成一个字符串，最终解码相应的文本内容。
如果它的实现思路看不懂，那么就看上面的代码实现，再回看它的实现思路就懂了。
好，咱们当初代码实现一把：
（1）在 Test 类中增加 decodeContent(String binaryStr, Map<Byte, String> pathMap) 办法和 doDecodeContent(String binaryStr, Map<String, Byte> pathByteMap) 办法；
/**
- 依据解压后的二进制编码串和赫夫曼编码表失去原始的字符串内容
* - @param binaryStr 压缩后的字节数组转换成的二进制编码串
- @param pathMap 赫夫曼编码表
- @return
*/
private byte[] decodeContent(String binaryStr, Map<Byte, String> pathMap) {
// 将映射关系倒换过去，即保留的 <key,value> 变成保留 <value,key>
Map<String, Byte> pathByteMap = reverseMap(pathMap);
// 依据门路一段段截取二进制数字串, 并拼凑为无效的 byte 码
byte[] resultBytes = doDecodeContent(binaryStr, pathByteMap);
return resultBytes;}
/**
- 反编译为最终须要的字节码
- @param binaryStr 压缩后的字节数组转换成的二进制编码串
- @param pathByteMap 赫夫曼编码表 (<Byte,String>) 的倒映射表(<String, Byte>)
- @return
*/
private byte[] doDecodeContent(String binaryStr, Map<String, Byte> pathByteMap) {
// 截取的每一个数字, 增加到汇合中
List<Byte> lstBytes = new ArrayList<>();
for (int i = 0; i < binaryStr.length();) {
int count = 1;
while(true) {
// 1、以 count 作为一个标识位, 始终向后挪动；举例：假如 binaryStr = "1001010001111010101001001110000..."
// 那么就用 count 一个个往后挪动一位，直到匹配到 pathByteMap 的 key，currStr 就有可能是 "1"、"10"、"100"...
String currStr = binaryStr.substring(i, i + count);
// 如果门路到字符映射中, 蕴含该门路, 则匹配胜利; 举例：假如 binaryStr = "1001010001111010101001001110000...",
// 假如 pathByteMap 的内容是 <{"1001",116},{"01000",104}...>
// 当 key = "1"、"10"、"100" 时拿进去的 Byte 那就是为空，key = "1001" 时，Byte 就不为空，则证实匹配胜利，查找到这个字节
if (null != pathByteMap.get(currStr)) {
// 将 字节增加到 lstBytes 汇合中，也就是将字符的 10 进制 Ascill 码增加到 lstBytes 汇合中
lstBytes.add(pathByteMap.get(currStr));
break;
}
count++;
}
// 匹配胜利后, i 间接进 count 位, 进行下一位字节查找；举例假如 binaryStr = "1001010001111010101001001110000...",
// 假如 pathByteMap 的内容是 <{"1001",116},{"01000",104}...>，// 当执行 binaryStr.substring(0, 5)这条语句的时候就找到了第一个字节(从 "1001" 从 pathByteMap 拿到一个字节)
// 那么查找下一个字节的 count 就从 5 开始
i += count;
}
// 将 List 汇合的 Byte 转换为 byte 数组保留
byte[] bytes = new byte[lstBytes.size()];
int index = 0;
for (Byte currByte : lstBytes) {bytes[index++] = currByte;
}
return bytes;}
（2）在 Test 类中的程序入口处调用略微做一下批改：
public static void main(String[] args) {
String s = "the virus mutated and became weaker and weaker";
byte[] bs = s.getBytes();
Test test = new Test();
byte[] bytes = test.huffumanZip(bs);
System.out.println("压缩后的字节数组：" + Arrays.toString(bytes));
System.out.println("压缩后的字节数组长度：" + bytes.length);
String decodeBinaryStr = test.decodeBinaryStr(bytes);
System.out.println("decodeBinaryStr =" + decodeBinaryStr);
String result = test.s.equals(decodeBinaryStr) ? "雷同" : "不雷同";
System.out.println("通过赫夫曼编码表取出的二进制编码与解压后的二进制编码是否雷同？" + result);
byte[] decodeByte = test.decodeContent(decodeBinaryStr, test.huffumanCodes);
System.out.println("解压后的数据：" + new String(decodeByte));}
日志打印如下所示：
图片
看见了没，解压后的数据和压缩前的截然不同，哈哈。
