Jared's blog Jared's blog
首页
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • Java
  • 数据库SQL
  • 设计模式
  • 集成开发环境
  • Linux系统
  • 代码管理
  • 项目管理
  • 后端

    • 中间件
    • Spring家族
    • 服务器软件
    • 数据库
    • 搜索引擎
    • 分布式&微服务
    • 容器化
  • 前端

    • 基础
    • 模板框架
    • 组件化框架
  • 运维知识
  • 部署工具
架构与模型
  • 在线教育
  • 电商
  • 疑惑日志
  • 随笔
  • 友链
  • 书籍
  • 娱乐
  • Github (opens new window)
  • Gitee (opens new window)
  • CSDN (opens new window)

Jared H

💻🤣😜
首页
  • 数据结构与算法
  • 计算机网络
  • 操作系统
  • Java
  • 数据库SQL
  • 设计模式
  • 集成开发环境
  • Linux系统
  • 代码管理
  • 项目管理
  • 后端

    • 中间件
    • Spring家族
    • 服务器软件
    • 数据库
    • 搜索引擎
    • 分布式&微服务
    • 容器化
  • 前端

    • 基础
    • 模板框架
    • 组件化框架
  • 运维知识
  • 部署工具
架构与模型
  • 在线教育
  • 电商
  • 疑惑日志
  • 随笔
  • 友链
  • 书籍
  • 娱乐
  • Github (opens new window)
  • Gitee (opens new window)
  • CSDN (opens new window)
  • 数据结构与算法

    • README
    • 数据结构

    • 算法

      • 哈夫曼算法
        • 什么是哈夫曼编码?
        • 举例
        • 二进制转十进制
  • 计算机网络

  • 操作系统

  • Java

  • 数据库-SQL

  • 设计模式

哈夫曼算法

# 10.哈夫曼编码

  • 什么是哈夫曼编码?
  • 举例
  • 二进制转十进制

# 什么是哈夫曼编码?

假设有一个字符串,其中包含了一些字符,每个字符出现的次数不同,也就是权重不同,所以可以根据哈夫曼树的特点,找到带权路径长度最短的二叉树,来达到无损压缩的目的。

参考: 哈夫曼树的构建 (opens new window) 、哈夫曼编码 (opens new window)

# 举例

  1. 定义一个字符:

    String str = "I like to learn Java";  
    
    1
  2. 转为byte数组,也就是对应的ASCII码

    byte[] bytes = str.getBytes();  
    
    1
  3. 用一个节点Node[data=ASCII码,weight=出现次数],转化上面的byte数组,方便构建哈夫曼树;参考 Node.java

  4. 构建哈夫曼树

    Node.java
    import java.util.*;
    
    /**
     * 创建Node,存数据和权值
     */
    public class Node implements Comparable<Node> {
    
        /**
         * 存放数据(ASCII编码),比如'a' => 97 ' ' => 32
         */
        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;
        }
    
        public String toString() {
            return "Node [data = " + data + ", weight=" + weight + "]";
        }
    
        //前序遍历
        public void preOrder() {
            System.out.println(this);
    
            if (this.left != null) {
                this.left.preOrder();
            }
            if (this.right != null) {
                this.right.preOrder();
            }
        }
    
        /**
         * 计算byte出现次数,byte作为节点的date,次数作为节点的权重
         *
         * @param bytes 接收字节数组
         * @return 返回 List<Node> 节点列表
         */
        public static List<Node> bytesToNodes(byte[] bytes) {
            ArrayList<Node> nodes = new ArrayList<>();
            //遍历 bytes , 统计 每一个byte出现的次数->map[key,value]
            Map<Byte, Integer> counts = new HashMap<>();
            for (byte b : bytes) {
                counts.put(b, counts.getOrDefault(b, 0) + 1);
            }
    
            //转换为Node列表
            for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
                nodes.add(new Node(entry.getKey(), entry.getValue()));
            }
            return nodes;
        }
    
        /**
         * 构建huffman树
         *
         * @param nodes 节点列表
         * @return huffman树
         */
        public static Node buildHuffmanTree(List<Node> nodes) {
            if (nodes == null) {
                return null;
            }
    
            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删除
                nodes.remove(leftNode);
                nodes.remove(rightNode);
                //将新的二叉树,加入到nodes
                nodes.add(parent);
            }
            //nodes 最后的结点,就是赫夫曼树的根结点
            return nodes.get(0);
        }
    }
    
    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
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
  5. 获取哈夫曼编码表:key = ASCII码,value=哈夫曼编码(从根节点到每一个叶子节点的路径上,左分支记为0,右分支记为1,将这些0与1连起来即为叶子节点的哈夫曼编码)

        /**
         * 哈夫曼编码表
         * eg: "I like to learn Java" => {32=111, 97=101, 101=1101, 73=0010, 105=0011, 74=0100, 107=0101, 108=000, 110=0110, 111=0111, 114=1000, 116=1001, 118=1100}
         */
        static Map<Byte, String> huffmanCodes = new HashMap<>();
     
        /**
         * 将节点值转换为哈夫曼编码
         *
         * @param root 节点
         * @param code 哈夫曼编码
         */
        public static void huffmanCode(Node root, String code) {
            if (root.left == null && root.right == null) {
                if (root.data != null) {
                    huffmanCodes.put(root.data, code);
                }
                return;
            }
            huffmanCode(root.left, code + "0");
            huffmanCode(root.right, code + "1");
        }
    
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
  6. 压缩:

    实际就是将原先的ASCII码转成哈夫曼所表示的二进制数组(这个二进制数组长度比原先的ASCII表示的二进制数组长度短),再转为十进制的ASCII码保存。

  7. 解压:

    将压缩后的数组与转为二进制,然后再与之前得到的哈夫曼表进行比较,得到原先的ASCII码。

