java实现哈夫曼压缩的实例

哈夫曼压缩的原理:

通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码.

其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短;

出现频率越低的字节其路径长度越长.从而达到压缩的目的.

如何构造哈夫曼树?

一.  定义字节类 

我的字节类定义了一下属性

   public int data;//节点数据
public int weight;//该节点的权值
public int point;//该节点所在的左右位置 0-左 1-右
private NodeData parent;//父节点引用
private NodeData left;//左节点引用
private NodeData right;//右节点引用

二.建哈夫曼树

1.定义一个存储字节信息的数组: int array_Bytes[256];

其中数组的下标[0,256)代表字节数值(一个字节8位,其值在[0,256)范围内);数组存储字节出现的次数.

2.遍历要压缩的文件,统计字节出现的次数.

 InputStream data = new FileInputStream(path);
 /******** 文件中字符个数 ********/
 int number = data.available();
 for (int i = 0; i < number; i++) {
int b = data.read();
array_Bytes[b] ++;
 }
data.close();

3.将字节类对象存入优先队列

4.运用HashMap 构造码表

哈夫曼压缩代码如下:

1.字节类

package compressFile;
/**
 * 节点数据
 * 功能:定义数据,及其哈夫曼编码
 * @author Andrew
 *
 */
public class NodeData {
  public NodeData(){ 

  }
  public int data;//节点数据
  public int weight;//该节点的权值
  public int point;//该节点所在的左右位置 0-左 1-右
  private NodeData parent;
  private NodeData left;
  private NodeData right; 

  public int getData(){
    return data;
  }
  public NodeData getParent() {
    return parent;
  }
  public void setParent(NodeData parent) {
    this.parent = parent;
  }
  public NodeData getLeft() {
    return left;
  }
  public void setLeft(NodeData left) {
    this.left = left;
  }
  public NodeData getRight() {
    return right;
  }
  public void setRight(NodeData right) {
    this.right = right;
  }
}

2.统计字节的类,并生成码表

package compressFile; 

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue; 

/**
 * 统计指定文件中每个字节数 功能:定义数组,将文件中的字节类型及个数写入数组
 * 创建优先队列和哈夫曼树
 * @author Andrew
 *
 */
public class StatisticBytes { 

