压缩算法数据结构

一 什么是数据压缩.

  数据压缩是一门通信原理和计算机科学都会涉及到的学科,在通信原理中一般称为信源编码,在计算机科学里一般称为数据压缩两者没有本质区别;

二 数据压缩的好处.

 1️⃣在进行通信的时候,将待传输的数据进行压缩,以减少带宽需求;
 2️⃣存储时减少磁盘容量;
 3️⃣提升IO速率;

三 应用场景

1. 文件系统
2. 数据库
3. 消息传输
4. 网页传输

四 压缩分类

1️⃣有损压缩
  指的是压缩之后就无法完整还原原始信息，但是压缩率可以很高，主要应用于视频、话音等数据的压缩，因为损失了一点信息很难察觉，丢失一部分数据也不会影响使用；
2️⃣无损压缩
 用于文件等等必须完整还原信息的场合.

五 压缩算法

1. LZ77 : 图解LZ77算法
2. 哈夫曼算法 : 哈夫曼算法详解

六 一个案例的入门思考

1️⃣LZ77算法案例 : 生，容易。活，容易。生活，不容易。
 假如这句话不压缩，如果使用Unicode编码，每个字会用2个字节表示。Unicode是一种国际标准，把常见各国的字符，比如英文字符、日文字符、韩文字符、中文字符、拉丁字符等等全部制定了一个标准，显然，用2个字节可以最多表示2^16=65536个字符;
 第一次出现的时候用普通的Unicode，第二次出现的“容易。”则可以用（距离、长度）表示，距离的意思是接下来的字符离前面重复的字符隔了几个，长度则表示有几个重复字符，上面的例子的第二个“容易。”就表示为（5,3），就是距离为5个字符，长度是3，在解压缩的时候，解到这个地方的时候，往前跳5个字符，把这个位置的连续3个字符拷贝过来就完成了解压缩;

2️⃣哈夫曼算法案例 : int[] arr = {13, 7, 8, 3, 29, 6, 1};
 哈弗曼树最小WPL定义 : 假设有m个权值{W1,W2,...Wm},可以构造一颗含有n个叶子节点的二叉树，每个叶子节点的权为Wj,则其中树的带权路径长度即WPL最小的二叉树称作最优二叉树或赫夫曼树。

哈夫曼树的生成步骤:
   1. 将每一个数据从小到大进行排序,每个数据都是一个节点,每个节点看成是一棵最简单的二叉树;
   2. 取出根节点权值最小的两棵二叉树;
   3. 组成一棵新的二叉树,新的二叉树根节点权值是前面两棵二叉树根节点权值的和;
   4. 再将这棵新的二叉树,以根节点的权值大小再次排序,不断重复`1-2-3-4`的步骤直到所有数据都被处理,就得到一棵哈夫曼树;

2.1 对数组排序 : 1,3,6,7,8,13,29
2.2 哈夫曼树生成图解

图解1 图解2 图解3 图解4 图解5

---

七 代码实现哈夫曼树

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 数据结构 --> 赫夫曼树简单实现
 *
 * @description:
 * @Author: my.yang
 * @Date: 2019/6/18 7:38 PM
 */
public class HuffmanTree {
    // main线程
    public static void main(String[] args) {
        // 声明测试数组
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        // 调用赫夫曼树生成权值节点
        Node root = createHuffmanTree(arr);
        // 打印结果权值节点value
        System.out.println("权值为 ---> " + root.value);
        // 前序编译验证赫夫曼树逻辑是否正确
        perOrder(root);
    }

    /**
     * 前序遍历完成赫夫曼树验证
     *
     * @param node
     */
    public static void perOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.value);
        perOrder(node.leftSubtree);
        perOrder(node.rightSubtree);
    }

    /**
     * 创建赫夫曼树并生成权值节点
     *
     * @param arr
     * @return
     */
    public static Node createHuffmanTree(int[] arr) {
        // 1. 数组转list
        List<Node> nodes = new ArrayList<>(arr.length);
        for (int value : arr) {
            nodes.add(new Node(value));
        }
        // 2. 循环合并权值节点并生成新的权值,直到节点为1时退出循环
        while (nodes.size() > 1) {
            // 2.1 对nodes排序 : 从小到大排序,规则取决于Comparable逻辑
            Collections.sort(nodes);
            // 2.2 获取左右子树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);
            // 2.3 生成新的树节点且计算权值
            Node parent = new Node(leftNode.value + rightNode.value);
            // 2.4 设置新权值的节点的左右子树
            parent.leftSubtree = leftNode;
            parent.rightSubtree = rightNode;
            // 2.5 移除原有节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 2.6 添加新数据到nodes中
            nodes.add(parent);
        }
        // 3. 返回最点权值
        System.out.println(nodes.size());
        return nodes.get(0);
    }
}

/**
 * 树节点node内部类,实现Comparable接口重写比较逻辑
 */
class Node implements Comparable<Node> {
    // node data
    int value;
    // 左子树
    Node leftSubtree;
    // 右子树
    Node rightSubtree;

    // 构造器
    public Node(int value) {
        this.value = value;
    }

    /**
     * 从小到大排序
     *
     * @param o
     * @return
     */
    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }
}