记录生活中的点点滴滴

0%

赫夫曼树

发表于 Valine：

这个赫夫曼树，我整了两天差不多算是搞定了。这篇文章主要介绍：

  • 赫夫曼树的构建
  • 赫夫曼编码
  • 借助赫夫曼树进行文件的压缩与解压缩

赫夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度( wpl )达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmanTree)。

赫夫曼树的构建

给你一个数列 {13,7,8,3,29,6,1}，要求转成一颗赫夫曼树

为之奈何？步骤如下：

  1. 从小到大进行排序，将每一个数据，每个数据都是一个节点，每个节点可以看成是一棵最简单的二叉树
  2. 取出根节点权值最小的两棵二叉树
  3. 组成一棵新的二叉树，该新的二叉树的根节点的权值是前面两棵二叉树根节点权值的和
  4. 新的二叉树节点再和剩余的节点排序，再找到最小的两棵二叉树再进行组合，依次循环，得到一棵赫夫曼树

最终形成的二叉树如下，叶子节点就是我们的数列节点：

我们先要定义一个 Node 节点类，它有左指针、右指针和权值三个属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Node节点类
class Node implements Comparable<Node>{
    public Node left;
    public Node right;
    public int val;
    public Node(int val){
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.val-o.val;
    }
}

构建方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//传入一个数组，构建赫夫曼树，返回根节点
public static Node createHuffman(int[] arr) {
    //遍历arr，将每一个数构造成Node节点放在list中
    ArrayList<Node> nodes = new ArrayList<>();
    for (int t : arr) {
        nodes.add(new Node(t));
    }
    //退出的条件是list里面只剩下一个根节点
    while (nodes.size()>1){
        //先排序
        Collections.sort(nodes);
        //获取前两个最小的结点
        Node first = nodes.get(0);
        Node second = nodes.get(1);
        //创建sum结点
        Node sum = new Node(first.val+second.val);
        sum.left = first;
        sum.right = second;
        //添加sum结点，删除first和second结点
        nodes.add(sum);
        nodes.remove(first);
        nodes.remove(second);
    }
    return nodes.get(0);
}

代码写完之后，我们可以在 main 方法中进行debug，看看是否正确。

赫夫曼编码

我们会了构建赫夫曼树之后，还需要对它们进行编码，即赫夫曼编码。

我们的文件什么的都是二进制文件我，我们站在字节上，它们都是一个个字节。

编码之后要返回什么？肯定是一个 HashMap 呀，它的键是什么类型我们先不管，它的值肯定是字符串类型的，只有0和1构成的字符串。这个不难理解，关键值怎么办？是一个数，那肯定，但是我们往后面继续做的时候，对文件进行压缩解压缩什么的，操作的是什么？

是字节，所以，干脆我们现在就用字节作为这个 HashMap 的键，每一个 byte 对应的赫夫曼编码就是它的值。

所以Node节点我们要改一下，给它增加一个字节成员属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//Node节点类
class Node implements Comparable<Node>{
    public Node left;
    public Node right;
    public Byte b;
    public int val;
    public Node(Byte b,int val){
        this.b = b;
        this.val = val;
    }
    @Override
    public String toString() {
        return "Node{" +
                "b=" + b +
                ", val=" + val +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        return this.val-o.val;
    }
}

下面我们写这个赫夫曼编码的方法，传入的是构建的赫夫曼数的根节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//给一个赫夫曼树，返回编码，用hashMap<Byte,string>返回
static HashMap<Byte,String> haffmanMap = new HashMap<>();
public static HashMap<Byte,String> getCodes(Node root){
    if(root==null)
        return null;
    StringBuffer sb = new StringBuffer();
    getCodes(root.left,"0",sb);
    getCodes(root.right,"1",sb);
    return haffmanMap;
}
//重载方法，便于递归调用
public static void getCodes(Node node, String s, StringBuffer sb) {
    if(node==null)//node为空则不处理
        return;
    //重新整一个sb，不然就一直会改变sb，直接爆炸起飞
    StringBuffer sb2 = new StringBuffer(sb);
    sb2 = sb2.append(s);
    if(node.b!=null){//叶子节点
        haffmanMap.put(node.b, sb2.toString());
    }else {
        getCodes(node.left,"0",sb2);
        getCodes(node.right,"1",sb2);
    }
}

借助赫夫曼树对文件压缩

下面我们做一个案例，我特马搞了两天这个破玩意。

