堆排序,霍夫曼编码

堆排序,霍夫曼编码

树结构的实际应用

应用一:堆排序

概念明确

大顶堆和小顶堆

所谓的大顶堆指的就是在一个二叉树中父节点要比所有的子节点要大,而小顶堆指的就是父节点要比子节点要小

我们一般使用大顶堆来进行升序排序,使用小顶堆来进行降序排序

基本思想介绍

  1. 将待排序数组当成一个顺序存储二叉树,将其变为一个大顶堆或者小顶堆
  2. 将成为大小顶堆的首元素于尾元素进行交换
  3. 再将出去尾元素的数组当成一个二叉树,变成一个大顶堆或者小顶堆
  4. 重复23步骤直到数组仅余下一个元素,数组就自然有序了

思路分析

其实整个堆排序就是选择排序的一个扩展
其难点就在于如何将普通的数组转化为大顶堆或者小顶堆
以转化为大顶堆为例,最困难的是如何保持大顶堆,要想将整个二叉树变为大顶堆,只需要先保证根节点的子树都是大顶堆,在求出左子树和右子树又或是根节点的最大值给根节点就是。
以上面的思路来,看似没有问题,实际上有个大破绽,如果根节点和左子树进行了交换,那么左子树的值肯定变小了,那左子树就不再是一个大顶堆,问题就是如何保证交换后可以保持子树的大顶堆。

代码实现

实现大顶堆的调整

/**
 * 功能:完成 将以i对应的非叶子节点的树调整成大顶堆
 * @param arr 待调整的数组
 * @param i 表示非叶子节点在数组中的索引
 * @param length 对多少个元素进行调整
 */
public static void adjust(int arr[], int i, int length) {
    int temp = arr[i]; // 先取出当前元素的值保存在临时变量
    // k = i * 2 + 1 k指向的是i的左子节点
    for (int k = i * 2 + 1; k < length; k = k * 2 +1) {
        if (k + 1 < length && arr[k] < arr[k+1]) { // 左子节点的值小于右子节点的值
            k++;// k指向右子节点
        }
        // k - > 最大的 子树

        if (arr[k] > temp) { // 如果子节点大于父节点
            arr[i] = arr[k]; // 把较大的值赋给当前节点
            i = k; // 让i指向k,继续循环比较
        } else {
            break; // !
        }

        arr[i] = temp;
    }
}

交换的实现

public static void heapSort(int arr[]) { 	
    int temp;
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        adjust(arr, i, arr.length);
    }

    for (int j = arr.length - 1; j > 0; j--) {
        // 交换
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        adjust(arr, 0, j);
    }
}

应用二:赫夫曼树

赫夫曼树的基础知识和实现

基础知识
赫夫曼树根据翻译也可以叫做哈夫曼树或者霍夫曼树。
它指的是给n个带权节点作为叶子节点造一颗二叉树,若该树的带权路径长度wpl最小就称为最优二叉树也叫赫夫曼树。
树的带权路径长度wpl:指的就是树的所有叶子节点的带权路径长度之和

若将树的高度设为L,节点的权为i。
那么单一节点的带权路径长度就是$L$ * $i$,而WPL=($L_1$ * $i_1$)+($L_2$ * $i_2$)+...+($L_n$ * $i_n$)

赫夫曼树示意图

赫夫曼树实现的步骤分析

根据示意图不难看出赫夫曼树的规律。使用权值最小的两个节点的权值相加构成他们的父节点,然后就是依次寻找权值最小的节点然后构造,直到所有的叶子节点都被构造完毕。
总结一下步骤:

  1. 先对待实现赫夫曼树的叶子节点进行升序排序
  2. 取出前两个节点,构造一个权值为前两个节点的权值和的父节点,然后父节点和之前两个节点共同组成一个二叉树。
  3. 隔离前两个节点,将他们的父节点加入待实现赫夫曼树的叶子节点中
  4. 重复1-3步骤直到待排序节点中只有一个元素,他就是新的赫夫曼树的根节点。

