哈夫曼压缩的步骤

人一旦闲下来就很恐怖的，已经好久都没写博客了，热情也不如先前的。忙碌的时候，每做完一件事，我就一种自豪的感觉。我不想让自己活得很空虚。所以还得写点东西。
对于哈夫曼树，我们的解释是每次取出一组数组里的最小两个数来建树，把这两者的和放到
原先的数组。作为新的元素。重复以上操作，来建树。
以下的步骤只是我的理解
1.统计文件中字节出现的次数，并把次数作为结点来键哈夫曼树。
  如何来建树，这里出现了问题。我们实际是通过优先队列来进行建树的。这个队列里的数，
  按从小到大进行的排序，仿佛这个队列就是为哈夫曼树而生。
  统计次数的方法。
  public int[] FileRead(String path){
    //创建文件输入流
    try {
     FileInputStream  fils = new FileInputStream(path);
//将文件输入流包装成缓冲流
      BufferedInputStream fos=new BufferedInputStream(fils);
//读入字节
int a=fos.read();
while(a!=-1){
array[a]++;
//读取下一个字节
    a=fos.read();
}
} catch (Exception ef) {
ef.printStackTrace();
}
    return array;
     }
   建树的过程
    /** 
     * 通过优先队列来构造哈夫曼树,返回根结点
      */
    public TreeNode2 CreatTree(PriorityQueue<TreeNode2> list){
    while(list.size()>1){
    //取出两个构造
    TreeNode2 node1=list.poll();
    TreeNode2 node2=list.poll();
   
    //创建父结点
    TreeNode2 nodeparent=new TreeNode2();
        nodeparent.sum=node1.sum+node2.sum;
   
    list.add(nodeparent);
   
    //建立关系
    nodeparent.lchild=node1;
    node1.parent=nodeparent;
   
    nodeparent.rchild=node2;
    node2.parent=nodeparent;
   
    //给结点附哈夫曼编码
    node1.flag1=0;
    node2.flag1=1;
    }
    TreeNode2 lastnode=list.poll();
        return lastnode;
    }
  这里传入的参数优先队列，因为系统的优先队列不能排序根结点，所以需要自己重写其中
  的比较方法。
     /**
      * 将读入的数据存入优先队列
      */
     public PriorityQueue<TreeNode2> arraylist(int array[]){
    //根据指定的比较器创建一个优先队列
    PriorityQueue<TreeNode2> list = new PriorityQueue<TreeNode2>(11,new MyComparator());
    //将一个个结点对象存入到优先队列中
    for(int i=0;i<array.length;i++){
    if(array[i]!=0){
    TreeNode2 treenode=new TreeNode2();
    treenode.obj=i;
    treenode.sum=array[i];
    list.add(treenode);
    }
    }
    return list;
     }
     /**
      * 写一个类来是实现迭代器这个接口
      * @author Administrator
      *重写里面的方法compare
      */
    class MyComparator implements Comparator<TreeNode2>{
    public  int compare(TreeNode2 node1,TreeNode2 node2){
    int o1=node1.sum;
    int o2=node2.sum;
    return o1-o2;
    }
     }
2.通过哈夫曼树进行编码
    /**
     *
     * @param str对应一个节点的哈夫曼编码
     * @param root传入的根结点
     * @param code哈夫曼编码字符串数组
     */
    public void GetoneCode(String str,TreeNode2 root,String code[]){
    //首先判断节点是否为空
    if(root!=null){
    if(root.flag1!=null){
    str=str+root.flag1;
    if(root.lchild==null&&root.rchild==null){
    code[root.obj]=str;
    System.out.println(root.obj+"该字节"+"哈夫曼编码为"+str);
    //将找到的数据依次输入队列中
    Data data=new Data();
    data.str=str;
    data.obj=root.obj;
    list.add(data);
    }
    }
    //递归遍历
    TreeNode2 left=root.lchild;
    GetoneCode(str,left,code);
   
    TreeNode2 right=root.rchild;
    GetoneCode(str,right,code);
    }
    }
3.利用哈夫曼编码对应的字节来进行读文件，然后把01字符串每8个字符串写成一个字节。
/**
     * 文件压缩 并输出
     * 将得到的字符串数组，取出字符串每8位变成一个字节
     */
public void OutPut(String path,String oldpath){
//记录文件中的01字符串的个数
int num=0;
//记录文件补0的情况
int addzero=0;
try{
//创建输入流对象
FileInputStream fis=new FileInputStream(oldpath);
//创建输入缓冲流
BufferedInputStream dis=new BufferedInputStream(fis);
//创建输出流对象
FileOutputStream fos=new FileOutputStream(path);
//创建输出缓冲流
BufferedOutputStream dos=new BufferedOutputStream(fos);
   /**
    * 写头文件,文件内容最后补零的情况
    */
     dos.write(list.size());
     System.out.println("队列的长度"+list.size());
     for(int i=0;i<list.size();i++){
    Data data=list.get(i);
    dos.write(data.obj);
    byte by[]=data.str.getBytes();
    dos.write(by.length);
    dos.write(by);
    num+=array[data.obj]*data.str.length();
    }
         System.out.println("该数目为"+num);
         addzero=8-num%8;//求出添零的个数
         dos.write(addzero);
        
         String writeString="";
         byte[] by=new byte[(num+addzero)/8];//将变成的字节存在创建的byte数组
         System.out.println("数组的长度为"+by.length);
         int count=0;
         while(dis.available()>0){
        int i=dis.read();
        //寻找与之匹配的编码
        for(int j=0;j<list.size();j++){
        boolean bool=false;//标记是否找到
        if(list.get(j).obj==i){
        int x=0;
        while(true){
        writeString+=list.get(j).str.charAt(x)+"";
        x++;
        //如果字符串长度已经达到8位
        if(writeString.length()==8){
        byte wri=this.change(writeString);
        by[count]=wri;//将转化的字节保存到数组中
        count++;
        writeString="";//将字符串重新初始化
        }
        //如果字符串长度不足8位但是已经编码完全加入字符串中
        if(x==list.get(j).str.length()){
        bool=true;
        break;//跳出循环
            }
        }
        }
        //如果找到，则跳出循环
        if(bool==true){
        break;
        }
          }
         }
         System.out.println("此时的count为"+count);
         //如果还有剩余的字符在字符串中，则需要补0
         if(writeString.length()>0){
        int n=8-writeString.length();
        for(int i=0;i<n;i++){
        writeString+="0";
        }
        byte wri=this.change(writeString);//将8位转换为一个byte
        by[count]=wri;//写入byte数组
         }
         //此处的写入的范围为多少
//         dos.write(by.length);//写入byte数组的大小
         dos.write(by);//写入byte数组
         System.out.println("byte的数组长度为"+by.length);
        
    dis.close();//关闭输入流
    dos.close();//强制输出
    fos.close();//关闭输出流
}catch(Exception e){
e.printStackTrace();
}
   
    }
4.文件的解压
/**
* 将压缩的文件进行解压
*
*/
public void read(String path,String Newpath){
//创建存放数据的队列
ArrayList<Data> list1=new ArrayList<Data>();
try{
//创建输入流
FileInputStream fis=new FileInputStream(path);
//创建输入缓冲流
BufferedInputStream dis=new BufferedInputStream(fis);
//创建输出流
FileOutputStream fos=new FileOutputStream(Newpath);
//创建输出缓冲流
BufferedOutputStream dos=new BufferedOutputStream(fos);
/**
* 读头文件
*/
int size=dis.read();
System.out.println("队列的长度为"+size);
for(int i=0;i<size;i++){
Data data=new Data();
data.obj=dis.read();
int len=dis.read();
        byte[] by=new byte[len];
        dis.read(by);
        data.str=new String(by);
        list1.add(data);
}
int addzero=dis.read();//读出补0的情况
// int count=dis.read();//读出byte数组大小
int count=dis.available();
byte[] b=new byte[count];
System.out.println("补零数为"+addzero+"byte数组的大小为"+count);
dis.read(b);//读出byte数组
String str=new String("");
for(int i=0;i<b.length;i++){
int n=(int)b[i];
if(n<0){
n+=256;
}
str=str+this.changeInt(n);
}
//减去01字符串中末尾多加上的0
str=str.substring(0, str.length()-addzero);
boolean bool=true;
while(bool){
bool=false;
//寻找与之对应的字符
for(int i=0;i<list1.size();i++){
if(str.startsWith(list1.get(i).str)){
dos.write((int)list1.get(i).obj);
str=str.substring(list1.get(i).str.length());

bool=true;
break;
  }
}
}
//关闭输入输出流
fis.close();
dos.flush();
fos.close();
}catch(Exception e){
e.printStackTrace();
}
}
}
看上去代码的确是很长，其中有些语句，没有深刻理解的话，确实难以弄懂。当然这个压缩也存在居多问题，比如压缩的文件大小太大，否则会卡机。可能是这个程序特别耗cpu导致的。