就是完成文件的压缩与解压缩，完成主要的两个方法：压缩与解压缩

它们都是传入两个 File 参数，一个完成压缩，另一个完成解压缩。

先看压缩文件，下面写一下步骤：

  1. 文件输入流读取文件的 byte 数组
  2. getByte(bytes) 方法获取每个字节及其个数，返回的是 HashMap
  3. 根据上面的 HashMap 构建赫夫曼树，获取根节点 root
  4. 根据 root 使用 getCodes(root) 方法获取赫夫曼编码表（haffmanMap），这个也是 HashMap
  5. 利用文件字节数组（bytes）和赫夫曼编码表（haffmanMap）得到采用赫夫曼编码后的字符串 sb
  6. 将压缩后的字符串 sb 用 toByte(sb) 方法转换成新的字节数组 haffmanBytes
  7. 将新的字节数组（haffmanBytes）和赫夫曼编码表（haffmanMap）写入到文件输出流中，压缩完成

下面写每个对应的方法：

读取文件字节流

我们看看我们总的步骤，其实我们做这些东西的目的就是根据读取的字节数组得到另一个新的字节数组，把它写入到输出流，那个赫夫曼编码表我们会直接写在类中。所以我们完全可以再进行进一步的抽象，再抽象出一个方法compressionByte ，它传入一个字节数组，返回赫夫曼编码的字节数组。