  /**
   * 第一步:
   * 统计文件中字节的方法
   *
   * @param path
   *      所统计的文件路径
   * @return 字节个数数组
   */
  private int[] statistic(String path) {
    /******储存字节数据的数组--索引值代表字节类型-存储值代表权值******/
    int[] array_Bytes = new int[256];
    try {
      InputStream data = new FileInputStream(path);
      BufferedInputStream buffered = new BufferedInputStream(data);
      /******** 文件中字符个数 ********/
      int number = data.available();
      System.out.println("字节个数》》》"+number);
      for (int i = 0; i < number; i++) {
        int b = data.read();
        array_Bytes[b] ++;
      } 

      data.close();
    } catch (IOException e) {
      e.printStackTrace();
    }
    return array_Bytes;
  }
  /**
   * 第二步:
   * 根据统计的字节数组创建优先队列
   * @param array 统计文件字节的数组
   * @return    优先队列
   */
  private PriorityQueue<NodeData> createQueue(int[] array){
    //定义优先队列,根据数据的权值排序从小到大
    PriorityQueue<NodeData> queue =
        new PriorityQueue<NodeData>(array.length,new Comparator<NodeData>(){
      public int compare(NodeData o1, NodeData o2) {
        return o1.weight - o2.weight;
      }
    }); 

    for(int i=0; i<array.length; i++){
      if(0 != array[i]){
        NodeData node = new NodeData();
        node.data = i;//设置该节点的数据
        node.weight = array[i];//设置该节点的权值
        queue.add(node);
      }
    }
    return queue;
  }
  /**
   * 第三步:
   * 根据优先队列创建哈夫曼树
   * @param queue  优先队列
   * @return     哈夫曼树根节点
   */
  private NodeData createTree(PriorityQueue<NodeData> queue){
    while(queue.size() > 1){ 

      NodeData left = queue.poll();//取得左节点
      NodeData right = queue.poll();//取得右节点 

      NodeData root = new NodeData();//创建新节点
      root.weight = left.weight + right.weight; 

      root.setLeft(left);
      root.setRight(right);
      left.setParent(root);
      right.setParent(root); 

      left.point = 0;
      right.point = 1; 

      queue.add(root);
    }
    NodeData firstNode = queue.poll();
    return firstNode;
  }
  /**
   * 第四步:
   * 寻找叶节点并获得哈夫曼编码
   * @param root  根节点
   */
  private void achievehfmCode(NodeData root){ 

    if(null == root.getLeft() && null == root.getRight()){
      array_Str[root.data] = this.achieveLeafCode(root);
      /**
       *
       * 得到将文件转换为哈夫曼编码后的文集长度
       * 文件长度 = 一种编码的长度 * 该编码出现的次数
       */
      WriteFile.size_File += (array_Str[root.data].length())*(root.weight);
    }
    if(null != root.getLeft()){
      achievehfmCode(root.getLeft());
    }
    if(null != root.getRight()){
      achievehfmCode(root.getRight());
    }
  }
  /**
   * 根据某叶节点获得该叶节点的哈夫曼编码
   * @param leafNode  叶节点对象
   */
  private String achieveLeafCode(NodeData leafNode){
    String str = "";
    /*****************存储节点 01 编码的队列****************/
    List<Integer> list_hfmCode = new ArrayList<Integer>();
    list_hfmCode.add(leafNode.point);
    NodeData parent = leafNode.getParent(); 

    while(null != parent){
      list_hfmCode.add(parent.point);
      parent = parent.getParent();
    } 

    int size = list_hfmCode.size();
    for(int i=size-2; i>=0; i--){
      str += list_hfmCode.get(i);
    }
    System.out.println(leafNode.weight+"的哈夫曼编码为>>>"+str);
    return str;
  }
  /**
   * 第五步:
   * 根据获得的哈夫曼表创建 码表
   * Integer 为字节byte [0~256)
   * String 为哈夫曼编码
   * @return 码表
   */
  public Map<Integer,String> createMap(){
    int[] hfm_Codes = this.statistic("F:\\JAVA\\压缩前.txt");//获得文件字节信息
    PriorityQueue<NodeData> queue = this.createQueue(hfm_Codes);//获得优先队列
    /*
     * 获得哈夫曼树的根节点,
     * this.createTree(queue)方法调用之后(含有poll()),queue.size()=0
     */
    NodeData root = this.createTree(queue);
    this.achievehfmCode(root);//获得哈夫曼编码并将其存入数组中 

    Map<Integer,String> map = new HashMap<Integer,String>();
    for(int i=0; i<256; i++){
      if(null != array_Str[i]){
        map.put(i, array_Str[i]);
      }
    }
    return map;
  }
  /**
   * 存储字节哈夫曼编码的数组
   * 下标:字节数据
   * 元素:哈夫曼编码
   */
  public String[] array_Str = new String[256];
}

3.将码表写入压缩文件并压缩正文

package compressFile; 

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataOutputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Iterator;
import java.util.Map;
import java.util.Set; 

/**
 * 将码表和文件写入新的文件中
 * @author Andrew
 *
 */
public class WriteFile { 

  // 实例化创建码表类对象
  private StatisticBytes statistic = new StatisticBytes();
  private Map<Integer, String> map = statistic.createMap();// 获得码表
  // 字节接收变量,接收哈夫曼编码连接够8位时转换的字节
  private int exmpCode;
  public static int size_File; 

  public static void main(String[] args) {
    WriteFile writeFile = new WriteFile();
    writeFile.init();
  } 

  private void init() { 

    String filePath = "F:\\JAVA\\压缩后.txt";
    this.writeFile(filePath);
  } 

  /**
   * 第一步: 向文件中写入码表
   *
   * @param dataOut
   *      基本数据流
   */
  private void writeCodeTable(DataOutputStream dataOut) {
    Set<Integer> set = map.keySet();
    Iterator<Integer> p = set.iterator(); 

    try {
      //向文件中写入码表的长度
      dataOut.writeInt(map.size());
      while (p.hasNext()) {
        Integer key = p.next();
        String hfmCode = map.get(key); 

        dataOut.writeInt(key);//写入字节
        //写入哈夫曼编码的长度
        dataOut.writeByte(hfmCode.length());
        for(int i=0; i<hfmCode.length(); i++){
          dataOut.writeChar(hfmCode.charAt(i));//写入哈夫曼编码
        }
      }
    } catch (IOException e) {
      e.printStackTrace();
    }
  } 