代码实现

节点代码:这里实现了一个Comparable接口,主要是为了可以使用集合的排序功能

class Node implements Comparable<Node>{
    int value; // 节点的权值
    Node left; // 左子节点
    Node right; // 右子节点
    public Node(int value) {
        this.value = value;
    }
    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
    @Override
    public int compareTo(Node o) {
        // 从小到大
        return this.value - o.value;
    }
}

创建赫夫曼树的代码:arr是存储了叶子节点中的权值的数组
这里使用了集合来便于管理节点,主要是使用了移除,添加,排序这些集合中的方法,在前面的笔记中这些东西都有实现过,这里就偷懒使用了集合。

public static Node createHuffmanTree(int[] arr) {
    List<Node> nodes = new ArrayList<>();
    for (int value : arr) {
        nodes.add(new Node(value));
    }
    while (nodes.size() > 1) {
        // 排序 小到大 使用了外部比较器
        Collections.sort(nodes);
        // 取出根节点权值最小的两颗二叉树
        Node left = nodes.get(0);
        Node right = nodes.get(1);
        // 构建一颗新的二叉树
        Node parent = new Node(left.value + right.value);
        parent.left = left;
        parent.right = right;
        // 从ArrayList中删除掉left和right
        nodes.remove(left);
        nodes.remove(right);
        // 将parent加入到nodes
        nodes.add(parent);
    }
    // 返回赫夫曼树的root节点
    return nodes.get(0);
}

赫夫曼编码

定长编码

定长编码对数据处理方式为将数据按照ASCII码表进行转换,然后对转换为的十进制树再转化为二进制之后进行存储,每一个字节都用8位的二进制存储

直观的理解就是不对数据进行任何加工直接进行存储

变长编码

按照字符出现的次数进行编码比如:i like jelly
l:0 空格:1 i:01 ...
通过执行规定来进行字符的编码,这样的编码长度都不尽相同,所以叫变长编码

问题
这样的变长编码,具有不唯一性,没办法确定该字符的编码不为其他字符的编码的前缀,也就是说这种编码不是前缀编码

前缀编码指的就是所有的字符的编码都不为其他字符编码的前缀,赫夫曼编码就是一种实现了前缀编码的编码方式

赫夫曼编码

赫夫曼编码首先也是统计字符出现的次数,然后让次数作为权值当叶子节点构成一颗赫夫曼树
然后规定往左路径为0往右路径为1,到达叶子节点的路径上的0或者1就作为叶子节点的编码,这个编码就称之为赫夫曼编码
具体参照下图示意

赫夫曼编码

赫夫曼编码也是属于变长编码的一种,但是它是一种前缀编码

注意:根据对相同权值的叶子节点处理的先后不同,会造成生成的赫夫曼树不同,但是它们都是赫夫曼树,也就是他们的wpl都是最小且相同的。

赫夫曼编码实现数据压缩

整体代码 赫夫曼demo代码

思想分析
首先是数据的压缩

  1. 首先是通过数据(byte[])转化为Node集合(List<Node>)
  2. 接着使用这个Node集合构建赫夫曼树
  3. 再通过赫夫曼树创建赫夫曼编码(Map<Byte, String>)
  4. 由编码再对数据进行组装后压缩

数据的解压:思路上就是直接通过赫夫曼编码表,反向推导回来

Node节点编写

首先需要一个Node节点类来辅助构成赫夫曼树,这里贴出代码
和之前的代码,区别仅在于数据本身位byte类型,而且多了一个权值weight属性。实现Comparable和之前的代码都无区别,在比较时用的权值作为参照。

// 创建Node,带数据和权值
class Node implements Comparable<Node> {
    Byte data; // 存放数据本身
    int weight; // 权值, 也就是数据出现了几次
    Node left;
    Node right;
    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node o) {
        // 升序
        return this.weight - o.weight;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
}

实现byte[]转List

