利用哈夫曼二叉树实现文件的压缩

首先，我们需要了解一下我们平时的文件是如何保存的。不难理解；不管是什么类型的文件都是以字节的形式存储在我们的各种储存器中的，以二进制的方式将数据储存起来。而我们需要找到一种能够占用内存更少的方式将我们的数据储存。下面我将以压缩字符串为例仔细探讨如何利用哈夫曼二叉树(最优二叉树)压缩文件。

首先需要一个字符串，String str=“QQAFDGGFDAAGFGFDHGFHG”;然后我们需要对每一个字符进行哈夫曼编码，即找到每一个出现的字符找个属于它的哈夫曼编码，当然这不是随便乱给的。下面来看一下如何给这个字符串编码。

①统计字符串中每个字符出现的次数，例中：A:3  D:3  F:5 G:6 H:2 Q:2

 关键代码:

       

 int []temp=new int[256];
         public void  statisticsString(String str){  
		    byte b[]=str.getBytes();
		       for(int i=0;i<b.length;i++){
		    		  temp[b[i]+128]++; 
		      }                      
	  }

　　

②将每一个字符出现的次数作为该字符的一个权值，A的权值为3、D为3、F为5、G为6、H为2、Q为2.然后按权值大小将字符排队，H(2)、Q(2)、A(3)、D(3)、F(5)、G(6)

③最最关键的一步就是生成树,应该怎么生成一颗哈夫曼二叉树呢？1、首先我们找出排好顺序的字符，每一个字符作为一个子结点，(这时候我们需要为我们的结点写一个结点类(文章末尾有我自己写的Node类)了，结点类中需要有两个指针,和两个数据)。每一个字符生成一个结点对象，保存两个数据，一个是字符，一个是字符的权值，将所有的结点保存在一个链表中。2、取出权值最小的两个字符作为叶结点，生成一个根结点，根结点也保存两个数据，一个是生成它的两个叶结点的字符(两个字符相连接在一起保存)，一个是生成它的两个叶结点的权值和3、将新的结点加入链表中，删除两个权值最小的结点，然后按照权值大小重新排序。4、然后重复2、3步直到剩下一个结点为止。由下图所示：

                             

      

  关键代码:

         

public void spanning(){
             list=new ArrayList<Node>();
             int count=0;
              for(int i=0;i<temp.length;i++){
                  if(temp[i]!=0){
                      Node<String> node=new   Node<String>(""+(i-128),temp[i]);
                      list.add(node);
                      count++;
                  }
              }
                int data[]=new int[count];
                for(int i=0;i<count;i++){
                   data[i]=(int) (list.get(i).data1);
                }
                Arrays.sort(data);
               
                for(int i=0;i<data.length;i++){
                    for(int j=0;j<count;j++){
                       if(list.get(j).data1==data[i]){
                           list.add(list.get(j));
                           list.remove(j);
                           count--;
                           break;
                      }
                    }
                }   
             while(list.size()>1){
                n=new Node((String)list.get(0).data+list.get(1).data,list.get(0).data1+list.get(1).data1,list.get(0),list.get(1));
                list.remove(0);
                list.remove(0);
               for(int i=0;i<=list.size();i++){
                    if(list.size()==0){list.add(n);break;}
                    else if(i==list.size()){list.add(n);break;}
                    else if(n.data1<=list.get(i).data1){
                       list.add(i, n);
                       break;
                   }
               }
              }         
      }

④然后给生成的树编码，左零右一。

 关键代码:

           

map=new HashMap<String, String>();
       public void  ergodic(Node node,String code){
              if(node==null)return ;
              if(node.next!=null){
                  ergodic(node.next,code+"1");
              }
              if(node.next2!=null){
                  ergodic(node.next2,code+"0");
              }
              if(node.next==null&&node.next2==null){
                    map.put(""+node.data,code);
              }
      }

⑤按着路径找到每个叶结点的编码，H:010 Q:011 A:100 D:101 F:00 G:11

⑥将编码代替字符串。例中：“QQAFDGGFDAAGFGFDHGFHG”替换成 ：

         0110111000010111110010110010011001100101010110001011然后我们就将我们的字符串替换成了二进制数串。

关键代码:

           

 public String read(String str){
       String code="";
       byte[] b=str.getBytes();
       for(int i=0;i<b.length;i++){         
             code+=map.get(""+b[i]);
             
    }    
        return code;
    }

⑦将我们的二进制数串每八个换成一个十进制数字，最后不足八个就补0，例中的就替换成：

                                             217-200-36-217-18-229-192

关键代码:

         

public String compressFile(String path,String fileName,String code){
          int coding;
          String sa="";
          byte co[]=new byte[code.length()/8+1];
          for(int i=0,j=0;i<code.length()-code.length()%8;i+=8,j++){
              String s=code.substring(i,i+8);
              coding=Integer.parseInt(s, 2);
              co[j]=(byte)coding;
              sa+=""+coding+"-";
           }
          if(code.length()%8!=0){
              String s=code.substring(code.length()-code.length()%8,code.length());
                for(int i=0;i<8-code.length()%8;i++)s+="0";         
                coding=Integer.parseInt(s, 2);
                co[code.length()/8]=(byte)coding;
                sa+=""+coding;
          }     
         System.out.println(sa);
         return sa;
    }

⑧然后将我们得到的十进制数保存成文件，这样我们就实现了我们的字符串的压缩，而如何压缩文件呢？同样道理，一个文件是有一个一个字节组成的，我们同样可以统计每个字符出现的次数，我们只需要按照上面的流程走一遍就可以了。

public class Node<E> {
    E data;
    int data1;
    Node<E> next;
    Node<E> next2;
    MyLinkList<E> mylist;
    public Node(){    
    }
    
    public Node(E e1,int e,Node<E> next,Node<E> next2){
        data=e1;
        data1=e;
        this.next=next;
        this.next2=next2;
    }
    public Node(E e,int e1){
        data=e;
        data1=e1;
    }
    public Node(E e){
        data=e;
    }
    public Node(E e,Node<E> next){
        data=e;2016-08-13
        this.next=next;
    }
}