自己手动实现的一个java算法的压缩软件，算法是根据赫夫曼树实现的，赫夫曼编码吧！饿也不知道该怎么说了，这还是刚学java几个月之后写的，格式什么的现在看都不敢看、、、，我写的这个只能压缩跟解压一些小的东西，BUG太多了，效率是硬伤，都还没解决的，特别是效率、、、以后再研究研究，有兴趣的朋友们可以看下，源代码在下面，有源代码有真相、、、、、、
下面的代码只是压缩算法的代码，由于文件大小的原因，解压算法放在附件里面了、、、http://bbs.itheima.com/forum.php?mod=attachment&aid=MjY0MzB8NGQwNDJjMTUyZmVlMTkzYjczNTMxNzZlZmVmMDkwMzF8MTczMTc4MTQzOQ%3D%3D&request=yes&_f=.zip
饿了，吃饭去、、、大神们给点建议，效率是硬伤啊！
import java.io.*;
public class Compression {
public static void main(String[] args) {
long startTime = System.currentTimeMillis(); // 获取开始时间
comp(); //压缩
long middleTime = System.currentTimeMillis(); // 获取中间时间
deComp(); //解压
long endTime = System.currentTimeMillis(); // 获取结束时间
p("");
p("压缩时间： " + (middleTime - startTime) + "ms");
p("解压时间： " + (endTime - middleTime) + "ms");
p("程序运行时间： " + (endTime - startTime) + "ms");
}
public static void comp() {
p("压缩文件开始、、、、、、");
File fin = null, fout = null;
int[] a = new int[255 + 1]; // 统计源数据中出现的次数，以此编码
int fileLength = 0;
int[] source; // 从文件读取的源数据
char[] cin; // 从文件读取的数据提取出不重复的数据
int countIn = 0;
// 读取文件
try {
fin = new File("F:\\Language\\Java\\Practice\\PracticeCompression\\yting10.txt");
FileInputStream in = new FileInputStream(fin);
fileLength = (int) fin.length();
source = new int[fileLength];
int tempSrc, lenTemp = 0;
while ((tempSrc = in.read()) != -1) {
source[lenTemp++] = tempSrc;
}
for (int i = 0; i < source.length; i++) {
a[source[i]]++;
}
// 统计a中不重复的有多少
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
countIn++;
}
}
// 将a中不重复的复制到cin中去
cin = new char[countIn];
for (int i = 0, k = 0; i < a.length; i++) {
if (a[i] != 0) {
cin[k++] = (char) i;
}
}
// ////////////构造赫夫曼树huff
// if(n<=1) return ;
int i, j1, m, n;
n = countIn;
m = 2 * n - 1;
HuffmanTree[] huff = new HuffmanTree[m + 1];
// 将1~m号单元中的双亲，左孩子，右孩子的下标都初始化为0
for (i = 1; i <= m; i++) {
huff[i] = new HuffmanTree();
huff[i].parent = 0;
huff[i].lchild = 0;
huff[i].rchild = 0;
}
// 输入
// 输入前n个单元中叶子结点的权值
// 结点的权值;
j1 = 0;
for (i = 1; i <= n; i++) {
huff[i].weight = a[cin[j1]];
j1++;
}
// 初始化工作结束，下面开始创建赫夫曼树
int s1, s2, t, min1 = -1, min2 = -1, j;
for (i = n + 1; i <= m; i++) {
// 在huff[j] (1<=j<=i-1)中选择两个双亲域为0且权值最小的结点
// 并返回他们在huff中的序号s1和s2
// //////////////////////////////////////////////////////////////////////////////////////////////////////////
// Select(huff,i-1,s1,s2);
min1 = 0;
min2 = -1;
// 为min1赋初值
for (j = 1; j <= i - 1; j++) {
if (huff[j].parent == 0) {
min1 = j;
break;
}
}
// 找出s1
for (j = 1; j <= i - 1; j++) {
if (huff[j].parent == 0) {
if (huff[min1].weight > huff[j].weight) {
min1 = j;
}
}
}
// 为min2赋初值
for (j = 1; j <= i - 1; j++) {
if (huff[j].parent == 0 && j != min1) {
min2 = j;
break;
}
}
// 找出s2
for (j = 1; j <= i - 1; j++) {
if (huff[j].parent == 0 && j != min1) {
if (huff[min2].weight > huff[j].weight) {
min2 = j;
}
}
}
s1 = min1;
s2 = min2;
// //////////////////////////////////////////////////////////////////////////////////////////////////////////
// 得到新结点i，从森林中删除s1,s2,将s1和s2的双亲域由0改为i
huff[s1].parent = i;
huff[s2].parent = i;
// s1,s2分别作为i的左右孩子
if (s1 > s2) {
t = s1;
s1 = s2;
s2 = t;
}
huff[i].lchild = s1;
huff[i].rchild = s2;
// i的权值为左右孩子权值之和
huff[i].weight = huff[s1].weight + huff[s2].weight;
}
// ///////////////////////////////////////////////////////////////////////////////////////////////////////////
char[][] HuffmanCode;
// 从叶子到根逆向求每个字符的赫夫曼编码。存储在编码表HuffmanCode中
char[] cd;
int itemp, start, c, ftemp;
HuffmanCode = new char[n + 1][]; //分配n+1个字符编码的空间
cd = new char[n - 1]; //分配临时存放编码的动态数组空间
for (itemp = 1; itemp <= n; itemp++) { // 逐个字符求赫夫曼编码
start = n - 1; // start开始指向最后，即编码结束符位置
c = itemp;
ftemp = huff[itemp].parent; // f指向结点c的双亲
while (ftemp != 0) { // 从叶子结点开始向上回溯，直到根结点
--start; // 回溯一次start向前指一个位置
if (huff[ftemp].lchild == c)
cd[start] = '0'; // 结点c是f的左孩子，则生成代码0
else
cd[start] = '1'; // 结点c是f的右孩子，则生成代码1
c = ftemp; // 继续向上回溯
ftemp = huff[ftemp].parent;
} // 求出第i个字符的编码
HuffmanCode[itemp] = new char[n - start - 1]; //为第i个字符编码分配空间
//将求得的编码从临时空间cd复制到HC的当前行中
for (int k1 = 0, k2 = 0; k1 < cd.length; k1++) {
if (cd[k1] == '0' || cd[k1] == '1') {
HuffmanCode[itemp][k2] = cd[k1];
k2++;
}
}
cd = new char[n - 1]; // 分配新空间
}
// //////////////////////////////////////////////////////////////////////////////////////////////////////////
char[] huffmanCodeCopy;
int lenHuff = 0;
// 求出lenhuff
for (int it = 0, k; it < source.length; it++) {
k = 0;
for (int jt = 0; jt < cin.length; jt++) {
if (source[it] == cin[jt]) {
while (HuffmanCode[jt + 1].length > k) {
k++;
lenHuff++;
}
}
}
}
// 为huffmanCodeCopy初始化
huffmanCodeCopy = new char[lenHuff];
lenHuff = 0;
for (int it = 0, k; it < source.length; it++) {
k = 0;
for (int jt = 0; jt < cin.length; jt++) {
if (source[it] == cin[jt]) {
while (HuffmanCode[jt + 1].length > k) {
huffmanCodeCopy[lenHuff] = HuffmanCode[jt + 1][k];
k++;
lenHuff++;
}
}
}
}
// 缩位
int tf;
tf = huffmanCodeCopy.length / 8 + 1;
char[] finallyCode = new char[tf];
char[] temp = new char[8];
String strTem;
int tp, fLen = 0;
int it, ij;
for (it = 0, ij = 0; it < huffmanCodeCopy.length; it++) {
if (ij < 8) {
if (it < huffmanCodeCopy.length) {
temp[ij] = huffmanCodeCopy[it];
ij++;
}
} else if (ij >= 8) {
strTem = new String(temp);
tp = Integer.parseInt(strTem, 2);
ij = 0;
temp = new char[8];
finallyCode[fLen++] = (char) tp;
it--;
}
}
for (int item = 0; item < temp.length; item++) {
pw(temp[item] + " ");
}
if ((temp[0] == '0' || temp[0] == '1') && (temp[7] !='0' && temp[7] !='1')) {
p("aaaaaaaa");
for (int item = 0; item < 8; item++) {
if (temp[item] != '0' && temp[item] != '1') {
temp[item] = '1';
}
}
strTem = new String(temp);
tp = Integer.parseInt(strTem, 2);
finallyCode[fLen++] = (char) tp;
}
// //////////////////////////////////////////////////////////////////////////////////////////////////////////
// 将压缩好的东西存到文件中去前的准备
// 先转换HuffmanCode
fout = new File("F:\\Language\\Java\\Practice\\PracticeCompression\\yting_compression.txt");
FileOutputStream fo = new FileOutputStream(fout);
DataOutputStream dp = new DataOutputStream(fo);
int huffmanCompLen = 0;
int[] huffmanComp = new int[HuffmanCode.length - 1];
String strTemp, flags = "1";
StringBuffer strBuf;
for (int item = 1; item < HuffmanCode.length; item++) {
strTemp = new String(HuffmanCode[item]);
strBuf = new StringBuffer(strTemp);
strBuf.insert(0, '1');
strTemp = strBuf.toString();
huffmanComp[huffmanCompLen] = (int) Integer.parseInt(strTemp, 2);
huffmanCompLen++;
}
// 开始压缩到文件中去
/*
* 编码方式 cinLen huffmanCompLen cin huffmanComp finallyCode
*/
// 写入cinLen
dp.writeInt(cin.length);
// 写入huffmanCompLen
dp.writeInt(huffmanComp.length);
// cin
// 写入huffmanC，也就是cin，但是cin是char[]的
for (int item = 0; item < cin.length; item++) {
dp.writeChar(cin[item]);
}
// 写入huffmanComp
for (int item = 0; item < huffmanComp.length; item++) {
dp.writeInt(huffmanComp[item]);
}
// 写入finallyCode
for (int item = 0; item < finallyCode.length; item++) {
dp.write(finallyCode[item]);
}
dp.close();
p("压缩文件结束、、、、、、");
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
public static void pw(Object o) {
System.out.print(o);
}
public static void p(Object o) {
System.out.println(o);
}
}
class HuffmanTree {
int weight;
int parent, lchild, rchild;
}
|
收藏
淘帖
踩