HuffmanCode.java
import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class HuffmanCode {

    /**
     * 哈夫曼编码表
     * eg: "I like to learn Java" => {32=111, 97=101, 101=1101, 73=0010, 105=0011, 74=0100, 107=0101, 108=000, 110=0110, 111=0111, 114=1000, 116=1001, 118=1100}
     */
    static Map<Byte, String> huffmanCodes = new HashMap<>();

    /**
     * 将节点值转换为哈夫曼编码
     *
     * @param root 节点
     * @param code 哈夫曼编码
     */
    public static void huffmanCode(Node root, String code) {
        if (root.left == null && root.right == null) {
            if (root.data != null) {
                huffmanCodes.put(root.data, code);
            }
            return;
        }
        huffmanCode(root.left, code + "0");
        huffmanCode(root.right, code + "1");
    }

    /**
     * 哈夫曼压缩算法
     *
     * @param bytes 原始的字符串对应的字节数组
     * @return 是经过 赫夫曼编码处理后的字节数组(压缩后的数组)
     */
    public static byte[] huffmanZip(byte[] bytes) {
        // 转化为权值ASCII 节点
        List<Node> nodes = Node.bytesToNodes(bytes);
        // 根据 nodes 创建的赫夫曼树
        Node huffmanTreeRoot = Node.buildHuffmanTree(nodes);
        // 得到赫夫曼编码表
        huffmanCode(huffmanTreeRoot, "");
        // 根据生成的赫夫曼编码表,压缩得到压缩后的赫夫曼编码字节数组
        return zip(bytes, huffmanCodes);
    }

    /**
     * 将原始的字节数组根据哈夫曼表进行压缩
     *
     * @param bytes        原始的字符串对应的 byte[]
     * @param huffmanCodes 哈夫曼表
     * @return 压缩后的byte[]
     */
    private static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {

        //1.利用哈夫曼编码表将原始字节数组转成赫夫曼编码数组
        // (实际就是将原先的ASCII码转成哈夫曼所表示的二进制数组(这个二进制数组长度比原先的长度短,所以就被压缩了))
        StringBuilder stringBuilder = new StringBuilder();
        for (byte b : bytes) {
            stringBuilder.append(huffmanCodes.get(b));
        }
        // +7 是为了防止 字符串长度不是 8的倍数,导致最后一个byte不足8位
        int len = (stringBuilder.length() + 7) / 8;
        byte[] huffmanCodeBytes = new byte[len];

        //2. 将赫夫曼编码字符串(0,1组成,每8位对应一个字节)转为int,再转成byte
        int index = 0;
        // 因为是每8位对应一个byte,所以步长 +8
        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte;
            if (i + 8 > stringBuilder.length()) {//不够8位
                strByte = stringBuilder.substring(i);
            } else {
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将strByte 转成一个byte,放入到 huffmanCodeBytes
            byte parseInt = (byte) Integer.parseInt(strByte, 2);
            huffmanCodeBytes[index] = parseInt;//输入二进制的strByte转为十进制
            index++;
        }
        return huffmanCodeBytes;
    }
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
    /**
     * 将一个byte 转成一个二进制的字符串
     *
     * @param b    传入的 byte
     * @param flag 标志是否需要补高位如果是true ,表示需要补高位,如果是false表示不补, 如果是最后一个字节,无需补高位
     * @return 是该b 对应的二进制的字符串,(注意是按补码返回)
     */
    public static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b; //将 b 转成 int
        //如果是正数我们还存在补高位
        if (flag) {
            temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
        }
        String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
        if (flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }


    /**
     * 解码
     *
     * @param huffmanCodes 哈夫曼编码表 map
     * @param huffmanBytes 哈夫曼编码得到的字节数组
     * @return 就是原来的字符串对应的数组
     */
    public static byte[] decode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {

        //1. 先得到 哈夫曼编码表 对应的 二进制的字符串 , 形式 1010100010111...
        StringBuilder stringBuilder = new StringBuilder();
        //将byte数组转成二进制的字符串
        for (int i = 0; i < huffmanBytes.length; i++) {
            byte b = huffmanBytes[i];
            //判断是不是最后一个字节
            boolean flag = (i == huffmanBytes.length - 1);
            stringBuilder.append(byteToBitString(!flag, b));
        }
        //把字符串安装指定的赫夫曼编码进行解码
        //把赫夫曼编码表进行调换,因为反向查询 a->100 100->a
        Map<String, Byte> map = new HashMap<String, Byte>();
        for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
            map.put(entry.getValue(), entry.getKey());
        }

        List<Byte> list = new ArrayList<>();
        for (int i = 0; i < stringBuilder.length(); ) {
            //指针,移动指针取一段字符串去匹配哈夫曼编码对应的ASCII
            int pointer = 1;
            while (true) {
                int end = i + pointer;
                // TODO: 按照目前压缩文件的写法最后一组是哈夫曼编码表,所以会有匹配不到的情况
                if (end > stringBuilder.length()) {
                    break;
                }

                String key = stringBuilder.substring(i, end);
                Byte b = map.get(key);
                if (b != null) {
                    //匹配到
                    list.add(b);
                    break;
                }
                pointer++;
            }
            i += pointer;
        }

        //把list 中的数据放入到byte[] 并返回
        byte[] result = new byte[list.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = list.get(i);
        }
        return result;
    }


    /**
     * 解压文件
     *
     * @param zipFile 准备解压的文件路径
     * @param dstFile 文件解压路径
     */
    public static void unZipFile(String zipFile, String dstFile) {

        //定义文件输入流
        InputStream is = null;
        //定义一个对象输入流
        ObjectInputStream ois = null;
        //定义文件的输出流
        OutputStream os = null;
        try {
            //创建文件输入流
            is = new FileInputStream(zipFile);
            //创建一个和  is关联的对象输入流
            ois = new ObjectInputStream(is);
            //读取byte数组  huffmanBytes
            byte[] huffmanBytes = (byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte, String> huffmanCodes = (Map<Byte, String>) ois.readObject();

            //解码
            byte[] bytes = decode(huffmanCodes, huffmanBytes);
            //将bytes 数组写入到目标文件
            os = new FileOutputStream(dstFile);
            //写数据到 dstFile 文件
            os.write(bytes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                os.close();
                ois.close();
                is.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 压缩文件
     *
     * @param srcFile 传入的压缩的文件的全路径
     * @param dstFile 压缩文件目录
     */
    public static void zipFile(String srcFile, String dstFile) {

        //创建输出流
        OutputStream os = null;
        ObjectOutputStream oos = null;
        //创建文件的输入流
        FileInputStream is = null;
        try {
            //创建文件的输入流
            is = new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b = new byte[is.available()];
            //读取文件
            is.read(b);
            //直接对源文件压缩
            byte[] huffmanBytes = huffmanZip(b);
            //创建文件的输出流, 存放压缩文件
            os = new FileOutputStream(dstFile);
            //创建一个和文件输出流关联的ObjectOutputStream
            oos = new ObjectOutputStream(os);
            //把 赫夫曼编码后的字节数组写入压缩文件
            oos.writeObject(huffmanBytes);
            //这里我们以对象流的方式写入 赫夫曼编码,是为了以后我们恢复源文件时使用
            //!!!注意一定要把赫夫曼编码 写入压缩文件
            oos.writeObject(huffmanCodes);
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                is.close();
                oos.close();
                os.close();
            } catch (Exception e) {
                e.printStackTrace();
            }
        }

    }
}

```

# 二进制转十进制

  1. 正数:反码补码和原码一样,正常计算

  2. 负数:

    原码:最高位是1,后面是其绝对值的二进制数

    反码:符号位不变,数据位按位取反

    补码:在其反码的最后一位+1

    计算:最左一位表示负,右面七位按位取反+1

    eg:      
    1010 0101  
    1101 1010  取反  
    1101 1011  加1
    结果= -91
    
    1
    2
    3
    4
    5
上次更新: 2022/04/02, 19:01:05
逻辑结构
计算机网络

← 逻辑结构 计算机网络→

Theme by Vdoing Copyright © 2020-2022 Jared H
粤ICP备20046800号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式
×