霍夫曼压缩算法

霍夫曼压缩算法

概述

霍夫曼压缩算法的主要思想是用较少的比特表示出现频率较高的字符,用较多的比特表示出现频率较低的字符。如下图所示,

实现

①读入完整的输入流,并转化为字符数组。
②计算每个字符出现的次数
③构建Huffman树
④构建编译表
⑤将单词查找树编码成比特输出串并写入到输出流
⑥将单词总数编码成比特输出串并写入到输出流
⑦使用编译表翻译每个输入字符

节点的表示

    private static final int R = 256;       //字符为ASCII表示

    private static class Node implements Comparable<Node> {

        private final char ch;
        private final int freq;
        private final Node left, right;

        public Node(char ch, int freq, Node left, Node right) {
            this.freq = freq;
            this.ch = ch;
            this.left = left;
            this.right = right;
        }

        private boolean isLeaf() {
            return left == null && right == null;
        }

        @Override
        public int compareTo(Node that) {
            return this.freq - that.freq;
        }
    }

构建Huffman单词查找树

构建初始有一堆没有父节点的节点,将它们放到最小队列中,这样对头总是freq为最小的那个节点。 从队列中找到freq最小的两个节点,创建一个它们的父节点,将三个节点归并成一个大节点,接着放入队列中, 循环往复直至队列中只剩一个节点。

    /**
     * @param freq 字符出现的次数
     * @return
     */
    private static Node buildTrie(char[] freq) {
        MinPQ<Node> pq = new MinPQ<Node>();

        //初始化多个将构成一颗Huffman树的结点
        for (char i = 0; i < R; i++) {
            if (freq[i] > 0) pq.insert(new Node(i, freq[i], null, null));
        }

        // special case in case there is only one character with a nonzero frequency
        if (pq.size() == 1) {
            if (freq['\0'] == 0) pq.insert(new Node('\0', 0, null, null));
            else pq.insert(new Node('\1', 0, null, null));
        }

        //归并两个小树
        while (pq.size() > 1) {
            Node left = pq.delMin();
            Node right = pq.delMin();

            Node parent = new Node('\0', left.freq + right.freq, left, right);      //创建连接子树的中间结点
            pq.insert(parent);
        }

        return pq.delMin();
    }

将Huffman单词查找树转化成字节流写到压缩文件中

做如下规定: 中间结点写0;叶子结点写1,并在后面写结点上的字符。

    /**
     * 将单词查找树编码成比特输出串并写入到输出流
     * 用前序遍历
     */
    private static void writeTrie(Node x) {
        if (x.isLeaf()) {
            BinaryStdOut.write(true);
            BinaryStdOut.write(x.ch);
            return;
        }

        BinaryStdOut.write(false);
        writeTrie(x.left);
        writeTrie(x.right);
    }

将压缩文件中字节流转化为Huffman单词查找树

按写入时的规定解析字节流。

    /**
     * 读比特流,得出一颗单词查找树
     */
    private static Node readTrie() {
        if (BinaryStdIn.readBoolean()) {   //读到1,说明是叶子结点
            return new Node(BinaryStdIn.readChar(), 0, null, null);
        }

        //读到的是0,说明是中间结点,需要递归直到读到1为止

        Node left = readTrie();
        Node right = readTrie();
        return new Node('\0', 0, left, right);
    }

构建编译表

构建编译表st,索引为字符,值为路径(比特字符串)。 根据这张表,可以将源文件中的某个字符,压缩为更少bit表示的Huffman树上的路径。

    private static void buildCode(String[] st, Node x, String s) {
        if (!x.isLeaf()) {
            buildCode(st, x.left, s + "0");
            buildCode(st, x.right, s + "1");
        } else {
            st[x.ch] = s;
        }

    }

压缩

      /**
     * 从输入流中读字节流,并将压缩后的结果写入输出流
     */
    private static void compress() {
        //①读入完整的输入流,并转化为字符数组
        String s = BinaryStdIn.readString();
        char[] input = s.toCharArray();

        //②计算每个字符出现的次数,没有出现的就为0
        char[] freq = new char[R];
        for (int i = 0; i < input.length; i++) {
            freq[input[i]]++;
        }

        //③构建Huffman树
        Node root = buildTrie(freq);

        //④构建编译表,将输入中的每个char值与一个比特字符串(即Huffman树上路径)相关联
        String st[] = new String[R];
        buildCode(st, root, "");


        //⑤将单词查找树编码成比特输出串并写入到输出流
        writeTrie(root);

        //⑥将单词总数编码成比特输出串并写入到输出流
        BinaryStdOut.write(input.length);


        //⑦使用编译表翻译每个输入字符
        for (int i = 0; i < input.length; i++) {
            String code = st[input[i]];   //code表示Huffman单词查找数上的路径
            for (int j = 0; j < code.length(); j++) {  //要一位一位地输出
                if (code.charAt(j) == '1') {
                    BinaryStdOut.write(true);
                } else {
                    BinaryStdOut.write(false);
                }
            }

        }

        BinaryStdOut.close();
    }

### 解压

     /**
     * 解压
     * 读取压缩文件的比特流,
     * 将比特流对应为路径在单词查找树上找,将找到的结点中的字符写出
     */
    private static void expand() {
        Node root = readTrie();
        int N = BinaryStdIn.readInt();  //读出存在压缩文件中的字符串长度

        for (int i = 0; i < N; i++) {   //找出源文件中每个字符

            Node x = root;
            while (!x.isLeaf()) {       //遍历,知道叶子结点
                if (BinaryStdIn.readBoolean()) {
                    x = x.right;
                } else {
                    x = x.left;
                }

            }

            BinaryStdOut.write(x.ch);
        }

        BinaryStdOut.close();
    }

参考

Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏SpringBoot

String、StringBuffer与StringBuilder之间区别

最近学习到StringBuffer,心中有好些疑问,搜索了一些关于String,StringBuffer,StringBuilder的东西,现在整理一下。

1022
来自专栏小樱的经验随笔

【python进阶】详解元类及其应用2

前言 在上一篇文章【python进阶】详解元类及其应用1中,我们提到了关于元类的一些前置知识,介绍了类对象,动态创建类,使用type创建类,这一节我们将继续接着...

2759
来自专栏Hongten

python开发_python代码风格(coding style)

1261
来自专栏chenjx85的技术专栏

leetcode-674-Longest Continuous Increasing Subsequence

2095
来自专栏个人分享

Scala第四章学习笔记(面向对象编程)

DelayedInit特质是为编译器提供的标记性的特质。整个构造器被包装成一个函数并传递给delayedInit方法。

881
来自专栏机器学习与自然语言处理

04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用

题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffm...

2857
来自专栏黑泽君的专栏

c语言基础学习04_条件判断语句

============================================================================= 涉及...

4521
来自专栏偏前端工程师的驿站

Java魔法堂:深入正则表达式API

目录                               一、前言 二、正则表达式的使用诉求 三、java.util.regex包 四、java.lan...

2115
来自专栏木东居士的专栏

通过源码分析 String、StringBuffer 和 StringBuilder

1833
来自专栏个人随笔

ADO.NET查询和操作数据库

stringbuilder 类 stringbuilder类:用来定义可变字符串 stringbulider Append(string value)   在结...

3455

扫码关注云+社区

领取腾讯云代金券