专栏首页云霄雨霁数据压缩----霍夫曼树和霍夫曼压缩

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

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

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

构造霍夫曼树:

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

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 条评论
登录 后参与评论

相关文章

  • SpringMVC--Json数据交互笔记

    SuperHeroes
  • 加权无向图----Kruskal算法实现最小生成树

    SuperHeroes
  • 查找----基于无序链表

    SuperHeroes
  • 一天一大 lee(有序链表转换二叉搜索树)难度:中等-Day20200818

    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

    前端小书童
  • 秒懂ReactJS | TW洞见

    今日洞见 文章作者/配图来自ThoughtWorks:贾朝阳。 本文所有内容,包括文字、图片和音视频资料,版权均属ThoughtWorks公司所有,任何媒体、网...

    ThoughtWorks
  • SAP最佳业务实践:FI–现金管理(160)-20银企对账-供应商付款-转账-FF67手动输入银行对帐单

    4.6.3 FF67手动输入银行对帐单 收到银行对账单,执行对供应商的付款,形成财务凭证如下: 借:银行结算(中间科目) 贷:银行现金 1. 输入一张...

    SAP最佳业务实践
  • 有备无患——数据中心基础设施备品备件管理

    随着云技术、互联网+等理念的不断发展,数据中心行业再次迎来了大规模发展的契机。大量的新技术和新模式推动着数据中心基础设施架构和体系的高歌猛进,而基础设施运营的实...

    腾讯数据中心
  • 微前端的设计理念与实践初探

    微服务与微前端,都是希望将某个单一的单体应用,转化为多个可以独立运行、独立开发、独立部署、独立维护的服务或者应用的聚合,从而满足业务快速变化及分布式多团队并行开...

    王下邀月熊
  • 如何让java中的注释代码执行?

    原因:java编译器会处理unicode字符,\u000d以及\u000a 正好对应“\r”回车、“\n”换行,经过编译器处理后,等效于下面的代码:

    菩提树下的杨过
  • python 性能的优化

    NumPy的创始人Travis,创建了CONTINUUM,致力于将Python大数据处理方面的应用。 推出的Numba项目能够将处理NumPy数组的Pytho...

    黑白格

扫码关注云+社区

领取腾讯云代金券