这里要做的事情很简单,先统计byte[]中数据的出现次数,用byte本身作为data域而次数作为权值存入List集合中
为了实现上述要求,这里使用了Map集合,用key来存储byte的数据而value存储次数也就是权值。最后再遍历Map集合创建Node节点类的实例添加到List集合中去。

private static List<Node> getNode(byte[] bytes) {
    // 创建一个ArrayList
    List<Node> nodes = new ArrayList<>();
    // 存储每一个byte出现的次数 -> map
    Map<Byte, Integer> hashMap = new HashMap<>();
    for(byte b : bytes) {
        Integer count = hashMap.get(b);
        if (count == null) {
           // map中没有这个数据
           hashMap.put(b, 1);
        } else {
           hashMap.put(b, count + 1);
        }
    }
    for (Map.Entry<Byte, Integer> entry : hashMap.entrySet()) {
        nodes.add(new Node(entry.getKey(), entry.getValue()));
    }
    return nodes;
}

构建赫夫曼树

这里创建赫夫曼树和之前叙述的思想相同,仅在代码上有小区别。

private static Node createHuffmanTree(List<Node> nodes) {
    while (nodes.size() > 1) {
        // 排序 升序
        Collections.sort(nodes);
        // 取出前两个元素
        Node leftNode = nodes.get(0);
        Node rightNode = nodes.get(1);
        // 创建一颗新的二叉树,他的根节点没有data,只有权值
        Node parent = new Node(null, leftNode.weight + rightNode.weight);
        parent.left = leftNode;
        parent.right = rightNode;
        // 处理掉的元素移除,新生成的元素加入
        nodes.remove(leftNode);
        nodes.remove(rightNode);
        nodes.add(parent);
    }
    return nodes.get(0);
}

创建赫夫曼编码

首先是创建成员变量huffmanCodes来存放赫夫曼编码表
stringBuilder是作为一个辅助变量用来做字符串的拼接的

// 生成的赫夫曼树对应的赫夫曼编码表
// 将赫夫曼编码表存放在Map<Byte, String> 形式 空格(32):00
static Map<Byte, String> huffmanCodes = new HashMap<>();
static StringBuilder stringBuilder = new StringBuilder();

在创建赫夫曼编码时是使用了递归的,也就是说下面这个方法是一个递归方法。
具体的思路为:将传入的字符串和本节点存储的字符串拼接,看传入的node节点是否为空。
如果不为空,则看传入的节点是否是叶子节点(通过判断data域,非叶子节点的data是空的),叶子节点就存储到huffmanCodes这个HashMap中,不是叶子节点就继续向左或者向右递归。

/**
 * 功能:将传入的Node节点的所有叶子节点的赫夫曼编码存放到Map中
 * @param node 传入的节点,默认是根节点
 * @param code 路径:左子节点是0,右子节点是1
 * @param stringBuilder 拼接路径
 */
private static void getCodes(Node node, String code, StringBuilder stringBuilder) {
    StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    stringBuilder2.append(code);
    if (node != null) {
        // 判断当前node是叶子节点还是非叶子节点
        if (node.data == null) {
            // 非叶子节点,递归处理
            // 向左
            getCodes(node.left, "0", stringBuilder2);
            // 向右
            getCodes(node.right, "1", stringBuilder2);
        } else {
            // 叶子节点, 存储
            huffmanCodes.put(node.data, stringBuilder2.toString());
        }
    }
}

这里再往外界暴露一个重载的方法便于操作

// 重载getCodes
private static Map<Byte, String> getCodes(Node root) {
    if (root == null) {
        return null;
    }
    getCodes(root, "", stringBuilder);
    return huffmanCodes;
}

压缩方法编写

压缩思路:现在已经获得编码表了,还有原本的字节数组,就可以对照编码表将字节数组编码成字符串
这里就有一个误区,接下来并不是将这个编码成的字符串存储,那样的话占用的空间很可能比之前还大
要做的是将编码成的字符串每八个字符存储为一个byte,这样就完成了压缩

