数据压缩----霍夫曼树和霍夫曼压缩

霍夫曼压缩的思想:使用较少的比特表示出现频繁的字符而使用较多的比特表示使用较少的字符。这样表示字符串所使用的总比特数就会减少。

前提:所有字符编码都不会成为其他字符编码的前缀。使用霍夫曼树可以保证这个前提的成立。

构造霍夫曼树:

首先定义霍夫曼树的结点类

private static class Node implements Comparable<Node> {
    private final char ch;
    private final int freq;
    private final Node left, right;

    Node(char ch, int freq, Node left, Node right) {
        this.ch    = ch;
        this.freq  = freq;
        this.left  = left;
        this.right = right;
    }
    private boolean isLeaf() { return (left == null) && (right == null); }
    public int compareTo(Node that) { return this.freq - that.freq; }
}

然后构建霍夫曼树:

霍夫曼树是一个二轮算法,它需要扫描目标字符串两次才能压缩它。第一次扫描统计每个字符出现的频率,第二次扫描根据生成的编译表压缩。

构造过程如下:为每个字符创建一个独立的结点(可以看成只有一个结点的树)。首先找到两个频率最小的结点,然后创建一个以这两个结点为子结点的新节点(新节点的频率值为两个子结点频率值之和);这个操作会使森林中树的数量减一。不断重复这个过程直到只剩下一棵树为止。这样,从树的根结点到叶结点的路径就是叶结点中字符对应的霍夫曼编码。

 private static Node buildTrie(int[] freq) {
    MinPQ<Node> pq = new MinPQ<Node>();
    for (char i = 0; i < R; i++)
        if (freq[i] > 0)
            pq.insert(new Node(i, freq[i], 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();
}

解码操作:

根据霍夫曼树将比特流解码:根据比特流的输入从根节点向下移动(遇到0走左子结点,遇到1走右子结点),遇到叶结点后,输出该叶结点的字符并回到根结点。

 public static void expand() {
    Node root = readTrie(); 
    int length = BinaryStdIn.readInt();

    for (int i = 0; i < length; i++) {
        Node x = root;
        while (!x.isLeaf()) {
            boolean bit = BinaryStdIn.readBoolean();
            if (bit) x = x.right;
            else     x = x.left;
        }
        BinaryStdOut.write(x.ch);
   }
   BinaryStdOut.close();
}

压缩操作:

压缩操作是根据构造的编译表实现的。根据霍夫曼树建立一张字符和路径对应的二进制字符串相联系的表,然后扫描目标字符串,每读入一个字符,查表得到相应的二进制字符串并输出即可。

构建编译表:

 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;
    }
}

使用编译表进行压缩:

for (int i = 0; i < input.length; i++) {
        String code = st[input[i]];
        for (int j = 0; j < code.length(); j++) {
            if (code.charAt(j) == '0')
                BinaryStdOut.write(false);
            else (code.charAt(j) == '1') 
                BinaryStdOut.write(true);
        }
    }

对于任意前缀码,编码后的比特字符串长度等于霍夫曼树的加权外部路径长度。

给定一个含有r个符号的集合和它们的频率,霍夫曼算法所构造的前缀码是最优的。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏LeetCode

2个线性表查找的优化

实际上,如果待查的数据比较均匀,那么1/2是一个很好的选择,一旦待查数据中的数据是极度不均匀的,那么就需要考虑插值查找法。

1204
来自专栏数据结构与算法

P3386 【模板】二分图匹配

题目背景 二分图 题目描述 给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数 输入输出格式 输入格式: 第一行,n,m,e 第二至e+1行,每...

3447
来自专栏计算机视觉与深度学习基础

Leetcode 282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all pos...

3516
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java提高十八】Map接口集合详解

四、Map接口 Map与List、Set接口不同,它是由一系列键值对组成的集合,提供了key到Value的映射。同时它也没有继承Collecti...

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

ZOJ 1403&&HDU 1015 Safecracker【暴力】

Safecracker ---- Time Limit: 2 Seconds      Memory Limit: 65536 KB ---- === Op t...

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

Codeforces 626C Block Towers(二分)

C. Block Towers time limit per test:2 seconds memory limit per test:256 megabyte...

2785
来自专栏应用案例

数据结构试题库答案算法设计题

算法设计题(10分) (1)阅读下列递归算法,写出非递归方法实现相同功能的C程序。 void test(int &sum) { int x; scanf(...

2628
来自专栏从流域到海域

Python map()函数

MapReduce: Simplified Data Processing on Large Clusters Jeffrey Dean and Sanj...

2749
来自专栏我是东东强

数据结构之栈与队列(优先队列/堆)

栈与队列是两种重要的特殊线性表,从结构上讲,两者都是线性表,但从操作上讲,两者支持的基本操作却只是线性表操作的子集,是操作受限制的线性表。栈与队列两者最大的区别...

1382
来自专栏java思维导图

JAVA容器-自问自答学ArrayList

前言 这次我和大家一起学习HashMap,HashMap我们在工作中经常会使用,而且面试中也很频繁会问到,因为它里面蕴含着很多知识点,可以很好的考察个人基础。但...

3699

扫码关注云+社区

领取腾讯云代金券