文件压缩（一）——Huffman树的构建
在前一篇文章中，我们已经构建了一棵Huffman树了，今天我们将利用这棵Huffman树来实现英文字符串的压缩和解压缩。
一、字符串在JAVA中的储存
String字符串相当于一个char型数组，和C++不同的是，JAVA采用的是unicode编码，每个char型数据占2个字节，只不过对于ASCII码中的字符，它的第一个字节位全0。浪费了一些空间。而存汉字的时候就需要用到两个字节。这里我们为了简便起见，只对ASCII码中的字符进行处理，也就是平常生活中的纯英文文件。因此我们在压缩的过程中只需关注字符的第二个字节位即可。
二、压缩的过程
1.获取字符编码
2.压缩过程
3.解压缩的过程
三、具体的代码（建Huffman树部分的代码见前一篇博客）
//构造Huffman树 import java.util.ArrayDeque; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Queue; public class Huffman { public static void main(String[] args) { //读取相应的字符串 String str = "aadefefbcffbaeadde";//待处理的文本 HashMap<Character,Integer> Charmap = new HashMap<Character,Integer>(); //将字符串解析为字符数组 char[] arr = str.toCharArray(); for (char ch : arr) { //如果找到了相应的字符，则权值加1，否则就把这个字符加到map中 if (Charmap.containsKey(ch)) { Integer old = Charmap.get(ch); Charmap.put(ch, old + 1); } else { Charmap.put(ch,1); } } System.out.println(Charmap); //把map中的储存的信息传递给nodes数组，以便建立Huffman树 List<Node> nodes=new ArrayList<Node>(); for(Character key:Charmap.keySet()) { Integer value= Charmap.get(key); nodes.add(new Node(key,value)); } Node root=Huffman.creatTree(nodes);//调用建树函数 //用一个数组来存储所有的节点信息 List<Node> list=new ArrayList<Node>(); list=Huffman.breadthFirst(root); //这里只能用泛型的类型数据，比如int只能用Integer,这里的char只能用Character来代替 //储存编码的数组 HashMap<Character,String> map=new HashMap<Character,String>(); HashMap<String,Character> DecompressMap=new HashMap<String,Character>(); for(int i=0;i<list.size();i++) { //判断字符是否存在，若存在则将其加入到Hashmap中 if(list.get(i).data!=null) { //这里的data本来不也是char型的吗？？？ map.put((Character) list.get(i).data, list.get(i).code); DecompressMap.put( list.get(i).code, (Character) list.get(i).data); } } System.out.println(map);//字符串压缩 System.out.println(DecompressMap); Compress com=new Compress(str,map,DecompressMap); com.CompressWay();//调用压缩方法 com.DecompressWay();//调用解压缩方法 //压缩前的文本 System.out.println("压缩前的文本:"+com.text); System.out.println("压缩后的文本:"+com.CompressText); System.out.println("解压缩后的文本:"+com.DecompressText); } } //构架一个压缩文件类 import java.util.HashMap; public class Compress { private static final String Binarytemp = null; private static final String String = null; public String text;//待压缩的字符串 public HashMap<Character,String> map=new HashMap<Character,String>();//每个字符所对应的Huffman编码 public HashMap<String,Character> DecompressMap=new HashMap<String,Character>();//每个字符所对应的Huffman编码 public String CompressText;//压缩后的文件 public int CharacterNumber;//用来保存待压缩文件的字符个数 public String DecompressText="";//解压缩后的文本 //构造函数 public Compress(String text,HashMap<Character,String> map,HashMap<String,Character> DecompressMap) { this.text=text; this.map=map; this.DecompressMap=DecompressMap; } //定义压缩文件的方法 public void CompressWay() { CharacterNumber=text.length(); //遍历待压缩的字符串，找出相应的Huffman编码 String buff="";//保存编码 char[] arr = text.toCharArray(); for (char ch : arr) { buff=buff+map.get(ch); } //将buff转化为8的整数，不足补0 while((buff.length())%8!=0) { buff=buff+"0"; } CompressText=""; char[] buffarray = buff.toCharArray();//把buff转化为字符数组 for(int i=0;i<buff.length();i=i+8) { int characterNumber=0;// //从倒数第二为开始每位都要乘以二 for(int j=i;j<i+7;j++) { //如果是1则加1乘以2 if(buffarray[j]=='1') characterNumber=(characterNumber+1)*2; //如果是0则直接乘以2 else characterNumber=characterNumber*2; } //最低位直接加1 if(buffarray[i+7]=='1') characterNumber=characterNumber+1; CompressText=CompressText+(char)(characterNumber); } } //定义一个解压缩的方法 public void DecompressWay() { //先把字符串转化为字符数组 char[] CompressTextArray=CompressText.toCharArray(); String result="";//保存转化后的二进制数据 for(int i=0;i<CompressText.length();i++) { //利用char型字符已经存在的方法把字符转化为二进制,注意char数据在转化为二进制时不会自动在高位补0 String Binarytemp=Integer.toBinaryString(CompressTextArray[i]); int count=0; while(Binarytemp.length()+count<8) { result=result+"0"; count++; } result+=Binarytemp; } char[] resultArray=result.toCharArray(); int count=0; //当解码的字符跟我们压缩的字符相等时，就退出 String temp=""; for(int i=0;i<result.length();i++) { temp+=resultArray[i]; //如果没有找到相应的编码，就不断往后取字符 while(DecompressMap.get(temp)==null) { //没有找到，则往下走一个位置 i++; temp=temp+resultArray[i]; } //跳出循环时说明已经找到一个字符了 DecompressText=DecompressText+DecompressMap.get(temp); count++;//找到的字符数量加1 //如果字符都找到了，就退出 temp="";//清空temp if(count==CharacterNumber) break; } } }四、反思总结
1.我们在把字符转化为相应的二进制序列时，需要将其进行补位，使其变成8的整数，因为每一个字符都是8个bit位。而在解压缩的时候要把补上的无效的0去掉。这里利用了一个int型数据CharacterNumber来保存压缩的字符个数，在解压缩时一旦解压的字符数量已经达到这个数量，则强制退出解压的循环。
2.在利用char型数据的toBinaryString方法把字符转化为二进制时,需要注意char数据在转化为二进制时不会自动在高位补0，它会默认这些高位0是无效位。因此我们需要手动把前面的这些高位0补上去。