这样会产生另一个问题,最后一个存储的byte有可能不足八位,这里教程中是直接存储,但是经过测试证明直接存储有可能会产生问题
例如:最后是3位001存储成byte后其实只用了1这一位,然后解压时,教程中处理最后一个byte时采取不补位的方案,这就会导致少了两位0,其实这里补位也不行,补位的话不知道补多少位。

这里根据视频教程评论区大佬的思路和方法提出了改进方案,将存储的byte数组的长度在原有基础上加1,最后一位用来存储最后一个字节的位数,这样在之后解压的时候就可以明确补位多少了。

这里的关于parseInt的二进制转化的补码问题可以参考文章二进制浅析

/**
 * 压缩方法
 * @param bytes 原始字符串对应的byte数组
 * @param huffmanCodes 赫夫曼编码map
 * @return 赫夫曼编码处理后的byte数组
 */
private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes){
    // 使用赫夫曼编码表将bytes转成 赫夫曼编码对应的字符串
    StringBuilder stringBuilder = new StringBuilder();
    // 遍历bytes数组
    for (byte b : bytes) {
        stringBuilder.append(huffmanCodes.get(b));
    }
    // 将字符串转化为byte数组
    //统计返回的length
    int len = (stringBuilder.length() + 7) / 8;
    // 创建一个存储压缩后的byte数组
    byte[] by = new byte[len + 1];
    int index = 0; // 记录时第几个byte
    for (int i = 0; i < stringBuilder.length(); i += 8) {
        String strByte;

        if (i + 8 > stringBuilder.length()) {
            // 代表当前是最后一个字节,有可能不慢8位
            strByte = stringBuilder.substring(i);
            by[len] = (byte)strByte.length();
        } else {
            strByte = stringBuilder.substring(i, i + 8);
        }
        // 将strByte转成一个byte数组放入by中
        by[index] = (byte)Integer.parseInt(strByte, 2);
        index++; // 计数器累加
    }
    return by;
}

数据的解压

首先数据的解压需要一个重要的步骤:将一个byte转化为一个二进制字符串
只有有了这一步骤后我们才能根据二进制字符串和编码表进行解压

将byte转化为二进制字符串封装为一个单独的方法

这里的toBinaryString方法是将一个十进制转化为二进制补码的字符串,但是这个方法有个局限性,在转化正数的二进制时它前面时不会补0的也就是在压缩的时候8位byte转化位十进制数如果是正数而且前面恰好有0这里解析的时候这个0是没有的,所以我们要给它高位补零
方案有很多这里教程中采用的是temp |= 256;经过这个公式处理后会将高位的0补充
例如88 的二进制补码为1011000 它不足8位很显然前面少了0
如果使用88 | 256 结果是344 再对344使用toBinaryString求补码为101011000 取后8位为01011000正好是补上0的正88的补码
之后还要处理最后一个byte的位数问题,这个前面提到过,就不在赘述。

/**
 * 将一个byte 转称一个二进制字符串
 * @param b 传入的byte
 * @param flag 标识是否需要补高位
 * @return 是该b 对应的二进制字符串,(注意这是按照补码返回)
 */
private static String byteToBitString(boolean flag, byte b, byte count) {
    // 使用一个变量保存b
    int temp = b;
    temp |= 256;
    String str = Integer.toBinaryString(temp);
    if (flag) {
        return str.substring(str.length() - 8);
    } else {
        return str.substring(str.length() - count);
    }
}

数据解压方法
有了之前的byteToBitString方法就可以比较容易的将byte[]转化为二进制字符串
我们可以将哈夫曼编码表也就是HashMap反转一下以便于操作,剩下的进行字符串的匹配和对照还原就没什么难点,看代码就好了。