所以压缩的主方法里面可以这样写，获取到文件字节流之后，直接调用 compressionByte ，然后将返回的字节还有类的静态成员赫夫曼编码表（haffmanMap）都写入到输出流中，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//使用赫夫曼编码对文件进行压缩
public static void compression(File file,File newFile){
    FileInputStream fis = null;
    FileOutputStream fos =null;
    BufferedInputStream bis = null;
    ObjectOutputStream oos = null;
    try {
        fis = new FileInputStream(file);
        int len = fis.available();//源文件字节数
        fos = new FileOutputStream(newFile);
        bis = new BufferedInputStream(fis);
        oos = new ObjectOutputStream(fos);
        byte[] bytes = new byte[len];
        //缓冲流读取文件，读入到bytes数组中
        bis.read(bytes);

        //传入byte数组，返回赫夫曼编码的byte数组
        byte[] haffmanBytes = compressionByte(bytes);

        //将压缩形成的赫夫曼byte数组写入到输出流中
        oos.writeObject(haffmanBytes);
        //将赫夫曼编码map也写入到输出流中
        oos.writeObject(haffmanMap);

        oos.flush();//刷新输出流
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        try {
            oos.close();
            bis.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

下面我们写 compressionByte 方法，我们把我们上面的步骤都抽象成方法，在这个 compressionByte 方法中按步骤调用即可，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//传入一个字符数组，返回赫夫曼编码的字符数组
public static byte[] compressionByte(byte[] bytes){

    //2.获取每个字节及其个数
    HashMap<Byte, Integer> map = getByteCount(bytes);

    //3.根据每个字节及其个数（hashmap）创建赫夫曼树
    Node root = createHuffman(map);

    //4.获取赫夫曼编码
    getCodes(root);

    //5.得到采用赫夫曼编码后的字符串
    String sb = getHaffmanString(bytes);

    //6.将压缩后的二进制字符串001100100101...转换成新的字节数组
    byte[] haffmanBytes = toByte(sb.toString());

    //返回新的字节数组
    return haffmanBytes;
}

下面我们再接着写对应的方法。

获取字节对应个数

就是遍历字节数组，如果我们的 HashMap 中不存在则添加，存在则将它的值加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
//传入一个字节数组，返回每个字符及其个数（hashmap）
public static HashMap<Byte,Integer> getByteCount(byte[] bytes){
    HashMap<Byte, Integer> hashMap = new HashMap<>();
    for (byte b : bytes) {
        if(!hashMap.containsKey(b)){//如果不包含,map添加
            hashMap.put(b,1);
        }else {//如果包含，对应value值加1
            Integer integer = hashMap.get(b);
            hashMap.replace(b,integer+1);
        }
    }
    return hashMap;
}

构建赫夫曼树

根据上面我们获得的 HashMap，然后创建赫夫曼树，将它的根节点返回：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//根据每个字节及其个数（hashmap）创建赫夫曼树
public static Node createHuffman(HashMap<Byte,Integer> hashMap){
    //遍历hashMap，将每一个数构造成Node节点放在list中
    ArrayList<Node> nodes = new ArrayList<>();
    hashMap.forEach((k,v)->{
        nodes.add(new Node(k,v));
    });
    while (nodes.size()>1){
        //先排序
        Collections.sort(nodes);
        //获取前两个最小的结点
        Node first = nodes.get(0);
        Node second = nodes.get(1);
        //创建sum结点
        Node sum = new Node(null,first.val+second.val);
        sum.left = first;
        sum.right = second;
        //添加sum结点，删除first和second结点
        nodes.add(sum);
        nodes.remove(first);
        nodes.remove(second);
    }
    return nodes.get(0);
}

获取赫夫曼编码

我们构建玩赫夫曼树之后，根据它的根节点对每一个字节进行赫夫曼编码，我们要先在类中定义一个静态的 HashMap<Byte,String> ，它就是我们最后要写入的赫夫曼编码表。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//给一个赫夫曼树，返回编码，用hashMap<Byte,string>返回
static HashMap<Byte,String> haffmanMap = new HashMap<>();
public static HashMap<Byte,String> getCodes(Node root){
    if(root==null)
        return null;
    StringBuffer sb = new StringBuffer();
    getCodes(root.left,"0",sb);
    getCodes(root.right,"1",sb);
    return haffmanMap;
}
//重载方法，便于递归调用
public static void getCodes(Node node, String s, StringBuffer sb) {
    if(node==null)//node为空则不处理
        return;
    //重新整一个sb，不然就一直会改变sb，直接爆炸起飞
    StringBuffer sb2 = new StringBuffer(sb);
    sb2 = sb2.append(s);
    if(node.b!=null){//叶子节点
        haffmanMap.put(node.b, sb2.toString());
    }else {
        getCodes(node.left,"0",sb2);
        getCodes(node.right,"1",sb2);
    }
}

得到采用赫夫曼编码后的字符串

得到赫夫曼编码表后，我们就可以根据这个编码表和之前获得的字节数组，重新对这些字节进行编码，返回编码后的字符串，下面就是这个方法的代码：就是先构造一个 StringBuffer，然后遍历字节数组，不断查询赫夫曼编码表，把对应的编码值追加到 StringBuffer 后面。

1
2
3
4
5
6
7
8
9
//根据字节数组和赫夫曼编码表得到编码后的字符串
public static String getHaffmanString(byte[] bytes) {
    StringBuffer sb = new StringBuffer();
    for (Byte b : bytes) {
        String s1 = haffmanMap.get(b);
        sb.append(s1);
    }
    return sb.toString();
}

将字符串转换成byte数组

有同学可能会想到，我们得到这个字符串之后如果直接就写到输出流不就行了，你可拉倒吧！

这个是字符串，每个01都是一个字节，这样反而比原来大的多，还压缩个锤子。

我们还要把这个字符串转换成字节数组，然后再写入到输出流。

所以我们还要完成最后一个 toByte 方法，它传入一个字符串，返回对应的字节数组。

但是其实蛮简单的，字符串每8个字符就能转换成一个字节，就是调个 Integer.parseInt(String s, int radix) 这个静态方法，第二个参数写成2即可。最后截取的时候还要留意不要截取多了，因为字符串的长度不一定是8的倍数，最后可能截不了8位这么多，我们得注意这个点。

我们可能会这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
public static byte[] toByte(String s){
    //等价于int len = s.length()%8==0 ? s.length()/8 : s.length()/8+1;
    int len = (s.length()+7)/8;//byte数组长度
    byte[] bytes = new byte[len];//要返回的byte数组
    int index = 0;//计数，第几个byte
    for (int i = 0,length=s.length(); i < length; i+=8) {
        //截取八位或最后不到八位
        String substring = (i+8)>length ? s.substring(i) : s.substring(i,i+8);
        //转换成byte类型
        bytes[index++] = (byte) Integer.parseInt(substring,2);
    }
    return bytes;
}

这样写确实没有问题。

但是特马的，解压缩的时候直接完蛋，我就是这个问题，给我整蒙了，我在解压缩的时候出了点错误，找它找了至少两个小时才发现，原来是这里存在一个小问题。

我们看看下面这样的情景（其实就是我出错的场景）：

字符串转字节数组，字符串的长度不是8的倍数，它的长度%8等于7。比如最后还剩 0000 011 这7位。它会变成字节3。但是我们解压缩的时候，会把3转成字符串 0000 0011，看到没？这里会多出一个0，其实不一定非得是多出一个0，因为我们不知道它本来的字符串长度是多少，这里是否会多0，还是多了多少个0，我们在解压缩的时候都不知道。那么译码的时候肯定会出错。

所以为之奈何？关键原因就是我们在解压缩的时候不知道最后一个字节是什么情况，对于每一个字节，我们都会把它们变成8位01的字符串，但是最后一个字节到底变成多少位，不知道。所以我们要解决这个问题，肯定要把这个数据传过去，解压缩的时候根据这个数据，进行截取。最好传的数据是 8-len%8 ，为什么？我们姑且称它为 j ，我们拿到这个 j 之后，在最后一位的时候直接用 substring(j) 方法截取就行了，它就是我们截取要开始的位置呗！

所以，我们约定最后返回的byte数组，也是我们写入到输出流中的byte数组，第一个字节中存放一个数，它不是真正的字节数据， 而是我们上面的那个 j 。解压缩的时候拿到这个 j ，从 bytes[1] 再开始相关操作，最后一位用这个 j 截取即可。

所以这个方法应该这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//将压缩后的二进制字符串 001100100101...转换成byte数组
public static byte[] toByte(String s){
    //等价于int len = s.length()%8==0 ? s.length()/8 : s.length()/8+1;
    int len = (s.length()+7)/8;//byte数组长度
    len = len+1;//数组长度加1
    byte[] bytes = new byte[len];//要返回的byte数组
    //第一位存放约定的截取位置
    bytes[0] = (byte) (8-s.length()%8);
    int index = 1;//计数，第几个byte
    for (int i = 0,length=s.length(); i < length; i+=8) {
        //截取八位或最后不到八位
        String substring = (i+8)>length ? s.substring(i) : s.substring(i,i+8);
        bytes[index++] = (byte) Integer.parseInt(substring,2);
    }
    return bytes;
}

至此，方法全部完成，我们在main方法中应该就可以直接调用 compression 方法就行了，还有一点就是对于小的文件可能压缩后的大小还要比本来文件还大，正常，因为我们除了字节数组，还写入了赫夫曼编码表。但当文件大了之后应该就不会出现这种情况了，我这边测试一个 111KB 的 txt文件压缩后的大小是 79KB，还是可以的。

下面再来写解压缩的方法，这个应该就简单了，啊，累的一批！坚持住

解压缩

先写步骤：

  1. 输入流读取 byte 数组及赫夫曼编码表 haffmanMap
  2. 因为我们要反查询，要将编码变反转，然后用 byteToString(bytes) 方法将bytes转换成我们之前那个字符串 sb
  3. 遍历 sb，根据赫夫曼反编码表，转成最本来的 byte 数组
  4. byte写入到输出流，解压缩就完成了，文件就又回来了

读取字节流及赫夫曼编码表

我们还是老样子，先看看这个解压缩的输入和输出，把它抽象出来。其实就是输入字节数组和赫夫曼编码表，输出一个字节数组。把它抽象为 reCompressionByte 方法，所以我们的解压缩的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//使用赫夫曼编码对文件进行解压缩
public static void reCompression(File file,File newFile){
    FileInputStream fis = null;
    FileOutputStream fos =null;
    ObjectInputStream ois = null;
    BufferedOutputStream bos = null;
    try {
        fis = new FileInputStream(file);
        fos = new FileOutputStream(newFile);
        ois = new ObjectInputStream(fis);
        bos = new BufferedOutputStream(fos);

        //先读取bytes数组
        byte[] bytes = (byte[]) ois.readObject();

        //读取赫夫曼编码map
        HashMap<Byte, String> reHaffmanMap = (HashMap<Byte, String>) ois.readObject();

        //传入赫夫曼编码的byte数组，返回本来的byte数组
        byte[] newBytes = reCompressionByte(bytes,reHaffmanMap);

        //将byte数组写入文件
        bos.write(newBytes);

        //刷新输入流
        bos.flush();
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } catch (ClassNotFoundException e) {
        e.printStackTrace();
    } finally {
        try {
            bos.close();
            ois.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}

我们再把后面的步骤抽象为方法，写入到 reCompressionByte 方法中，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//综合上面的方法，传入一个赫夫曼编码的字符数组和赫夫曼编码map，返回原来的字符数组
public static byte[] reCompressionByte(byte[] bytes, HashMap<Byte, String> reHaffmanMap) {
    //先将myMap转过来，后续我们要根据字符串找到对应的字符
    HashMap<String, Byte> reComToBytes = new HashMap<>();
    reHaffmanMap.forEach((k,v)->{
        reComToBytes.put(v,k);
    });

    //将bytes数组转换成压缩时转成的字符串sb
    String sb = reComByteToString(bytes);

    //根据传入字符串sb和反转的haffmanMap，返回原来的byte数组,用ArrayList形式返回
    ArrayList<Byte> byteList = reComToBytes(sb, reComToBytes);

    //将ArrayList<Byte>转成数组形式的byte
    byte[] resbytes = ArrListToArr(byteList);
    return resbytes;
}

先将赫夫曼编码表反转，然后得到字符串，再得到数组，将数组返回。

对了，中间我们返回原来的byte数组时，不能直接用数组，要先用 ArrayList 接受，后面再调用 ArrListToArr 方法将它转换成数组。

将字节数组转换成字符串

我们先写一个将一个字节转换成字符串的方法：

1
2
3
4
5
6
7
8
//将一个byte转换成一个二进制的字符串,补到8位
public static String byteToString(byte b){
    int temp = b;
    temp |= 256;
    String s = Integer.toBinaryString(temp);//返回的是二进制对应的补码
    //最后一个没有8位，二进制转换后肯定是正数
    return s.substring(s.length()-8);
}

它主要调用 Integer.toBinaryString 这个静态方法，不过他传入的参数是 int 类型的，我们要通过 与运算和截取操作，把它变成8位。

然后再重载这个方法，这时传入的是一个字节数组：

1
2
3
4
5
6
7
8
//将一个byte数组转换成一个二进制的字符串
public static String byteToString(byte[] bytes){
    StringBuffer sb = new StringBuffer();
    for (byte b : bytes) {
        sb.append(byteToString(b));
    }
    return sb.toString();
}

这个不难理解的吧，然后再完成我们的 reComByteToString(bytes) 方法，不过不要玩了我们之前的约定：我们写入到输出流中的byte数组，第一个字节中存放一个数，它不是真正的字节数据， 而是我们上面的那个 j 。

所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
//将解压时传入的bytes数组转换成压缩时转成的字符串sb
public static String reComByteToString(byte[] bytes){
    //将bytes变成字符串
    String sb = byteToString(bytes);
    int len = sb.length();//赫夫曼编码转成字符串的长度
    String front = sb.substring(8,len-8);//前面的部分
    String back = sb.substring(len-8,len);//后面的部分
    back = back.substring(bytes[0]);//依照约定截取
    sb = front+back;
    return sb;
}

返回原来的byte数组

下面我们先写返回 ArrayList 类型的那个方法（reComToBytes），就是不断遍历查询添加：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//解压缩时根据传入字符串sb和反转的haffmanMap，返回原来的byte数组,用ArrayList形式返回
public static ArrayList<Byte> reComToBytes(String sb,HashMap<String,Byte> reHaffmanMap){
    //要返回的byte链表，到最后转成数组即可
    ArrayList<Byte> byteList = new ArrayList<>();
    int left = 0;//遍历字符串时的左右指针
    int right = 0;
    int len = sb.length();
    while (right<=len){
        //将包含的字符串，查找到对应byte，添加到byte数组链表中
        if(reHaffmanMap.containsKey(sb.substring(left,right))){
            Byte b = reHaffmanMap.get(sb.substring(left, right));
            byteList.add(b);
            left = right;
        }
        right++;
    }
    return byteList;
}

下面将 ArrayList转换成数组类型的 byte：

1
2
3
4
5
6
7
8
9
10
11
12
13
//传入ArrayList<Byte>，返回数组形式的byte
public static byte[] ArrListToArr(ArrayList<Byte> byteList){
    int size = byteList.size();
    Byte[] resBytes = new Byte[size];//Byte数组
    //用集合的toArray方法返回Byte数组
    byteList.toArray(resBytes);
    byte[] resbytes = new byte[size];//byte数组
    //将Byte数组转成byte数组
    for (int i = 0; i < size; i++) {
        resbytes[i] = resBytes[i];
    }
    return resbytes;
}

至此，全部完成！撒花，累死了，纪念我学了两天的赫夫曼树，还有今天写这一篇博客！