Ве4ер добрый всем. Я реализую программу на Visual Studio - сжатие файлов по лагоритму Хаффмана. Программу написать было не сложно. Но проблемы оказались при проверке. Когда входной файл относительно(по меркам байт) большой - обходы дерева и построение дерева оказываются процессами скажем прямо не быстрыми. Я завел эту тему ,потому что хо4у ,чтобы программа работала быстрее. Ниже приведен код. Надеюсь на вашу помощь.
| Код |
#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>
using namespace std;
void BuildTree(vector <struct table> TBL);
void AroundTree(struct tree *A);
void ReadFile(FILE *fin1);
void WriteFile();
void DReadFile(FILE *df);
struct tree {
struct tree *left;
struct tree *right;
char Symbol;
int mass;
};
struct table {
string S;
int mass;
struct tree *adress;
};
struct code {
string S;
char ch;
};
vector <struct code> TCD;
vector <struct table> ITBL,WTBL,DTBL;
struct table Temp;
struct code CTemp;
char c,cTemp;
int N=0,K=0,K1=0,i=0,j=0,min1,min2,Ktemp=-1,K1temp=-1,Rej=1;
bool flag;
FILE *fin;
struct tree *Ttemp, *TMain;
string InputS, OutputS, S1, SOUT,TempS1;
long Bits;
FILE *f;
char *pm;
//------------------------------------------
void ReadFile(FILE *fin1){
cout<<"Reading file"<<endl;
long nFileLen = 0, Now = 0;
if (fin1)
{
fseek(fin1, 0, SEEK_END);
nFileLen = ftell(fin1);
fseek(fin1, 0, SEEK_SET);
}
pm = (char *)malloc((nFileLen+1)*sizeof(char));
fread(pm,nFileLen,1,fin1);
pm[nFileLen]=0;
while (Now < nFileLen)
{
c = pm[Now];
InputS.push_back(c);
N = ITBL.size();
flag = 0;
for (int i=0; i<N; i++)
{
if (ITBL[i].S.size() != 0)
if ((ITBL[i].S.at(0) == c))
{
ITBL[i].mass++;
flag = 1;
i = N;
};
}
if (flag == 0)
{
Temp.S.push_back(c);
Temp.mass = 1;
Temp.adress = NULL;
ITBL.push_back(Temp);
Temp.S.erase(Temp.S.begin());
}
Now++;
}
WTBL = ITBL;
free((char *) pm);
cout<<"Reading complete"<<endl;
};
void BuildTree(vector <struct table> TBL){
while (TBL.size() > 1)
{
K=0;
K1=-1;
min1 = TBL[0].mass;
for (int i=0;i<TBL.size();i++)
{
if (TBL[i].mass < min1)
{
min1= TBL[i].mass;
K = i;
}
}
if (K == TBL.size()-1)
{
min2 = TBL[TBL.size()-2].mass;
} else min2 = TBL[TBL.size()-1].mass;
for (int i=TBL.size()-1;i>=0;i--)
{
if ((TBL[i].mass <= min2) && (i != K))
{
min2= TBL[i].mass;
K1 = i;
}
}
// if ((K != KTemp) || (K != K1Temp))
Ttemp = (struct tree *) malloc (sizeof(struct tree));
Ttemp->left = NULL;
Ttemp->right = NULL;
Ttemp->Symbol = 0;
Ttemp->left = (struct tree *) malloc (sizeof(struct tree));
Ttemp->right = (struct tree *) malloc (sizeof(struct tree));
Ttemp->left->Symbol = 0;
Ttemp->right->Symbol = 0;
if (TBL[K].S.size() != 0)
{
c = TBL[K].S.at(0);
Ttemp->left->Symbol = c;
Ttemp->left->left = NULL;
Ttemp->left->right = NULL;
} else
{
Ttemp->left = TBL[K].adress;
};
if (TBL[K1].S.size() != 0)
{
c = TBL[K1].S.at(0);
Ttemp->right->Symbol = c;
Ttemp->right->left = NULL;
Ttemp->right->right = NULL;
} else
{
Ttemp->right = TBL[K1].adress;
};
Ttemp->left->mass = TBL[K].mass;
Ttemp->right->mass = TBL[K1].mass;
Ttemp->mass = TBL[K].mass + TBL[K1].mass;
if (K > K1)
{
TBL.erase(TBL.begin() + K);
TBL.erase(TBL.begin() + K1);
} else
{
TBL.erase(TBL.begin() + K1);
TBL.erase(TBL.begin() + K);
}
Temp.mass = Ttemp->mass;
Temp.adress = Ttemp;
TBL.push_back(Temp);
Temp.adress = NULL;
Temp.mass = 0;
}
TMain = TBL[0].adress;
};
void WriteFile(){
f = fopen("C://1.htxt", "wb");
Bits = OutputS.size();
fwrite((long *) &Bits, 4, 1, f);
unsigned char d = 0;
while (OutputS.size()>0)
{
d = 0;
if (OutputS.size() > 7)
{
for (int i =0; i<8; i++)
{
d<<=1;
if (OutputS.at(0) == '0')
d |= 0; else d|= 1;
OutputS.erase(OutputS.begin());
}
fwrite((unsigned char *) &d, 1, 1, f);
} else
{
N = OutputS.size();
for (int i =0; i<N; i++)
{
d<<=1;
if (OutputS.at(0) == '0')
d |= 0; else d|= 1;
OutputS.erase(OutputS.begin());
}
fwrite((unsigned char *) &d, 1, 1, f);
}
}
short num;
d = 0;
for (int i=0;i<WTBL.size();i++)
{
d = WTBL[i].S.at(0);
fwrite((unsigned char *) &d, 1, 1, f);
num = WTBL[i].mass;
fwrite((short *) &num, 2, 1, f);
}
fclose(f);
}
void AroundTree( struct tree *A){
if ((A->left == NULL))
{
CTemp.ch = A->Symbol;
CTemp.S = S1;
TCD.push_back(CTemp);
} else
{
if (A->left != NULL)
{
S1.push_back('1');
AroundTree(A->left);
S1.erase(S1.begin()+S1.size()-1);
}
if (A->right != NULL)
{
S1.push_back('0');
AroundTree(A->right);
S1.erase(S1.begin()+S1.size()-1);
}}
};
void DReadFile(FILE *df)
{
fread((long *) &Bits, 4, 1, df);
long byte;
long q = 0;
if (Bits %8 !=0)
byte = Bits/8 + 1;
else
byte = Bits/8;
for (int i=0;i<byte;i++)
{
c = 0;
fread((unsigned char *) &c, 1, 1, df);
if (i == byte-1)
for (int j=0;j<(8-byte*8+Bits);j++)
{
if (c & 1)
SOUT.insert(SOUT.begin()+q,'1');
else
SOUT.insert(SOUT.begin()+q,'0');
c>>=1;
}
else
for (int j=0;j<8;j++)
{
if (c & 1)
SOUT.insert(SOUT.begin()+q,'1');
else
SOUT.insert(SOUT.begin()+q,'0');
c>>=1;
}
q+=8;
}
short temps=0;
while ((c= fgetc(df)) != EOF)
{
Temp.S.push_back(c);
fread((short *) &temps, 2, 1, df);
Temp.mass =temps;
DTBL.push_back(Temp);
Temp.S.erase(Temp.S.begin());
}
fclose(df);
}
//------------------------------------------
void main(){
cout<<"Rejim: 1 - coding file, 2 - decoding file"<<endl;
Rej = 0;
cin>>Rej;
if ((Rej != 1) && (Rej != 2))
cout<<"Wrong parametr"<<endl;
else
if (Rej == 1)
{
if ((fin = fopen( "C://1.txt", "rb" )) == NULL )
cout<<"Fail not found"<<endl;
else
{
ReadFile(fin);
if (ITBL.size() > 1)
{
BuildTree(ITBL);
AroundTree(TMain);
int l = InputS.size();
int l1 =0;
while (l1<l)
{
for (int i=0; i< TCD.size(); i++)
{
if (TCD[i].ch == InputS[l1])
{
OutputS=OutputS + TCD[i].S;
i = TCD.size();
l1++;
}
}
}
WriteFile();
cout<<"Vse prosholo horosho, Fail zakodirovan"<<endl;
}
else
cout<<"Empty file"<<endl;
}
} else
{
if ((f = fopen( "C://1.htxt", "rb" )) == NULL )
cout<<"Fail not found"<<endl;
else
{
DReadFile(f);
int i = 0;
BuildTree(DTBL);
Ttemp = TMain;
f = fopen( "C://1.dtxt", "wb" );
for (int i=0;i<SOUT.size();i++)
{
if (SOUT.at(i) == '1')
{
Ttemp = Ttemp->left;
}
else
{
Ttemp = Ttemp->right;
};
if (Ttemp->Symbol != 0)
{
fwrite((char *) &Ttemp->Symbol,1,1,f);
Ttemp = TMain;
}
}
fclose(f);
}
};
getchar();
}
|
|
)