// 数据解压
private static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
    // 先得到huffmanByte 对应的二进制字符串
    StringBuilder stringBuilder = new StringBuilder();
    // 将byte数组转成二进制的字符串
    for (int i = 0; i < huffmanBytes.length - 1; i++) {
        // 判断是否为最后一个字节
        boolean flag = (i == huffmanBytes.length - 2);
        stringBuilder.append(byteToBitString(!flag, huffmanBytes[i], huffmanBytes[huffmanBytes.length - 1]));
    }

    // 调转 键值
    Map<String, Byte> map = new HashMap<>();
    for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
        map.put(entry.getValue(), entry.getKey());
    }
    // 创建一个集合存放byte
    List<Byte> list = new ArrayList<>();
    for (int i = 0; i < stringBuilder.length();) {
        int count = 1;
        Byte b = null;
        boolean flag = true;

        while (flag) {
            String key = stringBuilder.substring(i, i + count);
            b = map.get(key);
            if (b == null) {
                count++;
            } 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;
}

扩展内容:压缩文件和解压文件

压缩

方法中的huffmanZip是一个整合方法将之前的压缩步骤放在一个控制方法中

/**
 * 压缩方法
 * @param bytes 原始的字符串对应的byte
 * @return 是经过赫夫曼编码处理后的字节数组
 */
private static byte[] huffmanZip(byte[] bytes) {
    // 1. 获得Node的List集合
    List<Node> node = getNode(bytes);
    // 2. 通过集合获得赫夫曼树
    Node huffmanTree = createHuffmanTree(node);
    // 3. 通过赫夫曼树生成赫夫曼编码
    Map<Byte, String> codes = getCodes(huffmanTree);
    // 4. 通过赫夫曼编码对原始数组进行压缩,并返回
    return zip(bytes, codes);
}

压缩文件其实无非就是对IO流的操作,没什么难点,需要注意的是千万别忘记将赫夫曼编码表写入文件,否则将无法解压文件

/**
 *
 * @param srcFile 传入的希望文件路径
 * @param dstFile 压缩后文件放的路径
 */
public static void zipFile(String srcFile, String dstFile) {
    // 创建流
    // 创建一个文件的输入流
    InputStream is = null;
    OutputStream os = null;
    ObjectOutputStream oos = null;
    try {
        is = new FileInputStream(srcFile);
        // 创建和源文件大小一样的byte数组
        byte[] b = new byte[is.available()];
        // 读取文件
        is.read(b);
        // 直接对源文件压缩
        byte[] huffmanBytes = huffmanZip(b);
        // 创建一个文件的输出流存放压缩文件
        os = new FileOutputStream(dstFile);
        // 创建一个对象输出流
        oos = new ObjectOutputStream(os);
        // 利于恢复
        oos.writeObject(huffmanBytes);
        // 一定要把赫夫曼编码写入压缩文件
        oos.writeObject(huffmanCodes);
    } catch (IOException e) {
        System.out.println(e.getMessage());
    } finally {
        try {
            if (is != null) {
                is.close();
            }
            if (oos != null) {
                oos.close();
            }
        } catch (IOException e) {
            System.out.println(e.getMessage());
        }
    }
}

解压文件

public static void unZipFile(String zipFile, String dstFile) {
    // 定义文件输入流
    InputStream is = null;
    ObjectInputStream ois = null;
    OutputStream os = null;
    try {
        is = new FileInputStream(zipFile);
        ois = new ObjectInputStream(is);
        byte[] huffmanBytes = (byte[])ois.readObject();
        Map<Byte, String> huffmanCodes = (Map<Byte, String>)ois.readObject();
        // 解码
        byte[] decode = decode(huffmanCodes, huffmanBytes);
        // decode写入
        os = new FileOutputStream(dstFile);
        os.write(decode);
    } catch (IOException | ClassNotFoundException e) {
        System.out.println(e.getMessage());
    } finally {
        try {
            if (ois != null) {
                ois.close();
            }
            if (os != null) {
                os.close();
            }
        } catch (IOException e) {
            System.out.println(e.getMessage());
        }
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.byfree.top/archives/algorithm04