  /**
   * 第二步: 向压缩文件中写入编码
   *
   * @param path
   */
  private void writeFile(String path) { 

    try {
      // 输入流
      FileInputStream in = new FileInputStream("F:\\JAVA\\压缩前.txt");
      BufferedInputStream bIn = new BufferedInputStream(in);
      // 输出流
      FileOutputStream out = new FileOutputStream(path);
      DataOutputStream dataOut = new DataOutputStream(out);
      BufferedOutputStream bOut = new BufferedOutputStream(out);
      // 向文件中写入码表
      this.writeCodeTable(dataOut);
      /********************写入补零个数*********************/
      if(0 != size_File % 8){
        dataOut.writeByte(8 - (size_File % 8));
      } 

      String transString = "";//中转字符串,存储字符串直到size大于8
      String waiteString = "";//转化字符串, 

      int size_File = in.available();
      for(int i=0; i<size_File; i++){
        int j = bIn.read();
        System.out.println("]]]]]]]]]]]>>");
        waiteString = this.changeStringToByte(transString + statistic.array_Str[j]);
        if(waiteString != ""){
          bOut.write(exmpCode);
          transString = waiteString;
        }else{
          transString += statistic.array_Str[j];
        }
      }
      if("" != transString){
        int num = 8-transString.length()%8;
        for(int i=0; i<num; i++){
          transString += 0;
        }
      }
      transString = this.changeStringToByte(transString);
      bOut.write(exmpCode); 

      bIn.close();
      bOut.flush();
      bOut.close();
      out.close();
    } catch (IOException e) {
      e.printStackTrace();
    }
  } 

  /**
   * 附属第二步:
   * 将字符串转化为byte
   *
   * @param str
   *      要转化的字符串
   * @return 如果str的长度大于8返回一个截取前8位后的str
   *     否则返回""
   */
  private String changeStringToByte(String str) {
    if (8 <= str.length()) {
      exmpCode = ((str.charAt(0) - 48) * 128
          + (str.charAt(1) - 48) * 64 + (str.charAt(2) - 48) * 32
          + (str.charAt(3) - 48) * 16 + (str.charAt(4) - 48) * 8
          + (str.charAt(5) - 48) * 4 + (str.charAt(6) - 48) * 2
          + (str.charAt(7) - 48));
      str = str.substring(8);
      return str;
    }
    return "";
  }
}

二.哈夫曼解压 

原理:将压缩的逆向,即你是如何压缩的就怎样去解压。相当于你根据自己定义的协议进行压缩与解压缩文件。

代码如下:

package decompressionFile; 

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set; 

/**
 * 解压文件 从压缩文件中读入数据解压
 *
 * @author Andrew
 *
 */
public class ReadFile {
  /**
   * 码表 Integter: 字节 [0,255) String: 哈夫曼编码
   */
  private Map<Integer, String> code_Map = new HashMap<Integer, String>(); 

  public static void main(String[] args) {
    ReadFile readFile = new ReadFile();
    readFile.readFile();
  } 

  /**
   * 第一步: 从文件中读出码表
   *
   * @param dataInput
   *      基本数据输入流
   *
   */
  private void readMap(DataInputStream dataInput) { 

    try {
      // 读出码表的长度
      int size_Map = dataInput.readInt();
      /**************** 读出码表信息 ************************************/
      for (int i = 0; i < size_Map; i++) {
        int data = dataInput.readInt();// 读入字节信息
        String str = "";// 哈夫曼编码
        // 哈夫曼编码长度,存储时以字符写入
        byte codeSize = dataInput.readByte();
        for (byte j = 0; j < codeSize; j++) {
          str += dataInput.readChar();
        }
        System.out.println("&&&&&&&&&&>>>>"+data+"!!!!!!!>>"+str);
        code_Map.put(data, str);
      }
      /***************************************************************/
    } catch (IOException e) {
      e.printStackTrace();
    }
  } 

  /**
   * 第二步: 解压正式文件
   */
  private void readFile() {
    try {
      // 文件输入流
      InputStream input = new FileInputStream("F:\\JAVA\\压缩后.txt");
      // BufferedInputStream bIn = new BufferedInputStream(input);
      DataInputStream dInput = new DataInputStream(input);
      // 调用读出码表的方法
      this.readMap(dInput);
      byte zerofill = dInput.readByte();// 读出文件补零个数
      System.out.println("补零个数》》》>>>>"+zerofill);
      // 文件输出流
      OutputStream out = new FileOutputStream("F:\\JAVA\\解压后.txt"); 

      String transString = "";//接收用于匹配码表中哈夫曼编码的字符串
      String waiteString = "";//接收截取哈夫曼编码后剩余的字符串 

      /***********************************不耗内存的方法*****************************************/
      int readCode = input.read();//从压缩文件中读出一个数据
      int size = input.available();
      for(int j=0; j<=size; j++){
        System.out.println("readCodereadCodereadCode》》>>>>"+readCode);
        waiteString += this.changeIntToBinaryString(readCode);//将读到的整数转化为01字符串
        for(int i=0; i<waiteString.length(); i++){
          //将从文件中读出的01串一个一个字节的截取添加与码表中的哈夫曼编码比较
          transString += waiteString.charAt(i);
          if(this.searchHC(transString, out)){
//           waiteString = waiteString.substring( i+1 );
            transString = "";
          }
        }
        waiteString = "";
        readCode = input.read();
        if(j == size-1){
          break;
        }
      }
      /************************************处理最后一个字***************************************/
//     int lastByte = input.read();
      String lastWord = this.changeIntToBinaryString(readCode);
      waiteString = transString + lastWord.substring(0, 8-zerofill);
      transString = "";
      for(int i=0; i<waiteString.length(); i++){
        //将从文件中读出的01串一个一个字节的截取添加与码表中的哈夫曼编码比较
        transString += waiteString.charAt(i);
        if(this.searchHC(transString, out)){
//         waiteString = waiteString.substring( i+1 );
          transString = "";
        }
      }
//     this.searchHC(transString, out);
      /***********************************队列法,耗内存****************************************/
//     int readCode = input.read();//从压缩文件中读出一个数据
//     List<Character> list = new ArrayList<Character>();
//     while(-1 != readCode){
//       String str = this.changeIntToBinaryString(readCode);
//       for(int i=0; i<str.length(); i++){
//         list.add(str.charAt(i));
//       }
//       readCode = input.read();
//     }
//     for(int j=0; j<list.size()-zerofill; j++){
//       transString += list.get(j);
//       if(this.searchHC(transString, out)){
//         transString = "";
//       }
//     }
      /*****************************************************************************************/
      input.close();
      out.close();
    } catch (IOException e) {
      e.printStackTrace();
    }
  }
  /**
   * 将从文件中读到的01 串与码表中的哈夫曼编码比较
   * 若在码表中含有与之对应的哈夫曼编码则将码表中对应的
   * 数据写入解压文件,否则不写入
   * @param str 从文件中读到的01 字符串
   * @param out 文件输出流
   * @return   若写入文件返回true,否则返回false
   * @throws IOException 写入发生错误时抛出异常
   */
  private boolean searchHC(String str, OutputStream out) throws IOException{
    Set<Integer> set = code_Map.keySet();
    Iterator<Integer> p = set.iterator();
    while (p.hasNext()) {
      Integer key = p.next();//获得码表中的字节数据
      String hfmCode = code_Map.get(key);//获得哈夫曼编码
      if(hfmCode.equals(str)){
        out.write(key);
        return true;
      }
    }
    return false;
  }
  /**
   * 根据 "除2取余,逆序排列"法
   * 将十进制数字转化为二进制字符串
   * @param a  要转化的数字
   * @return  01 字符串
   */
  private String changeIntToBinaryString(int a) {
    int b = a;
    int count = 0; //记录 a 可转化为01串的个数,在不够8为时便于补零
    String str = "";// 逆序二进制字符串
    String exmpStr = "";// 顺序二进制字符串 

    while (a != 0) {
      b = a/2;
      if (a % 2 != 0) {
        str += 1;
      } else {
        str += 0;
      }
      a = b;
      count++;
    }
    //不够8位的地方补零
    for (int i = 0; i < 8 - count; i++) {
      str += 0;
    }
    //将转化后的二进制字符串正序
    for (int j = 7; j >= 0; j--) {
      System.out.print(str.charAt(j));
      exmpStr += str.charAt(j);
    }
    System.out.println("转化后的字符串>>>>>>>>>"+exmpStr);
    return exmpStr;
  }
}
(0)

