详解Huffman编码算法之Java实现

Huffman编码介绍

Huffman编码处理的是字符以及字符对应的二进制的编码配对问题,分为编码和解码,目的是压缩字符对应的二进制数据长度。我们知道字符存贮和传输的时候都是二进制的(计算机只认识0/1),那么就有字符与二进制之间的mapping关系。字符属于字符集(Charset), 字符需要通过编码(encode)为二进制进行存贮和传输,显示的时候需要解码(decode)回字符,字符集与编码方法是一对多关系(Unicode可以用UTF-8,UTF-16等编码)。理解了字符集,编码以及解码,满天飞的乱码问题也就游刃而解了。以英文字母小写a为例, ASCII编码中,十进制为97,二进制为01100001。ASCII的每一个字符都用8个Bit(1Byte)编码,假如有1000个字符要传输,那么就要传输8000个Bit。问题来了,英文中字母e的使用频率为12.702%,而z为0.074%,前者是后者的100多倍,但是确使用相同位数的二进制。可以做得更好,方法就是可变长度编码,指导原则就是频率高的用较短的位数编码,频率低的用较长位数编码。Huffman编码算法就是处理这样的问题。

Huffman编码Java实现

Huffman编码算法主要用到的数据结构是完全二叉树(full binary tree)和优先级队列。后者用的是Java.util.PriorityQueue,前者自己实现(都为内部类),代码如下:

static class Tree {
    private Node root; 

    public Node getRoot() {
      return root;
    } 

    public void setRoot(Node root) {
      this.root = root;
    }
  } 

  static class Node implements Comparable<Node> {
    private String chars = "";
    private int frequence = 0;
    private Node parent;
    private Node leftNode;
    private Node rightNode; 

    @Override
    public int compareTo(Node n) {
      return frequence - n.frequence;
    } 

    public boolean isLeaf() {
      return chars.length() == 1;
    } 

    public boolean isRoot() {
      return parent == null;
    } 

    public boolean isLeftChild() {
      return parent != null && this == parent.leftNode;
    } 

    public int getFrequence() {
      return frequence;
    } 

    public void setFrequence(int frequence) {
      this.frequence = frequence;
    } 

    public String getChars() {
      return chars;
    } 

    public void setChars(String chars) {
      this.chars = chars;
    } 

    public Node getParent() {
      return parent;
    } 

    public void setParent(Node parent) {
      this.parent = parent;
    } 

    public Node getLeftNode() {
      return leftNode;
    } 

    public void setLeftNode(Node leftNode) {
      this.leftNode = leftNode;
    } 

    public Node getRightNode() {
      return rightNode;
    } 

    public void setRightNode(Node rightNode) {
      this.rightNode = rightNode;
    }
  }

统计数据

既然要按频率来安排编码表,那么首先当然得获得频率的统计信息。我实现了一个方法处理这样的问题。如果已经有统计信息,那么转为Map<Character,Integer>即可。如果你得到的信息是百分比,乘以100或1000,或10000。总是可以转为整数。比如12.702%乘以1000为12702,Huffman编码只关心大小问题。统计方法实现如下:

public static Map<Character, Integer> statistics(char[] charArray) {
    Map<Character, Integer> map = new HashMap<Character, Integer>();
    for (char c : charArray) {
      Character character = new Character(c);
      if (map.containsKey(character)) {
        map.put(character, map.get(character) + 1);
      } else {
        map.put(character, 1);
      }
    } 

    return map;
  }

构建树

构建树是Huffman编码算法的核心步骤。思想是把所有的字符挂到一颗完全二叉树的叶子节点,任何一个非页子节点的左节点出现频率不大于右节点。算法为把统计信息转为Node存放到一个优先级队列里面,每一次从队列里面弹出两个最小频率的节点,构建一个新的父Node(非叶子节点), 字符内容刚弹出来的两个节点字符内容之和,频率也是它们的和,最开始的弹出来的作为左子节点,后面一个作为右子节点,并且把刚构建的父节点放到队列里面。重复以上的动作N-1次,N为不同字符的个数(每一次队列里面个数减1)。结束以上步骤,队列里面剩一个节点,弹出作为树的根节点。代码如下:

private static Tree buildTree(Map<Character, Integer> statistics,
      List<Node> leafs) {
    Character[] keys = statistics.keySet().toArray(new Character[0]); 

    PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
    for (Character character : keys) {
      Node node = new Node();
      node.chars = character.toString();
      node.frequence = statistics.get(character);
      priorityQueue.add(node);
      leafs.add(node);
    } 

    int size = priorityQueue.size();
    for (int i = 1; i <= size - 1; i++) {
      Node node1 = priorityQueue.poll();
      Node node2 = priorityQueue.poll(); 

      Node sumNode = new Node();
      sumNode.chars = node1.chars + node2.chars;
      sumNode.frequence = node1.frequence + node2.frequence; 

      sumNode.leftNode = node1;
      sumNode.rightNode = node2; 

      node1.parent = sumNode;
      node2.parent = sumNode; 

      priorityQueue.add(sumNode);
    } 

    Tree tree = new Tree();
    tree.root = priorityQueue.poll();
    return tree;
  }

编码

某个字符对应的编码为,从该字符所在的叶子节点向上搜索,如果该字符节点是父节点的左节点,编码字符之前加0,反之如果是右节点,加1,直到根节点。只要获取了字符和二进制码之间的mapping关系,编码就非常简单。代码如下:

public static String encode(String originalStr,
      Map<Character, Integer> statistics) {
    if (originalStr == null || originalStr.equals("")) {
      return "";
    } 

    char[] charArray = originalStr.toCharArray();
    List<Node> leafNodes = new ArrayList<Node>();
    buildTree(statistics, leafNodes);
    Map<Character, String> encodInfo = buildEncodingInfo(leafNodes); 

    StringBuffer buffer = new StringBuffer();
    for (char c : charArray) {
      Character character = new Character(c);
      buffer.append(encodInfo.get(character));
    } 

    return buffer.toString();
  }
private static Map<Character, String> buildEncodingInfo(List<Node> leafNodes) {
    Map<Character, String> codewords = new HashMap<Character, String>();
    for (Node leafNode : leafNodes) {
      Character character = new Character(leafNode.getChars().charAt(0));
      String codeword = "";
      Node currentNode = leafNode; 

      do {
        if (currentNode.isLeftChild()) {
          codeword = "0" + codeword;
        } else {
          codeword = "1" + codeword;
        } 

        currentNode = currentNode.parent;
      } while (currentNode.parent != null); 

      codewords.put(character, codeword);
    } 

    return codewords;
  }

解码

因为Huffman编码算法能够保证任何的二进制码都不会是另外一个码的前缀,解码非常简单,依次取出二进制的每一位,从树根向下搜索,1向右,0向左,到了叶子节点(命中),退回根节点继续重复以上动作。代码如下:

public static String decode(String binaryStr,
      Map<Character, Integer> statistics) {
    if (binaryStr == null || binaryStr.equals("")) {
      return "";
    } 

    char[] binaryCharArray = binaryStr.toCharArray();
    LinkedList<Character> binaryList = new LinkedList<Character>();
    int size = binaryCharArray.length;
    for (int i = 0; i < size; i++) {
      binaryList.addLast(new Character(binaryCharArray[i]));
    } 

    List<Node> leafNodes = new ArrayList<Node>();
    Tree tree = buildTree(statistics, leafNodes); 

    StringBuffer buffer = new StringBuffer(); 

    while (binaryList.size() > 0) {
      Node node = tree.root; 

      do {
        Character c = binaryList.removeFirst();
        if (c.charValue() == '0') {
          node = node.leftNode;
        } else {
          node = node.rightNode;
        }
      } while (!node.isLeaf()); 

      buffer.append(node.chars);
    } 

    return buffer.toString();
  }

测试以及比较

以下测试Huffman编码的正确性(先编码,后解码,包括中文),以及Huffman编码与常见的字符编码的二进制字符串比较。代码如下:

public static void main(String[] args) {
    String oriStr = "Huffman codes compress data very effectively: savings of 20% to 90% are typical, "
        + "depending on the characteristics of the data being compressed. 中华崛起";
    Map<Character, Integer> statistics = statistics(oriStr.toCharArray());
    String encodedBinariStr = encode(oriStr, statistics);
    String decodedStr = decode(encodedBinariStr, statistics); 

    System.out.println("Original sstring: " + oriStr);
    System.out.println("Huffman encoed binary string: " + encodedBinariStr);
    System.out.println("decoded string from binariy string: " + decodedStr); 

    System.out.println("binary string of UTF-8: "
        + getStringOfByte(oriStr, Charset.forName("UTF-8")));
    System.out.println("binary string of UTF-16: "
        + getStringOfByte(oriStr, Charset.forName("UTF-16")));
    System.out.println("binary string of US-ASCII: "
        + getStringOfByte(oriStr, Charset.forName("US-ASCII")));
    System.out.println("binary string of GB2312: "
        + getStringOfByte(oriStr, Charset.forName("GB2312")));
  } 

  public static String getStringOfByte(String str, Charset charset) {
    if (str == null || str.equals("")) {
      return "";
    } 

    byte[] byteArray = str.getBytes(charset);
    int size = byteArray.length;
    StringBuffer buffer = new StringBuffer();
    for (int i = 0; i < size; i++) {
      byte temp = byteArray[i];
      buffer.append(getStringOfByte(temp));
    } 

    return buffer.toString();
  } 

  public static String getStringOfByte(byte b) {
    StringBuffer buffer = new StringBuffer();
    for (int i = 7; i >= 0; i--) {
      byte temp = (byte) ((b >> i) & 0x1);
      buffer.append(String.valueOf(temp));
    } 

    return buffer.toString();
  }

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • java实现哈弗曼编码与反编码实例分享(哈弗曼算法)

    复制代码 代码如下: //哈弗曼编码的实现类public class HffmanCoding {    private int charsAndWeight[][];// [][0]是 字符,[][1]存放的是字符的权值(次数)    private int hfmcoding[][];// 存放哈弗曼树    private int i = 0;// 循环变量    private String hcs[];    public HffmanCoding(int[][] chars) {  

  • 详解Huffman编码算法之Java实现

    Huffman编码介绍 Huffman编码处理的是字符以及字符对应的二进制的编码配对问题,分为编码和解码,目的是压缩字符对应的二进制数据长度.我们知道字符存贮和传输的时候都是二进制的(计算机只认识0/1),那么就有字符与二进制之间的mapping关系.字符属于字符集(Charset), 字符需要通过编码(encode)为二进制进行存贮和传输,显示的时候需要解码(decode)回字符,字符集与编码方法是一对多关系(Unicode可以用UTF-8,UTF-16等编码).理解了字符集,编码以及解码,满

  • Spring学习笔记1之IOC详解尽量使用注解以及java代码

    在实战中学习Spring,本系列的最终目的是完成一个实现用户注册登录功能的项目. 预想的基本流程如下: 1.用户网站注册,填写用户名.密码.email.手机号信息,后台存入数据库后返回ok.(学习IOC,mybatis,SpringMVC的基础知识,表单数据验证,文件上传等) 2.服务器异步发送邮件给注册用户.(学习消息队列) 3.用户登录.(学习缓存.Spring Security) 4.其他. 边学习边总结,不定时更新.项目环境为Intellij + Spring4. 一.准备工作. 1.m

  • 详解基于IDEA2020.1的JAVA代码提示插件开发例子

    之前因为项目组有自己的代码规范,为了约束平时的开发规范,于是基于2019.1.3版本开发了一个代码提示的插件.但是在把IDEA切换到2020.1版本的时候,却发现疯狂报错,但是网上关于IDEA插件开发的相关文章还是不够多,只能自己解决.于是根据官方的SDK文档,使用Gradle重新构建了一下项目,把代码拉了过来.下文会根据2020.1版本简单开发一个代码异常的提示插件,把容易踩坑的地方提示一下. 1.首先先根据IDEA插件开发官方文档,用Gradle新建一个project 选中file -> n

  • 详解多云架构下的JAVA微服务技术解析

    微服务生态 微服务生态本质上是一种微服务架构模式的实现,包括微服务开发SDK,以及微服务基础设施. 目前比较成熟的 JAVA 微服务生态包括 servicecomb(华为), spring-cloud (Pivotal), dubbo(阿里), tsf(腾讯)等.gRPC.Thrift 等也用于内部服务之间的通信,但是微服务基础设施比较欠缺. 核心的微服务基础设施包括:注册中心.配置中心.应用网关.此外,分布式事物管理.计划任务.调用链跟踪系统等也是微服务基础设施的组成部分.完整的微服务基础实施

  • C语言详解数据结构与算法中枚举和模拟及排序

    目录 枚举 连号区间数 递增三元组 二分 双指针 前缀和 模拟 特别数的和 错误票据 排序 快速排序 归并排序 枚举 连号区间数 来源:第四届蓝桥杯省赛C++B组,第四届蓝桥杯省赛JAVAB组 小明这些天一直在思考这样一个奇怪而有趣的问题: 在 1∼N 的某个排列中有多少个连号区间呢? 这里所说的连号区间的定义是: 如果区间 [L,R] 里的所有元素(即此排列的第 L 个到第 R 个元素)递增排序后能得到一个长度为 R−L+1 的“连续”数列,则称这个区间连号区间. 当 N 很小的时候,小明可以

  • 详解C++图搜索算法之双端队列广搜

    目录 广度优先遍历 双端队列BFS 例题:AcWing 175. 电路维修 解题思路 AC代码 广度优先遍历 广度优先遍历是一种按照层次顺序进行访问的方法,它具有以下两种重要性质: 在访问完所有第i层的结点后,才会去访问第i+1层的结点 任意时刻,队列中至多有两个层次的结点.若其中一部分结点属于第i层,则另一部分结点属于第i+1层,并且所有第i层结点排在第i+1层之前.也就是说,广度优先遍历队列中的元素关于层次满足 双端队列BFS 在最基本的广度优先搜索中,每次沿着分支的扩展都记为“一步”,我们

  • 图文详解牛顿迭代算法原理及Python实现

    目录 1.引例 2.牛顿迭代算法求根 3.牛顿迭代优化 4 代码实战:Logistic回归 1.引例 给定如图所示的某个函数,如何计算函数零点x0 在数学上我们如何处理这个问题? 最简单的办法是解方程f(x)=0,在代数学上还有著名的零点判定定理 如果函数y=f(x)在区间[a,b]上的图象是连续不断的一条曲线,并且有f(a)⋅f(b)<0,那么函数y=f(x)在区间(a,b)内有零点,即至少存在一个c∈(a,b),使得f(c)=0,这个c也就是方程f(x)=0的根. 然而,数学上的方法并不一定

  • 详解APP微信支付(java后台_统一下单和回调)

    1.微信配置信息 global.properties 2.方法wxpay用于生成预支付订单信息 方法notifyWeiXinPay用于微信支付成功后的回调, 注意: 在手机端使用微信支付成功后,微信服务器会根据提供的回调地址进行回调, parameterMap.put("notify_url", wxnotify); (见下面代码) 在局域网是无法进行回调的,必须将你的服务端放在公网上进行测试, 回调函数会被多次调用,如果第一次成功后,你可以将业务数据状态标志为已处理, 对于相同订单的

  • 详解直接插入排序算法与相关的Java版代码实现

    直接插入排序 直接插入排序的思路很容易理解,它是这样的: 1.把待排序的数组分成已排序和未排序两部分,初始的时候把第一个元素认为是已排好序的. 2.从第二个元素开始,在已排好序的子数组中寻找到该元素合适的位置并插入该位置. 3.重复上述过程直到最后一个元素被插入有序子数组中. 4.排序完成. 示例: 思路很简单,但代码并非像冒泡排序那么好写.首先,如何判断合适的位置?大于等于左边.小于等于右边?不行,很多边界条件需要考虑,而且判断次数太多.其次,数组中插入元素,必然需要移动大量元素,如何控制它们

  • 详解DES加密算法及在Java程序中的使用示例

    DES加密算法 DES全称为Data Encryption Standard,即数据加密标准,是一种使用密钥加密的块算法,1976年被美国联邦政府的国家标准局确定为联邦资料处理标准(FIPS),随后在国际上广泛流传开来. DES算法的入口参数有三个:Key.Data.Mode.其中Key为7个字节共56位,是DES算法的工作密钥;Data为8个字节64位,是要被加密或被解密的数据;Mode为DES的工作方式,有两种:加密或解密. DES算法把64位的明文输入块变为64位的密文输出块,它所使用的密

随机推荐