资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

怎么利用java语言实现一个哈夫曼压缩功能

本篇文章给大家分享的是有关怎么利用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 createQueue(int[] array){ 
    //定义优先队列，根据数据的权值排序从小到大 
    PriorityQueue queue =  
        new PriorityQueue(array.length,new Comparator(){ 
      public int compare(NodeData o1, NodeData o2) { 
        return o1.weight - o2.weight; 
      } 
    }); 
     
    for(int i=0; i 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 list_hfmCode = new ArrayList(); 
    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 createMap(){ 
    int[] hfm_Codes = this.statistic("F:\\JAVA\\压缩前.txt");//获得文件字节信息 
    PriorityQueue queue = this.createQueue(hfm_Codes);//获得优先队列 
    /* 
     * 获得哈夫曼树的根节点， 
     * this.createTree(queue)方法调用之后(含有poll())，queue.size()=0 
     */ 
    NodeData root = this.createTree(queue); 
    this.achievehfmCode(root);//获得哈夫曼编码并将其存入数组中 
     
    Map map = new HashMap(); 
    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 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 set = map.keySet(); 
    Iterator 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>"); 
        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

二.哈夫曼解压 

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

代码如下：

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 code_Map = new HashMap(); 
 
  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 list = new ArrayList(); 
//     while(-1 != readCode){ 
//       String str = this.changeIntToBinaryString(readCode); 
//       for(int i=0; i set = code_Map.keySet(); 
    Iterator 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; 
  } 
}

以上就是怎么利用java语言实现一个哈夫曼压缩功能，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注创新互联行业资讯频道。


网站题目：怎么利用java语言实现一个哈夫曼压缩功能
标题URL：http://cdkjz.cn/article/pccjdh.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
绵阳梓潼网站建设软文推广成都标牌标识牌制作公司温江网站建设四川成都网站建设背发光字成都婚庆策划微信开发成都广告制作网站营销

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图