上节我们学习赫夫曼编码的过程,这节我们来学习赫夫曼编码的逆操作---------->解码操作,由于我们对编码的过程了解了,那么解码的过程就很简单了,具体过程如何我们来看
还记得我们在上节编码最后的生成的字节数组,即:[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28],我们的目的是要使用赫夫曼编码进行解码最后得到原字符串即:String string = "i like like like java do you like a java",在整个此过程中是我们编码的逆过程,接下来我们直接用代码实现:
代码实现
整个实现的过程都是在上节的编码的基础上完成,包括一些公用的属性等
/**
* 将一个byte转成一个字符串
* @param flag 是否需要补高位,如果是true表示需要,false表示不需要
* @param b 传入的byte
* @return
*/
private static String byteToBitString(boolean flag,byte b){
//定义一个临时变量来保存我们传入的byte
int temp = b; //我们需要将byte转成int
//1.如果是正数的话我们需要补高位
if (flag){
temp |= 256; //按位与256 假设temp为1如 1 0000 0000 | 0000 0001 => 1 0000 0001
}
//返回的是temp对应的二进制的补码
String string = Integer.toBinaryString(temp);
//System.out.println(string);
if (flag){
return string.substring(string.length() -8);
}else {
return string;
}
}
上述方法的主要作用是将一个字节转为字符串的过程,该方法在解码的过程中用到,接着我们来看解码的代码编写:
/**
*
* @param huffmanCodes 赫夫曼编码表(map)
* @param huffmanCodeBytes 赫夫曼编码得到的字节数组
* @return 原字符串对应的数组
*/
private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanCodeBytes){
//1.首先我们先要得到huffmanCodeBytes所对应的二进制字符串,如:101010001011111111001...
//创建一个StringBuilder来拼接
StringBuilder sb = new StringBuilder();
for (int i = 0; i <huffmanCodeBytes.length ; i++) {
//判断是不是最后一个字节,如果是我们不需要补高位
boolean flag = (i == huffmanCodeBytes.length -1); //表示是最后一个
sb.append(byteToBitString(!flag,huffmanCodeBytes[i]));
}
//2.把字符串按照指定的赫夫曼编码进行解码
//2.1.首先我们将赫夫曼编码表(huffmanCodes)进行key和value的调换,由之前的 a =100,转为 100 = a
Map<String, Byte> map = new HashMap<>();
for (Map.Entry<Byte,String> entry : huffmanCodes.entrySet()){
map.put(entry.getValue(),entry.getKey());
}
//System.out.println(map);
//3.创建一个集合,用来存放我们的byte
List<Byte> list = new ArrayList<>();
//遍历我们的sb
for (int i = 0; i <sb.length() ;) {
//1.首先我们定义一个计数器来记录我们的i(指针)每次遍历的位置
int count = 1;
boolean flag = true;
//定义一个变量b来保存我们我们遍历到的字节
Byte b = null;
while (flag){
//假如去找第一个字节(每8位一个字节),如101010001011111111001...
//首次进入while循环时, i = 0 ,也就是i的指针指向上述字符串的1这个位置,这时候不满足让count往后移动,
// 但是我们的i还是保持不变也就是 i = 0 ,i +count = 0 + 2 =2 这个时候获取的字符串为 10,重复去找直到找到10101000
//递归获取strByte的值
//说明: 这里i不变,让count移动去匹配
String strByte = sb.substring(i, i + count);
//从上述步骤2中调换之后的map中去获取
b = map.get(strByte);
if (b ==null){ //表示没有匹配到,让count++
count ++;
}else { //表示匹配到了,跳出while循环
flag = false;
}
}
//将找到的字节b添加到list中
list.add(b);
i += count; //直接将i增加到count的位置处进行下一次的遍历
}
//到这里时我们的list中此刻是存放了所有的字符即"i like like like java do you like a java"
//将list中的数据放入到byte[]返回即可
byte[] bytes = new byte[list.size()];
for (int i = 0; i <bytes.length ; i++) {
bytes[i] = list.get(i);
}
return bytes;
上述代码就是解码的操作,代码注释很详细,想看的可以自己看看,我们先来总结下上述代码编写的一个思路:
- 1.首先我们需要将赫夫曼编码=[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]转成 转成赫夫曼编码对应的二进制字符串"101010001011111111001000101111111100100010111111110010010100110111000111000001 1011101000111100101000101111111100110001001010011011100"
- 2.将赫夫曼二进制字符串转成对应的赫夫曼编码对应的原始字符串:"i like like like java do you like a java"
其实大致思路分析就这两步,我们来测试一把,来看测试代码:
System.out.println("赫夫曼解码测试:");
byte[] sourceBytes = decode(huffmanCodes, huffmanCodeBytes);
System.out.println("原字符串sourceBytes="+ new String(sourceBytes));
测试结果如下图:
解码测试.png
从上述的测试结果来看证明了我们的思路和代码的编写是没有问题的,那么赫夫曼解码操作就到这里了,完整代码在Git:
