哈夫曼压缩总结

哈弗曼压缩
哈弗曼压缩过程梳理
步骤
读入文件。统计字节出现的次数（可以得到数组里面的次数还有该对应的下标）
将要读入的文件一个字节一个字节的读入，然后创建一个数组，数组的下标与该字符的ASCII码值相对应，当出现一次该字符的时候，拥有该下标值的数组加一。
while (fis.available() > 0) {// 当文件还有字节没被读取，继续循环
int i = fis.read();
// 每次读取的都是一个字节，正好是一个ascii码值，也正好是countByte下标
countByte[i]++;// 次数加一
对该数组进行排序。（返回的是一个树的根节点，也就是队列只剩下一个时的节点）
在优先队列（优先队列里面储存的是节点）里面添加该数组，并进行排序。然后建哈弗曼树。每次都从队列中选两个最小值的节点，小的作为右节点，大的作为左节点，新建一个父节点，对他们进行设置后，把该父节点放进队列里面重新进行排序。重复此操作，当队列只剩一个时，该树建立完成。
// 实例化一个优先队列
PriorityQueue<HfmNode> nodeQueue = new PriorityQueue<HfmNode>();
for (int j = 0; j < countByte.length; j++) {
// 循环数组，让每个出现的ascii码值全都遍历到，长度是256
if (countByte[j] != 0) {
// 当有该ascii码值出现的时候，把带有ascii码值和出现次数的节点加入到队列中
HfmNode node = new HfmNode(j, countByte[j]);
// 新建一个节点带有ascii码值出现的次数和ascii码
nodeQueue.add(node);// 把该节点加入到优先队列中去
}
}
　HfmNode min1 = nodeQueue.poll();
HfmNode min2 = nodeQueue.poll();
// 新建一个节点，作为min1和min2的父节点，他的出现次数是两个相加
HfmNode result = new HfmNode(0, min1.gettimes() + min2.gettimes());
然后返回root，这棵哈弗曼树就建好了。
对每个哈弗曼树的叶子节点设置对应的哈弗曼编码
遍历每个叶子节点，然后向左走就是0；往右子树走的话就在字符串上加1。然后就可以把叶子节点的所对应的01串与数组下标进行匹配。也相当于AscII值所对应的字符与01串相对应。
public void getMB(HfmNode hfm, String str) {
if ((hfm.getLchild() == null) && (hfm.getRchild() == null)) {
// 当该节点是叶子节点的时候
Code code = new Code();
code.setNode(str);// 设置节点的01字符串
code.setN(str.length());// 设置01字符串的长度

SaveCode[hfm.getData()] = code;
　　/ /每个叶节点的ascii码所对应的编码（01字符串）
}
if (hfm.getLchild() != null) {
getMB(hfm.getLchild(), str + "0");// 往左边走就是写0
}
if (hfm.getRchild() != null) {
getMB(hfm.getRchild(), str + "1");// 往右边走写1
}
}
写文件：1.头文件
写每个编码的长度（对应有几个字节）
写每个编码与之所对应的字符（由于编码可能不足八位或者超过八位，不足八位的则补0补到八位，超过八位则补0补到八的整数倍位）

/**
* 该方法是字节补0，每个ascii码值对应的哈弗曼编码长度可能不足八位，或者超过八位
* 所以要给长度补到8的倍数
* zijienode【】保存的是每个ascii码补0 后的01串字符 zijiesize【】保存的是每个ascii码* 补到八位后的长度
*/
public void zijiebu0() {
for (int i = 0; i < SaveCode.length; i++) {
if (SaveCode[i] != null) {
// 当savecode里面储存的不为空，里面存的是code，code存的是哈弗曼编码和长度
zijienode[i] = SaveCode[i].getNode();
int bytesize = 8 - SaveCode[i].getN() % 8;// 求需补多少0
if(bytesize==8){
bytesize=0;
}
int size = bytesize;
if (bytesize > 0) {// 当余数大于0
while (bytesize > 0) {
// SaveCode[i].setNode(SaveCode[i].getNode()+"0");//给哈弗曼编码补上一个0
zijienode[i] = zijienode[i] + "0";// 给哈弗曼编码补上一个0
bytesize--;// 循环次数减一
}
}
zijiesize[i] = (SaveCode[i].getN() + size) / 8;
// 把取得的ascii码值的哈弗曼编码设置字节长度
System.out.println("字符" + (char) i + "的哈弗曼编码为：" + zijienode[i]
+ "他的长度为" + zijiesize[i]);
}
}
}
现在已经得到了字节补0后的哈弗曼编码和字节的长度，这样就可以把码表给写进去
// 先把码表都给读入进去
for (int i = 0; i < countByte.length; i++) {
if (countByte[i] != 0) {// 当又出现ascii码值的下标的数组时，读入
try {
fos.write(i);// 先把每个ascii码给写进去
fos.write(zijiesize[i]);
//把每个ascii码值对应的补0后的哈弗曼编码的长度也写进去
int bu0=zijiesize[i] * 8 - SaveCode[i].getN();
fos.write(zijiesize[i] * 8 - SaveCode[i].getN());// 再把每个ascii码值所补0的个数写进去
System.out.println("========哈弗曼编码补零个数："+bu0 );
// 因为每次读入的是int型，读八位，所以如果大于八位的那就循环每次读八位
int k = 8;
int z = zijiesize[i];
while (z > 0) {// 当哈弗曼编码的长度大于8，则先读前八位
String ss = "";
for (int j = k - 8; j < k; j++) {// 每次都循环八次
ss += zijienode[i].charAt(j);// 把要读入的ss先写好八位
}
k += 8;// 继续加上八位
fos.write(changeString(ss));
System.out.println("=======哈弗曼编码为："+ss );
z -= 1;// 每次读完八位后，就在哈弗曼长度-1
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
书写好码表之后，就开始书写文件补0的个数
书写文件内容
把文件内容一个字节一个字节的读入到指定的文件位置，因为文件内容此时是每个字符对应的哈弗曼编码，加起来位数可能不足八位。如果不足八位，则在后面补0补到八位。
FileInputStream fis = new FileInputStream(newpath);// 实例话一个输入流，把文件内容读写进来
String str = "";
try {
while (fis.available() > 0) {// 当文件还有字节没有读取的时候则执行循环
int i = fis.read();// 读取每一个字节
str += SaveCode[i].getNode();// 把哈弗曼编码加上去
while (str.length() > {
// 当加起来的哈弗曼编码长度大于八，则执行循环，若小于或等于8，则加上后来的哈弗曼//编码
String str1 = "";// 要输入的哈弗曼编码
for (int j = 0; j < 8; j++) {// 每次写进去一个字节长度的哈弗曼编码
str1 += str.charAt(j);
}
fos.write(changeString(str1));
// System.out.println("输入内容啦输入内容啦！！！");
for (int j = 8; j < str.length(); j++) {
　　// 然后把前八位的哈弗曼编码去掉
str = "" + str.charAt(j);
}
}
}
// 当文件没有文件内容可读入的时候且这时候还有哈弗曼编码没有写进去时，判断是否是一个字节的长度或者不是一个字节的长度，不够的则补0后写入
if (str.length() == {
fos.write(changeString(str));
}
if (str.length() < {
int c = 8 - str.length();
for (int d = 0; d < c; d++) {
str += "0";
}
fos.write(changeString(str));
}
解压缩和压缩正好是逆过程
思路：
先读取码表长度，得到码表的长度后，在循环读取码表的ascii码值，ascii码值对应的哈弗曼编码长度，补零情况，然后读取补0后的哈弗曼编码，然后把哈弗曼编码去掉补的0，把哈弗曼与ascii码值相对应起来，用数组存。
读取码表与文件内容补零情况
　　for (int a = 0; a < mabiaosize; a++) {
int i = fis.read();// 先读取ascii码值
System.out.println("ascii码值为：" + (char) i);
int zijiesize = fis.read();// 获得字节长度的大小
System.out.println("字节长度为：" + zijiesize);
int bu0 = fis.read();// 读取补0的情况
System.out.println("字节补零个数" + bu0);
String str = "";
for (int j = 0; j < zijiesize; j++) {// 开始循环取得哈弗曼补0后的编码
str += int_to_String(fis.read());// 把字符串给写进来
}
// 然后开始根据补0的个数来去掉0
String hfmcode1 = "";
for (int j = 0; j < zijiesize * 8 - bu0; j++) {
hfmcode1 += str.charAt(j);
}
hfmcode[i] = hfmcode1;// 根据取得的字符串和ascii编码进行匹配
System.out.println((char) i + "字符的哈弗曼编码是：" + hfmcode[i]);
}
int neirongbu0 = fis.read();// 读取文件内容补零的情况
System.out.println("字节补零个数 " + neirongbu0);
然后读取完码表后，开始读取文件内容
　　String file_01="";
while(fis.available()>1){
int count_writed_01=0;
//读取的01字符串
file_01+=int_to_String(fis.read());
//System.out.println("源文件的01串是："+file_01);
int k=0;
int count=1;
while(count<=file_01.length()){
//定义哈夫曼编码变量
String HFMcode="";
for(int i=k;i<count;i++){
HFMcode+=file_01.charAt(i);
}
for(int i=0;i<hfmcode.length;i++){
if(hfmcode[i]!=null&&hfmcode[i].equals(HFMcode)){
//System.out.println("哈夫曼编码是"+HFMcode);
count_writed_01+=HFMcode.length();
//System.out.println("写入了"+count_writed_01+"个");
k=count;
fos.write(i);
//System.out.println("内容写入了"+i);
}
}
count++;
}
//System.out.println("写入后的file_01是"+file_01);
String file_01x="";
for(int i=count_writed_01;i<file_01.length();i++){
file_01x+=file_01.charAt(i);
}
file_01=file_01x;
//System.out.println("清空后的file_01是"+file_01);
}
　　//读取最后一个字符串
String str_end=file_01+int_to_String(fis.read());
//System.out.println("最后一个字符串是"+str_end);
int file__0=yasuo.getFile_0();//获取问价末尾补0个数
//把最后读取的字符串补的0去掉
String str="";
for(int i=0;i<str_end.length()-file__0;i++){
str+=str_end.charAt(i);
}
str_end=str;
//System.out.println("把0删掉后变成："+str_end);
int count=1;
int k=0;
while(count<=str_end.length()){
str="";
for(int i=k;i<count;i++){
str+=str_end.charAt(i);
}
//System.out.println("str是："+str);
for(int i=0;i<array.length;i++){
if(array[i]!=null&&array[i].equals(str)){
//System.out.println("&&&&&&&&&&&");
fos.write(i);
k=count;
}
}
count++;
}
如此一来，哈夫曼压缩就完成了！！