相关推荐

  • 图文详解JAVA实现哈夫曼树

    前言  我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的"最优二叉树",为了纪念他呢,我们称之为"哈夫曼树".哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等.今天一起来看看哈夫曼树到底是什么东东. 概念 当然,套路之一,首先我们要了解一些基本概念. 1.路径长度:从树中的一个结点到另一个结点之间的分支构成这两个结点的路径,路径上的分支数目称为路径长度. 2.树的路径长度:从树根到每一个结点的路径长度之和,我们所说的完全

  • java哈夫曼树实例代码

    本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.Queue; class Node<T> implements Comparable<Node<T>>{ private T

  • java实现哈夫曼压缩的实例

    哈夫曼压缩的原理: 通过统计文件中每个字节出现的频率,将8位的01串转换为位数较短的哈夫曼编码. 其中哈夫曼编码是根据文件中字节出现的频率构建的,其中出现频率越高的字节,其路径长度越短; 出现频率越低的字节其路径长度越长.从而达到压缩的目的. 如何构造哈夫曼树? 一.  定义字节类  我的字节类定义了一下属性 public int data;//节点数据 public int weight;//该节点的权值 public int point;//该节点所在的左右位置 0-左 1-右 privat

  • Java之哈夫曼压缩原理案例讲解

    1. 哈夫曼压缩原理 首先要明确一点,计算机里面所有的文件都是以二进制的方式存储的. 在计算机的存储单元中,一个ASCII码值占一个字节,1个字节等于8位(1Byte = 8bit) 可以参考这个网站: ASCII码在线转换计算器 以"JavaJavaJavaJavaJavaJava"这个字符串为例,它在计算机内部是这样存储的(每一个字符的ASCII码转换为二进制存储起来): public static void main(String[] args) { String beforeS

  • java实现哈夫曼压缩与解压缩的方法

    一哈夫曼树以及文件压缩原理: 1.哈夫曼树 : 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树.哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近(频率越高的结点离根越进). 以 下数组为例,构建哈夫曼树 int a[] = {0,1,2,3,4,5,6,7,8} 我们可以发现以下规律 1:9个数构成的哈夫曼树一共有17个结点,也就是可以n个数可以生产2*n-1个结点 2:数字越大的数离根节点越近,越小的数离根节点越近.

  • C++数据结构之文件压缩(哈夫曼树)实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • Java利用哈夫曼编码实现字符串压缩

    赫夫曼编码基本介绍 1) 赫夫曼编码也翻译为 哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式, 属于一种程序算法 2) 赫夫曼编码是赫哈夫曼树在电讯通信中的经典的应用之一. 3) 赫夫曼编码广泛地用于数据文件压缩.其压缩率通常在 20%-90%之间 4) 赫夫曼码是可变字长编码(VLC)的一种.Huffman 于 1952 年提出一种编码方法,称之为最佳编码 在通信领域中几种信息处理方式的区别(以字符串" i like like like java do you li

  • java实现哈夫曼文件解压缩

    本文实例为大家分享了java实现哈夫曼文件解压缩的具体代码,供大家参考,具体内容如下 1.哈夫曼压缩对已经经过压缩处理的文件压缩率比较低,比如ppt和视频. 2.这个程序主要涉及到集合.树.IO相关知识. 字符的统计可以用map集合进行统计. 哈夫曼树的构建过程也并不复杂: ①先对树的集合按照根节点大小进行排序 ②拿出根节点数值最小的两棵树,用它两构建成一颗新的树: ③从集合中删除之前那两颗根节点最小的数: ④把新生成的树加入到集合中 一直循环重复上面的过程,直到集合的大小变成1为止: 写出.读

  • Java实现赫夫曼树(哈夫曼树)的创建

    目录 一.赫夫曼树是什么? 1.路径和路径长度 2.节点的权和带权路径长度 3.树的带权路径长度 二.创建赫夫曼树 1.图文创建过程 2.代码实现 一.赫夫曼树是什么? 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 图1 一棵赫夫曼树 1.路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.

  • 如何用Java实现啥夫曼编码

    大家可能会想,程序和第三方提供了很多压缩方式,何必自己写压缩代码呢?不错,如GZIP这样的压缩工具很多,可是在某些情况下(如文本内容小且字符不重复),GZIP压缩后会比原始文本还要大.所以在某些特殊情况下用自己的压缩方式可以更优. 大家可能早已忘记了在学校学习的哈夫曼知识,可以先在百度百科了解一下哈夫曼知识:http://baike.baidu.com/view/127820.htm 哈夫曼思想:统计文本字符重复率,求出各字符权值,再构造出一颗最优二叉树(又称哈夫曼树),然后给每个叶子结点生成一

  • C++ 哈夫曼树对文件压缩、加密实现代码

    在以前写LZW压缩算法的时候,遇到很多难受的问题,基本上都在哈夫曼编码中解决了,虽然写这代码很费神,但还是把代码完整的码出来了,毕竟哈夫曼这个思想确实很牛逼.哈夫曼树很巧妙的解决了当时我在LZW序列化的时候想解决的问题,就是压缩后文本的分割.比如用lzw编码abc,就是1,2,3.但这个在存为文件的时候必须用分割符把1,2,3分割开,非常浪费空间,否则会和12 23 123 产生二义性.而哈夫曼树,将所有char分布在叶节点上,在还原的时候,比如1101110,假设110是叶节点,那么走到110

随机推荐